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!
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.
- 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.
- 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.
- 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.
- 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:
You can use a hierarchy to help you build a complex heuristic.
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.
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…
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.
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.
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!