Review
ss-icon

Hierarchical Planning and Coordinated Plan Execution for Squads of Characters

Alex J. Champandard on January 17, 2008

Traditional game AI techniques like scripts and finite state machines are turning out to be a poor way for designers to build complex character behaviors, in particular group behaviors. Instead, a growing trend is for developers to turn to planners, and hierarchical ones in particular, to help automate the process of assembling behaviors using logical reasoning.

This Thursday theory article on AiGameDev.com looks into a paper by Peter Gorniak and Ian Davis from MadDoc Software, submitted to the AIIDE ‘07 conference last year. This short paper shows how to apply hierarchical task networks (HTN) to generating squad behaviors coordinated among multiple actors in a game.

(Note: The first part of the review is rather technical; skip to the discussion if you get lost!)

Motivation

Beyond just using planners to help the AI behave intelligently, the project has the following goals:

  1. Coordination — It should be easy to specify group behaviors in a centralized fashion and coordinate the execution of multiple actors precisely.

  2. Efficiency — The implementation of the planner should be suitable for realtime use, and integrate well into modern game engines.

Generally, the paper shows how HTN planners can be applied on a larger scale than individual actors, for example coordinating squads of policemen.

Hierarchical Task Network Graph (HTN)

Figure 1: An HTN plan to control squad behaviors. Click to enlarge.

Contributions

There are three things that make this particular research project interesting:

  • A C++ compiler that can turn the problem definition (a.k.a. domain language, specified in Lisp-style syntax) into a set of classes that can be built with the rest of the project.

  • Optimizations for looking up symbols while planning. In practice, a lot of the work of the planner is manipulating world variables while deliberating different options, so any efficiency gain here pays off tremendously.

  • A set of extensions to traditional HTN planner that deal with synchronization and coordination of behaviors among multiple actors.

The idea of using a compiler to help generate efficient code is becoming increasingly popular since JSHOP (a Java-based hierarchical planner that searches for solutions in order). The general idea is to avoid writing a general planner that can solve any problem, but instead write a tool that generates specific planners. Here’s how it works:

  1. Once the problem domain is specified (i.e. the names and types of variables in the world model), a compiler writes out optimized C++ code that deals with variables of known type. The resulting files are compiled into a library during the build, which works as long as the domain is not changed at runtime.

  2. The search itself, even if it’s done in efficient C++ code, may take more or less time depending on the current situation and the complexity of the solution. To make the search easy to interrupt and resume, the whole planner is not implemented in a recursive fashion (which causes large C++ stacks that are hard to debug and prone to overflow). Instead, the code uses a iteration over a stack of possible solutions.

  3. To deal with squad coordination, extra operators are included in the HTN domain. This includes a local and global block that causes the actors involve to wait until the action is finished. There’s also a way to force a particular action to finish, aborting it rather than letting it finish itself. (This is shown in the diagram above.)

The paper itself doesn’t go into too many details, but if you’d like more information about planner domains and problem representation, read this previous article.

Abstract & References

Here’s the abstract for the paper:

“This paper presents an application of Hierarchical Transition Network (HTN) planning to a squad-based military simulation. The hierarchical planner produces collaborative plans for the whole squad in real time, generating the type of highly coordinated behaviors typical for armed combat situations involving trained professionals. Here, we detail the extensions to HTN planning necessary to provide real-time planning and subsequent collaborative plan execution. To make full hierarchical planning feasible in a game context we employ a planner compilation technique that saves memory allocations and speeds up symbol access. Additionally, our planner can be paused and resumed, making it possible to impose a hard limit on its computation time during any single frame.

For collaborative plan execution we describe several synchronization extensions to the HTN framework, allowing agents to participate in several plans at once and to act in parallel or in sequence during single plans. Overall, we demonstrate that HTN planning can be used as an expressive and powerful real-time planning framework for tightly coupled groups of in-game characters.”

You can download the paper from the website (PDF, 614 Kb):

SquadSmart: Hierarchical Planning and Coordinated Plan Execution for Squads of Characters
Gorniak P. and Davis I.
Proceedings of Artificial Intelligence and Interactive Digital Entertainment (AIIDE), 2007.

Evaluation

Here’s how I think the technology in the paper ranks in practice:

Applicability to games: 8/10
For games with a large and complex world that require an efficient planner to generate the behaviors, this kind of technology should be very helpful. This would be the case for squad-based shooters and other simulations which require a certain level of logical behaviors.
Usefulness for character AI: 8/10
Not all games require coordination between squad member’s, nor do they have large enough domains to warrant a compiler as opposed to a normal planner. However, this technology should generally make the behaviors more efficient in most other cases..
Simplicity to implement: 2/10
The major pitfall of this technology is that it takes a lot of work to reach a level of understanding that’s required to build a planner compiler that’s based on custom domain definitions! The actual implementation may not take too long if you know what you’re doing, but not many people have that experience in the industry — yet.
LISP Hierarchical Task Network HTN


Screenshot 2: A custom hierarchical task network (HTN) specified with S-expressions.

Discussion

If most of this article went over your head, don’t worry. I expect only a handful of people reading AiGameDev.com could fully grasp what’s involved in implementing this paper. (If you’re one of those people, please post a comment!)

The process of building tools… to create planners… that generate behaviors… responsible for controlling characters is not something that’s easy to think about. In fact, this kind of research combines some of the most advanced forms of AI (hierarchical planners) with the most difficult field of computer science (language and compiler design).

That said, I think it’s extremely promising technology — particularly on the middleware front. The overall workflow of such a tool would be as follows:

  • Describe each of your actions and conditions, explaining what C++ functions should be called under what situations.

  • Specify the behaviors as a plan using these actions and conditions in a text file which uses S-expressions like Lisp.

  • Click on Generate Code in the editor, and the tool outputs a C++ file that can solve the problems in the way you specified.

  • Integrate the resulting source file into your engine. Call the appropriate function in the API as specified by the middleware vendor, and let it run!

It seems like a rather nice workflow! The question is, however, how long would it take for this kind of technology to be available on the market?

What do you think about the technology in this paper, and its applicability for controlling AI actors in games?

Discussion 2 Comments

William on January 17th, 2008

AFAIK, the use of JSHOP2 (or a derivative) brings both an advantage and a disadvantage. The clear advantage is the planner-compilation design (although it probably hasn't been easy to translate JSHOP2's compiler and support library from Java to C++). A disadvantage is JSHOP's lack of support for selecting a method/rewrite-rule based on expected and actual costs/benefits. Without this kind of support, alternative plans (methods) are chosen based on the order of method declaration. I guess the domain at hand (a 4 man SWAT team clearing a house to detain a suspect?) does not feature many alternative drills for the same situation (figure 2 in the article seems to suggest this). In an A* based planner, such as Jeff Orkin's GOAL, alternative plans naturally compete based on costs, and the most attractive plan will be detailed until it ends up complete, infeasible, or (again) more expensive than the alternative.

alexjc on January 18th, 2008

[B]William,[/B] Ah yes, that's a great point! I'll have to write about that topic in the coming days... Both solutions encode the domain expertise in very different ways (hierarchy vs. heuristic), as well as searching for solutions differently (local improvement of a single solution vs. global comparison of many candidates). I'm not sure what the "official" terminology is for that last trait, but I'll see what I can find. Anyway, there's lots to talk about there. :-) 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!