Since F.E.A.R., the use of planners in commercial game has been growing steadily — particularly those based on heuristic A* search. However, a primary concern is performance, as it can take a lot of resources to compute even the smallest plans within a typical level of a FPS.
A solution to such problems involves using a hierarchical search instead, which isn’t only more efficient but also provides more designer control. The SHOP planner, or Simple Hierarchical Ordered Planner, built by the University of Maryland addresses these issues head on.
This Thursday Theory article from AiGameDev.com looks into the paper behind this planner, explaining how it works conceptually, then analyzing its applicability to games. If you have any experiences or comments about this technology, feel free to post them below!
In the context of Hierarchical Task Network (HTN) planners, SHOP focuses on two core issues in planning research and development:
Planners can always benefit from being faster. This research in particular aims to show how total-order forward search (where each action is applied in order from the start state) can in fact be a more efficient way to encode domain knowledge.
For many types of planners, including HTN, their limitation is in the flexibility of the domain. Custom procedural functions can be hard to integrate when you don’t know how the planner may combine actions while planning. So instead, it can be better to limit the expressiveness of the planner (by imposing an order on the plans) to make it easy to insert custom logic.
SHOP addresses these two issues to build a planner that can solve problems more efficiently using domain knowledge encoded as custom logic.
Figure 1: A visual representation of a Hierarchical Task Network (HTN).
HTN already helps encode domain knowledge very efficiently for planners. But there two key ideas help SHOP achieve these goals of efficiency and customizability:
The plan is expanded one action at a time in the order in which it will be executed. This results in a total-order algorithm, which helps reduce conflicts and keeps things simple.
The planner always knows the full state of the world at the current stage, since it worked out the consequences of each action until now. This allows custom procedural code to be included easily.
In practice, SHOP implements this using the following techniques:
Like most planners, the domains are expressed in dialect based on S-expressions (see the paper for an example). In fact, the planner itself is written in Lisp — yet it remains competitive with other planners written in lower-level languages.
Typically, HTN planners use methods and operators to describe their problems (the tree-like domain), but SHOP requires additional axioms to help it infer conditions about the current state effectively.
The planner is implemented as an efficient depth-first search, which traverses the tree from left to right. This procedure recursively expands composite tasks until it hits an atomic task, building up the resulting plan in a list.
Combined together, these two implementation tricks make this planner one of the simplest yet most efficient HTN implementations available.
Listing 2: A simple domain written with Lisp-like syntax.
Abstract & References
Here’s the abstract for the paper:
“SHOP (Simple Hierarchical Ordered Planner) is a domain-independent HTN planning system with the following characteristics.
SHOP plans for tasks in the same order that they will later be executed. This avoids some goal-interaction issues that arise in other HTN planners, so that the planning algorithm is relatively simple.
Since SHOP knows the complete world-state at each step of the planning process, it can use highly expressive domain representations. For example, it can do planning problems that require complex numeric computations.
In our tests, SHOP was several orders of magnitude faster man Blackbox and several times faster than TLpian, even though SHOP is coded in Lisp and the other planners are coded in C.”
You can download the paper from the website (PDF, 331 kb):
SHOP: Simple Hierarchical Ordered Planner D. Nau, Y. Cao, A. Lotem, and H. Muñoz-Avila. International Joint Conferences on AI, 1999.
Here’s how I think the technology in the paper ranks in practice:
- Applicability to games: 6/10
- The average games don’t often need planners as the desired behavior of most controllers (e.g. for the actors) is often reactive instead of deliberative. However, given its simplicity and efficiency, a planner like SHOP could very well be built to replace traditional scripting languages and give developers the ability to solve parts of problems automatically.
- Usefulness for character AI: 8/10
- For character AI, SHOP seems very useful as it will help create intelligent, purposeful context-sensitive behaviors. Anywhere you’d consider a planner you should also include this solution as an option. The down side, of course, is that you’ll need a lot of “execution” logic to apply and monitor the plan also.
- Simplicity to implement: 6/10
- As far as planners go, this is probably one of the simplest to implement, on a par with the A* (A-Star) based STRIPS algorithm. The challenge, however, is figuring out how to apply it efficiently and create domains that solve the problem according to the game design.
Figure 3: A plan resulting from the domain HTN listed above.
According to the latest trends, HTN planners are on the rise. You’ll find them in upcoming middleware offerings this year, and presumably in a bunch of games too. They make lots of sense for the typical first- or third-person shooter type game to control the enemy soldiers intelligently.
SHOP is an ideal way to get started with this kind of technology, and there’s even an open-source implementation in multiple languages. It’s relatively simple to understand and implement compared to other solutions, and it has many speed benefits too. You’ll be able to customize it easily to suit the needs of your game.
What do you think about the technology in this paper, and its applicability for controlling AI actors in games?