An Introduction to Behavior Trees

If you’ve been following our work at Adinkra, you know we are developing flexible behavior systems for many kinds of robotics applications and products. One of the most important methods we use to do this involves what are called behavior trees. Behavior trees allow our team to develop modular robotic behaviors for various tasks in an intuitive, graphical way, drastically reducing our development time and enabling better overall architectures and performance. In this article, we will introduce the general concepts and applications of behaviors trees so you can improve your robotics engineering process.

Basic Behavior Tree Structure

Behavior Trees (BTs) first became popularized in computer games such as Halo 2 and have since become ubiquitous across applications in game development, robotics, control systems, and more. Fundamentally, a behavior tree is a computational model of execution which allows a system to switch between tasks in a predictable way. Examples of tasks could be “takeoff” for a quadcopter drone, or “pick up this object” for a robotic arm. Hence tasks can vary widely in complexity and may include multiple steps and conditions to successfully accomplish.

Tasks are executed by nodes, with the root node denoting the start of the process. In graphical representations of behavior trees, the root node of the tree is typically drawn at the top. The other nodes are then connected via arrows and follow a specific ordering of top to down and left to right. Nodes can be additionally designated as child nodes, parent nodes, tree nodes and leaf nodes based on their relationships to other nodes in the graph.

Figure 1 best shows the nodes (blue boxes), execution order (number in the box), and hierarchical parent-child relationships (arrows). Each node may execute any number of tasks, or be combined with other nodes to execute more complex behaviors.

The process by which the next task is executed is called a tick. A tick is a general command signal that propagates through the tree based on its structure but does not itself contain an execution context. Rather, when a node receives a tick, it begins executing its respective tasks by pulling from a shared context (i.e. shared data cache) available to all nodes in the tree called a blackboard and then returns one of three values:

• Success
• Failure
• Running (in asynchronous or long-running tasks)

Advantages Over Finite State Machines

Because behavior trees share context and nodes only return one of three values, behavior trees are extremely modular. This enables developers to easily reorder nodes, create subtrees, and modify behaviors as they develop, which pays off when implementing large and complex robotics system that need constant iteration. This also gives behavior trees an advantage over their generalized counterparts, Finite State Machine (FSM). With FSMs, maintainability and flexibly are major issues because changes to one state often require modification of at least two addition states and they no longer maintain a clear hierarchy.

A Basic Example: Sequence Nodes

We can create a basic behavior tree by introducing a basic control node called a sequence node. Sequence nodes have the task of ticking all children in order from left to right. If any child fails along the way, the sequence node will also return failure and stop ticking children. If all children return success, then the sequence node will also return success.

An example tree using the sequence node is shown in Figure 2 for the application of a multi-rotor drone. It consists of a single sequence node (denoted by the top block with the arrow) and three other nodes: Arm, Takeoff, and Hover. While the underlying tasks for each node may not be trivial to implement, once completed, the BT sequence structure makes it easy to compose these into more complex behaviors.

For developers familiar with libraries such as BehaviorTree.CPP, this tree can be equivalently defined using XML as below:

Snippet 1. XML for a behavior tree from Fig. 1

Fallback Nodes

So far, we have built a simple behavior system for a multi-rotor drone to arm, take-off, and hover in place. But let’s suppose we want to prioritize more safety in our design: if any of these actions fail, we would like the drone to land and disarm. Nodes that handle such cases of failure are called a fallback node (sometimes also called a selector node), and they are extremely important for real-world autonomous systems.

Fallback nodes work by ticking their children like a sequence node except they return success if any child node returns success, and return failure when all children return failure. In other words, when a fallback node attempts to tick a child node and gets a failure, it falls back to the next child node in the sequence in the hopes that this node can return a success.

Figure 3. shows how the fallback node (denoted with the “?” symbol) can be combined with sequence nodes for more robust behavior system. In this example, the drone will attempt to arm, takeoff, and hover as orchestrated by the left sequence node. If any of those actions result in failure, the left sequence node also fails. The fallback node, having had one of its children fail (in this case the left sequence node) will then attempt to call the next child node in hopes of a success (in this case the right sequence node). As the right sequence represents a safe landing behavior, we have effectively fallen back to a safe operational sequence when something cause the nominal left sequence to fail. 

Decorator Nodes

Building on our example from Fig. 3, let’s now consider a waypoint mission for our drone. For simplicity, let’s say we want to fly through a fixed set of five waypoints. We can build this functionality as the sub-tree shown in Figure 4 using a sequence node.

Now, imagine that we execute this subtree just after takeoff. Do you see a potential issue in using a sequence like this? Because we are using a sequence node, any failure in achieving the waypoint would cause the whole sequence to return failure. If we had our fall back behavior in place, then this would trigger the landing sequence. Depending on the specifics of your mission, this might not be something you would want to happen. For example, your waypoint may be outside of your geofence or there might be a hazard directly beneath you!

Instead, we may want to ensure that the drone will at least attempt to fly through all mission waypoints, even if it cannot achieve some of them. To achieve this, we can use a so-called decorator node to modify the outcome of a child node before continuing execution of the behavior tree. 

In Figure 5., we can see that decorator nodes called “Force Success” do just this. In our example, if we force waypoint nodes to succeed before continuing on in our sequence – regardless if they actually failed or not – we can ensure the rest of the sequence node’s children are at least attempted.

Adding the Mission sub-tree to our behavior tree now allows us to safely fly a robust waypoint mission as shown in Figure 6.

Final Thoughts

Behavior trees are extremely useful for our robotics development process at Adinkra. While we have only covered the basics here – and more complex real-world behaviors require more advanced structures and concepts – this introduction already enables you to develop extremely safe, capable robotics systems. Behavior trees are key for accelerating your robotics development and are especially well suited for applications where tasks and transitions can be clearly defined. We note that if your tasks are more open-ended or your environments are less defined, then other methods such as reinforcement learning, might be more useful. Of course, depending on the details, multiple methods can be merged to create truly powerful autonomous systems.

If you would like to learn more about behavior trees, here are some additional resources:

• BehaviorTree.CPP Documentation
• Behavior Trees in Robotics and AI: An Introduction
• Behavior Trees for UAV Mission Management
• Asynchronous Behavior Trees with Memory aimed at Aerial Vehicles with Redundancy in Flight Controller

About Adinkra

Adinkra is an R&D engineering firm helping customers create state of the art robotics and AI products while minimizing costs and time to market. We combine a world-class engineering team with a flexible project management framework to offer a one-stop development solution and unlock your product’s full potential for your customers.