An Introduction to Behavior Trees
If you read our previous articles, you might have noticed that we are developing flexible behaviors for the robots we are working on so that they can execute on their mission objectives. While there are many ways to accomplish advanced behaviors on a robot, behavior trees play an important role in robotics because they allow us to create modular actions in a robotic system in a graphical way and, at the same time, allow us to keep a clean structure of transitions between various tasks.
Behavior Trees are great if you can clearly define the tasks that should be performed in your systems. If you want your actions to be more fluid and in an environment that is not as defined, then Reinforcement Learning might be a better choice. Of course, depending on the finer details, you can merge the two methods to create very powerful systems for carrying out complex missions autonomously.
Even though we won’t go too much into technical details in this blog post, we will provide you with tools that will allow you to build intuition on creating complex robot behaviors.
Introduction to Behavior Trees
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 model of execution that allows us to switch between a finite set of tasks. Tasks are executed by nodes, with the root node denoting the start of the process. Traditionally, in a behavior tree, the root of the tree is drawn at the top, and the order of operations is top->down and left->right.
The process by which the next set of task is executed is called a tick. A tick is a signal that is going through the tree based on its structure. When a node receives a tick, it will begin executing its respective tasks and then return one of three values:
- Running (in asynchronous or long-running tasks)
Nodes connected to other child nodes can execute new ticks based on their state. Nodes connected to children are also be called tree nodes, while nodes without children are called leaf nodes.
BT vs. FSM
BTs are actually a special case of a more general structure called a Finite State Machines (FSM), with the constraint that behavior tree nodes are more hierarchical, modular, and self-contained. While FSMs are intuitive and used across many robotics and artificial intelligence applications, their main issue is maintainability, as many who have worked with large state machines can confirm. For example, if you want to only insert a single state in the middle of your FSM, then you generally need to modify at least two other states. It’s also quite rare that you can reuse the same state machine in multiple scenarios.
In contrast, Behavior Trees are more modular, which quickly pays off when you start implementing large and complex systems that need to be improved or redesigned from time to time. This modularity is achieved through a data caching mechanism called a blackboard that is accessible to all nodes. This allows nodes to always have the context they need to execute, independent of where they are being called, enabling developers to easily reorder nodes and develop modular subtrees which can be reused across the system.
Modularity, coupled with a more restrictive set of results for each node (Success, Failure, or Running) ends up producing a cleaner and more maintainable execution graph.
A Basic Example
We can create a basic behavior tree by introducing a basic control node called a sequence.
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.
This simple behavior tree is shown in figure 2. It consists of a single sequence node (denoted by the top block with the arrow) and three other nodes: Arm, Takeoff, and Hover. With this structure, the BT is designed to execute the actions one after another in a sequence.
For developers, there is a standard library called BehaviorTree. CPP which allows us to declare behavior trees using XML. Our simple behavior tree can therefore be also defined in the code snippet below.
<root main_tree_to_execute = “MainTree” >
Snippet 1. XML for a behavior tree from Fig. 1
By now, you can probably see how flexible BTs can be. Let’s try to extend our simple example into something more involved.
We’ve started our behavior tree with an example of a multirotor drone that would be armed, take-off, and hover in place. We want to prioritize safety in our design, so if any of these actions fail, we would like the drone to land and disarm. This behavior in the case of failure is called a fallback (sometimes also called a selector) control node, and is extremely important for real-world autonomous systems.
Fallback nodes work by ticking their children like a sequence 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 a powerful and robust behavior. 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.
Let’s build on this example by now considering an actual mission for our drone. For simplicity, let’s say we want to fly through a fixed set of five waypoints, and for simplicity, let’s build this functionality as a subtree:
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, any failure in achieving the waypoint would cause the whole sequence to return failure, triggering our fallback and starting the landing sequence. Depending on the specifics of your mission, this might not be something you would want to happen, for example, if you happen to accidentally place one of your waypoints outside of your geofence.
Instead, we might want to relax our drone operations 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 decorator node to modify the outcome of a child node before continuing execution of the behavior tree.
In Figure 5., we can see that decorators are nodes that only have a single child and usually modify the result of that child node’s result. In our example, if we force waypoint nodes to succeed before continuing on in our sequence, regardless of if they actually failed or not, we can ensure the rest of the sequence node’s children are attempted.
We can then add the robust waypoint Mission Subtree we created in Figure 5. to our behavior tree as shown in Figure 6. While simple, this full tree allows us to safely fly a drone for a waypoint mission.
These are just the basics of working with Behavior Trees. To perform complex behaviors in real life – such as gimbal control, target acquisition, checking battery levels, or determining landing zones – behavior trees will need additional functionality and structures to ensure successful and safe operations.
If you would like to learn more about behavior trees, then here are some great resources on the topic:
- 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
- The Future of Robotics is Now and it’s Open-Source
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.