Article
files/essays/icon-map

Heuristic vs. Hierarchy: Domain Knowledge for Planners

Alex J. Champandard on January 18, 2008

Most situations in commercial games have very large problem spaces, so it would take a long time to list all the possible AI behaviors… In order for planners to solve such problems in real-time, they must effectively discard as many useless options as possible.

Generally speaking, you can approach the implementation of such planners using a heuristic or using a hierarchy. The rest of this essay describes this concept of domain knowledge, then explains how both these optimizations work using pathfinding in a 2D terrain as an example, and finally tries to judge which is best!

Fridays at AiGameDev.com are dedicated to reader questions. This topic was chosen based on two opposing comments: William yesterday [1] about a possible lack of expressiveness of Hierarchical Task Network planners like SHOP, and pemjahat about performance of STRIPS planners in MMO games in the forums [2] (registration and introduction required).

What Is Domain Knowledge?

Domain knowledge is basically information about the nature of a problem that helps find a solution. For example, in the case of a 2D terrain, there are two kinds of domain knowledge:

  • Problem Type — If you know the graph that you’re searching represents a map, then you can add optimizations to guess which direction is most likely to lead to the goal.

  • Problem Instance — Moreover, if you understand the specific layout of the terrain that’s currently being searched, then you can make even better guesses.

Without domain knowledge, solving a problem is just a matter of raw computation power and memory. Keep in mind, however, that some problems might never be solvable in practice with a real computer; you’d run out of time or space before getting anywhere.

Domain knowledge effectively makes it possible to find a solution much faster and using less memory. Thus, acquiring and using domain knowledge is an important aspect of intelligence — and game AI!

A Heuristic Approach

A heuristic is typically a function that is capable of assigning values to different options to help compare them together. The heuristic is typically implemented based on rules of thumb designed by human experts. For example, a heuristic for pathfinding would help pick a path that moves closer towards the target.

With a heuristic in place, the search algorithm can then estimate the value of the different candidates, compare them together, and explore the best options first. This is how the A* (A-Star) pathfinding works like in this demo.

Heuristic Domain Knowledge on 2D Terrain Map

Figure 1: A 2D map colored using a distance heuristic. (Click to enlarge.)

Advantages
This approach does not make any structural changes to the search graph. Only the order in which nodes are searched varies based on the heuristic function.
Disadvantages
The size of the search space remains the same. Also, building a heuristic can be a complex task, so it can negatively impact performance in special cases.

The Hierarchical Approach

Instead of ordering all of the possible solutions, a hierarchical approach restructures the graph by adding higher-level information to guide the search. The hierarchy is either assembled manually or generated from the low-level graph automatically. For example, this could be connectivity information for a 2D map.

Essentially, this creates a very small search space that partitions the old search space into many smaller chunks, thereby guiding the search. A large number of low-quality solutions are thereby completely discarded using this approach.

Hierarchical Domain Knowledge on a 2D Terrain Map

Figure 2: The same domain with a higher-level map. (Click to enlarge.)

Advantages
This approach matches human reasoning better, as it uses recursive decomposition of a problem. It can be a lot faster too, as it doesn’t require estimating different candidates and comparing them together.
Disadvantages
The hierarchical approach requires a person or tool to generate a hierarchy in the search graph. Also, this approach can be theoretically suboptimal, as it discards certain solutions for the sake of speed.

Do Hybrid Approaches Make Sense?

Things get interesting when you look at it this way:

  1. You can use a hierarchy to help you build a complex heuristic.

  2. A heuristic can be used as a guide to generate a hierarchy.

Effectively, despite being opposing approaches, there’s a certain amount of overlap between the two. In fact, modern pathfinders in games combine these two approaches together; the hierarchy simplifies the overall search space, and the heuristic helps solve the lower-level problems.

Figure 3: The same domain using a hierarchy and a heuristic. (Click to enlarge.)

Don’t Forget Your Search Algorithm!

This analysis of planners isn’t quite over yet! While it’s possible to mix these two types of domain knowledge, the choice goes hand in hand with your search algorithm — which basically is the most important decision you have to make when applying a planner. Roughly speaking, there are two choices…

Breadth-First Search

BFS algorithms are always optimal as they consider all possible options together. The down side, of course, is that it takes a lot of memory to store all this while searching! BFS can be implemented with a simple FIFO queue (first-in first-out) that can grow very big.

In practice, for BFS to work effectively, you must rely on a heuristic. By using the evaluation function to sort the candidates in the queue, it prevents the algorithm from having to remember every possible option. Instead, it only has to store the minimal number of candidates to reach an optimal solution.

That’s how A* search and the STRIPS planner works. These algorithms are very effective at finding provably optimal solutions using only rough guidance in the form of a heuristic.

Depth-First Search

A DFS search is very memory efficient because it makes lots of rash assumptions by picking the first branches in the graph without considering alternatives. This can be implemented with a simple LIFO stack (last-in first-out) that takes almost no space.

In practice, for DFS to work effectively, you must use a hierarchy. The higher-levels of domain knowledge in the hierarchy help turn the rash decisions of the search algorithm into an advantage: early commitments in the right direction.

HTN (hierarchical task network) planners use this approach, particularly the ordered planners like SHOP. As a consequence, these planners are hands down the most efficient in the world when there domain knowledge available — which is perfect for game development.

Summary

When applying a planner, you have a choice to make:

  • If you have very little memory available, then use an ordered HTN planner based on DFS and expect to spend time modeling your hierarchy. In this case, you’ll probably use less computation time too.

  • If you have enough memory available, then use a STRIPS-like planner based on BFS and prepare to tweak your heuristic regularly. Here, you can expect to get optimal solutions instead.

In either case, you’ll certainly spend lots of time modeling your domain knowldege to make sure the planner operates efficiently!

Discussion 2 Comments

Ian Morrison on January 19th, 2008

Based off some of the ideas that were thrown around in this thread about [URL="http://aigamedev.com/forums/showthread.php?t=205"]achieving a smoother transition between scripts and autonomous AI[/URL]: One of the things talked about is the idea of giving a list of goals via script instead of a series of actions. The AI would then decide on the actions to take to satisfy the scripting goal, hopefully leading to an AI that was still reacting to the world even in scripted sequences. Reading the article, I think that the hierarchal planner described would be an ideal fit for this. The higher level actions in the domain normally would be chosen autonomously, with the smaller actions being filled in later in the plan. When the level designer wants scripting control, however, they can override the higher level actions with a list of their own. The intermediate steps would not be tampered with by the designer, though. The planner itself would fill them in as it went, as it did when it was selecting it's own high level actions. Would this work for that purpose, or am I missing something here? I'm not entirely sure how designer specified goals and actions could be fit in at runtime, since they'd probably be unique, one-off things, so that might break the planners.

alexjc on January 19th, 2008

[B]Ian, [/B]You're absolutely right. The fact that a hierarchical planner breaks down tasks recursively from the top is the key feature for me. It's great for both autonomous AI and designer control! I wrote the article to be a rather balanced analysis, but I do prefer the DFS/HTN approach by a long way. You can use tricks to tweak them into giving you more optimal results like A* if that's the biggest problem... Alex

If you'd like to add a comment or question on this page, simply log-in to the site. You can create an account from the sign-up page if necessary... It takes less than a minute!