Featured Blog | This community-written post highlights the best of what the game industry has to offer. Read more like it on the Game Developer Blogs or learn how to Submit Your Own Blog Post
A comparison of behavior trees and the ABL planning language.
EISBotABT
While preparing for the 2011 Paris Game AI conference, Alex Champandard asked me if there are any differences between ABL and behavior trees (BTs) at the planning level, which motivated me to dig a bit deeper into this topic. The goal of this post is to distinguish differences between behavior trees and ABL. While I am contrasting ABL with the Behavior Tree architecture described in Alex’s chapter in AI Game Programming Wisdom 4, I am aware that there are several flavors of BT implementations so feel free to add feedback or corrections based on any BT variant.
First, some background. ABL (A Behavior Language) was developed by Michael Mateas and used to author the behaviors for the autonomous characters in the interactive drama Façade. ABL is a reactive planning language that builds on the semantics of Hap, which was developed as part of the Oz project at CMU. ABL is currently being used in several projects at the Expressive Intelligence Studio, and I am using ABL to author EISBot, an opponent AI for StarCraft.
To kick off this discussion, I’ll be focusing on the differences between the decision cycle processes in ABL and BTs. There are several other topics that can be discussed such as sensors, actuators, and working memory, but I want to discuss planning aspects.
One of the main differences between the decision cycle processes is that ABL runs asynchronously from the main game update, while BTs are updated during an AI tick. Synchronization with the game is achieved through the agent’s actuators and sensors. While ABL could be modified to run during an AI tick, the tree may need to be evaluated multiple times per tick, if controlling multiple units. By default, an ABL agent will run at 60 updates per second if no behaviors are available for execution. If behaviors are available for expansion, then additional updates will occur each second.
In ABL, the behavior tree is expanded as needed. An ABL agent is instantiated as a single root behavior, which can subgoal additional behaviors. When a behavior is selected for expansion, its steps (child nodes) are added to the active behavior tree (ABT). Leaf nodes in the ABT are nodes that are available for execution, unless currently executing.
Success-failure propagation is similar between the two techniques. In ABL, if any step in a behavior fails, the entire behavior fails and failure is propagated up the tree. At each node in the ABT, ABL will attempt to run additional behaviors with the same name and input parameters as the failed behavior. If no additional behaviors are available for execution, or all matching behaviors have failed, then failure is propagated to the node that selected the failed behavior for expansion. There are several types of decorators in ABL for handing success and failure in the ABT.
Another difference between ABL and BTs is action scheduling. In ABL, an action begins executing as soon as it is selected by the decision cycle. During action execution, the leaf node executing the action is marked as executing and the decision cycle process continues. Action execution does not stall the decision cycle, and concurrent action execution can be achieved using parallel behaviors. In BT systems, action selection and action execution are decoupled; the BTs determine which actions to perform and a scheduler is responsible determining when to execute the actions.
ABL is a language, while BTs are a data structure. ABL agents are compiled to Java and executed by the ABL runtime, which is written in Java. One of the advantages of this approach is that an ABL agent can include small Java snippets inline in behaviors. The huge disadvantage is that an ABL agent’s behaviors cannot be modified during runtime. I’ve discussed the idea of building an ABL interpreter with Michael Mateas, and we might explore this option in the future.
The semantics of ABT and BTs are different, but there are several similarities. Alex discusses the following node types in the AI Game Programming Wisdom 4 chapter:
Sequence: Expresses a linear sequence of actions or behaviors to perform.
Selector: Selects a single child to execute.
Parallel: Expresses a set of actions or behaviors to perform concurrently.
Decorator: Wraps a node to extend its functionality.
In ABL, all nodes in the ABT are behaviors. A behavior contains a set of steps to perform, which are expanded as nodes on the ABT. Behaviors can be sequential or parallel. In a sequence behavior, the steps are executed in a linear sequence, providing the same functionality as a sequence node. In a parallel behavior, the steps are available for concurrent execution, providing the same functionality as a parallel node.
In ABL, several step types are available:
Act: Specifies a physical action to perform, such as moving an NPC to a location. Acts are mapped to actuators, which perform the execution of the action in the game
Mental act: An atomic piece of arbitrary Java code. Mental acts are often used to update working memory. Mental acts are performed during the decision cycle process and therefore mental acts that take a long time to perform will stall an agent’s decision cycle.
Subgoal: A high-level control flow structure for specifying a sub goal to pursue. When a subgoal node is selected for expansion, the goal node is added to the ABT and behaviors with matching names and parameters are selected for expansion. Subgoal provides the same functionality as selector nodes in BTs.
Spawngoal: Similar to subgoal, but the goal node is added at the ABT root instead of the parent behavior. The spawned goal will be pursued concurrently with the current goal. Subgoal is analogous to spawning a new thread of execution within an ABL agent.
Fail: A fail step causes a behavior to fail, which will result in the behavior propagating failure up the ABL.
Succeed: Causes a behavior to succeed, which is the default result of a behavior. This is only used in behaviors that would otherwise have 0 steps. (ABL behaviors must have at least 1 step)
Wait: A blocking step. A naked wait will result in a behavior that never completes. Waits can also be combined with a success test, which waits for a condition to be true. For example, a behavior may contain two steps, where the first step issues a physical action to move to a location, and the second step is a wait with a success test that suspends the behavior until the NPC has reached the target location.
Steps in ABL can be annotated with modifiers, which provide the functionality of the decorator node in BTs:
Priority: Assigns a priority to a step. If multiple steps on the ABT are available for execution, the step with the highest priority will be selected.
Persistent: Causes a step to be retired indefinitely despite success or failure.
Ignore failure: Causes the step to always return success, ignoring failure or success of the step.
Persistent when succeeds: The step is retried until it fails.
Persistent when fails: The step is retried until it succeeds.
Effect only: The step is optional and does not need to be executed for the behavior to complete. Effect only steps are used to add decorative behavior to an agent. Effect only behaviors always return success.
In addition to a collection of steps, ABL behaviors can contain several modifiers:
Preconditions: A set of conditions that must evaluate to true for a behavior to be selected for execution.
Context conditions: A set of conditions that must remain true during the duration of a behavior. If a behavior’s context conditions evaluate to false during execution, the behavior is immediately aborted and failure is propagated up the tree.
Specificity: Specifies a priority for behavior selection. When a subgoal node is added to the ABT, behaviors will be selected for expansion from highest specificity to lowest specificity.
Success conditions: A set of conditions that will terminate the behavior and return success if evaluated to true during the execution of a behavior.
Number needed for success: The number of child steps that need to successfully complete for the behavior to return success. The behavior completes immediately after the number of steps needed for success is met.
That concludes my comparison of the planning aspects and semantics of ABL versus BTs. Further reading:
A Behavior Language for Story-Based Believable Agents: Provides an overview of the ABL language.
Reactive Planning Idioms for Multi-Scale Game AI: Presents ABL idioms used in EISBot.
Interactive drama, art, and artificial intelligence: Michael Mateas' dissertation, which includes a chapter on ABL.
Believable Agents: Building Interactive Personalities: Bryan Loyall's dissertation, which includes an overview of Hap, the predecessor to ABL.
Read more about:
Featured BlogsYou May Also Like
