ABL versus Behavior Trees

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:

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:

Steps in ABL can be annotated with modifiers, which provide the functionality of the decorator node in BTs:

In addition to a collection of steps, ABL behaviors can contain several modifiers:

That concludes my comparison of the planning aspects and semantics of ABL versus BTs. Further reading: