Article
i/2007/07/parallel

Enabling Concurrency in Your Behavior Hierarchy

Alex J. Champandard on July 10, 2007

Assume you have a tree of behaviors, with conditions and actions as leaf nodes, and sequences and selectors as branches. This type of logic is very linear, and will only ever do one thing at a time. So how do you get your AI to support concurrent behaviors?

The answer is to use a parallel composite as a branch in your tree, which runs all the child behaviors at the same time. The parallel is fully responsible for its child behaviors, and shuts them all down cleanly when it terminates.

Parallel Behavior Trees

A parallel used to fork execution into two sub-trees.

The parallel isn’t the only pattern to deal with concurrency, but it gives you the most bang for buck.

Configuring Parallel Behaviors

You’ll quickly find it useful to implement your parallel behavior with some basic control options, such as when and how to terminate. This can be summed up with two policies:

Failure Policy
How many children need to fail before the parallel fails? You can specify this as a number, or ideally just a boolean option: require all of them or require just one.
Completion Policy
How many child behaviors should complete for the parallel to complete? Again, you can set a specific number, but it’s simpler to keep two options: require all or require one child.

These two options are used together for every parallel; they are not mutually exclusive. For example, the parallel could be waiting for all child behaviors to complete, and fail immediately if one fails. If the policies for failing and completing successfully are both true at the same time, then it’s safer to just fail.

You may also use the concept of a master behavior within the parallel. The parallel would be entirely synchronized around that specific child behavior, so when it completes or fails, the parallel does the same.

Required Features for Parallels

To use parallel behaviors, it helps if you’ve implemented a scheduler to run behaviors at the same time without having to micro-manage them. It’s also ideal to use the scheduler observers too, then your parallel won’t run actively every update but instead wait for notification from the child behaviors.

Having parallel trees is also much easier if the atomic behaviors are designed for concurrency. Ideally, you want low-level behaviors that are independent from each other, or capable of cooperating.

Advice for Using Parallels

1. The best place to use a parallel — without worrying about concurrency problems — is to group a single action with multiple conditions. Only the action has side effects in the world, so there are no possible conflicts. (The conditions just query information from the world.) This allows you to attach preconditions to any action, and make sure they are monitored during execution.

2. It’s also safe to use parallels with completely different behavior trees. For example during a patrol, one tree controlling the head for looking around, and the another for deciding where to go. There are no possible conflicts there, so a parallel is safe to use.

3. For more complex behaviors, where there are multiple trees with side-effects running in parallel, you need another pattern to make sure that these trees are synchronized. This is discussed in the next article in this section…

Discussion 2 Comments

bknafla on February 18th, 2008

The task system you describe sounds similar to the task system used by Intel Threading Building Blocks (unsurprisingly - both are task systems). It might be interesting to see if Game::AI++ can be adapted to use TBBs tasks system to enable truly parallel execution of behavior trees. Though my current gut feeling and the experience of one of my students who implemented BTs in Java for a parallel game-simulation/agent-modell (hi Dennis ;-) ), indicate that at least small BTs are executed so fast, that it might be better to just execute/evaluate them sequentially but evaluate the different agents that use BTs in parallel to each other. Cheers, Bjoern

alexjc on February 19th, 2008

[B]Bjoern[/B], The kind of tasks I use are implemented as a superset of what Erlang does. So, if I setup my tasks to communicate data by copying it only (like Erlang), then I'm at least as well positioned to parallelize the system. However, as you said, it doesn't always make sense to do so for small trees. It also needs to be done in a sensible way, for example batching tasks that use the same data or do similar computation. (See my [URL=http://aigamedev.com/site/2008-plan-killzone]research goals[/URL] for the next year for more about that in the context of "smart" sensory systems.) In general, I think that it makes sense to start a separate thread everytime you hit a selector while planning, so you can search every branch in parallel, and then compare options afterwards. This kind of parallelism scales to N cores very quickly, and would really benefit most applications these days — I believe. Cool stuff anyway! 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!