|
Behavior Trees: Simple yet Powerful AI for your Robot
In both ROS By Example and in previous tutorials, we have seen that it is relatively straightforward to program a robot to execute a particular behavior such as face tracking, navigating between locations, or following a person. But a fully autonomous robot will be expected to select its own actions from a larger repertoire of behaviors depending upon the task at hand and the current conditions.
There are a number of ways to program a so-called task controller for robots. Traditionally, most task controllers make use of hierarchical finite state machines. This approach is available in ROS via the SMACH package which has been used extensively with the PR2 to manage tasks as complex as having the robot plug itself into a standard wall outlet as shown below:
While it is fairly straightforward to program state machines like this, they can become rather complex and difficult to follow as the image above illustrates.
Introducing Behavior Trees
A relatively new approach to task management comes from the computer game industry. Perhaps not surprisingly, programming an animated character in a game to behave in a realistic manner is not unlike programming a robot to carry out a series of tasks. Both must handle a set of unpredictable inputs and choose from a variety of behaviors appropriate to the task at hand as well as the current situation.
In the early days of game programming, developers tended to use hierarchical state machines similar to SMACH. The main difficulty with state machines is the wiring of all the transitions between states. Adding a new state or behavior to a character requires not only coding the new state itself but also adding the transitions between all related states. Before long, the state diagram of the game begins to look like tangled spaghetti similar to the diagram shown above.
In recent years, a method using behavior trees has become increasing popular among game developers as a simple yet powerful method for programming character behaviors. Although behavior trees are superficially similar to hierarchical state machines, the strict tree structure makes them especially easy to program and understand even in very complex games. The image below shows a tree designed to control a house cleaning robot's behavior.
As the name implies, a behavior tree consists of behaviors linked together in the form of a tree beginning with a single root node (labeled "BEHAVE" above). Behaviors higher in the tree are more abstract such as "clean house" while those at lower levels are more specific such as "mop floor". The breadth of the tree toward the top reflects the number of general behaviors available to the robot while the depth of any branch is an indication of the complexity of that behavior.
The most important distinction between behavior trees and hierarchical state machines is that there can never be direct links between behaviors on the same level of a tree: any connection between such "sibling" behaviors can only be indirect by virtue of shared links to higher-level behaviors. For example, in a state machine version of the house cleaning robot, the tasks "mop floor" and "scrub tub" in the Bathroom state machine connect directly together via transitions such as "when the floor is clean, start scrubbing the tub". This kind of lateral connection can never occur in a tree. In this way, behavior trees force a kind of overall structure on the task controller than helps prevent a runaway criss-crossing of links between behaviors. It also means that individual behaviors can be treated as independent modules and can be moved around the tree without having to worry about breaking lateral connections with other behaviors.
What's in a Tree?
Before learning about behavior trees in particular, let's quickly review the terminology used when working with trees in general.
A tree is a special type of graph or network consisting of nodes connected by links. Trees are both directed and acyclic. By directed we mean that we always follow the links from top to bottom in the tree beginning with the root node. By acyclic we mean that the tree does not contain any loops. This means that all nodes in a tree descend from the root node.
A parent node has nodes connected immediately beneath it which in turn are referred to as the parent's child nodes. Child nodes that share a parent are referred to as siblings. Note that siblings are never linked together directly—only indirectly through their common parent. A node without any children is called a leaf node. All other non-leaf nodes are called interior nodes. It is easy to see from the definition that each node in a tree has only one parent.
A node can be both a child node and a parent node (e.g. node 2 above). In fact, every node can be considered to be the root node of the subtree beneath it. (The subtree of a leaf node is the empty tree.) So a tree is a collection of smaller trees making it a recursive data structure consisting of a single type of object that refers to itself. The repeating object in a tree is a node together with its list of child nodes. By starting at the root node, we can trace out the entire tree simply by repeatedly following links from parent to child.
Planners, Decision Makers and Problem Solvers
Even outside of robotics or computer games, trees are often used for making decisions, planning actions, or searching for a solution to a problem. Each node in the tree can represent one or more conditions which then determines which branch to follow next. These branches can represent a possible action, plan or solution depending on what the nodes represent.
Starting at the root node of a tree, one can search through or "visit" all other nodes by simply tracing the links from parent to child until reaching a leaf node. To guarantee that every node is visited exactly once, two common search algorithms are used: depth-first and breadth-first. Behavior trees use depth-first search: as soon a node indicates that it is OK to follow its sub-tree, that tree is explored downward until a problem occurs or a leaf node is reached. If execution is blocked at a particular node in the subtree, we back track up the tree and move laterally until a new subtree can be executed.
Key Properties of Behavior Trees
The key features of behavior trees can be summarized as follows:
- Nodes represent tasks or conditions. The terms "task" and "behavior" will be used interchangeably and as will see later on, checking conditions can be considered a form of behavior as well. When talking about the tree structure itself, we can also use the more generic term "node". What you will not hear is the term "state" which is generally reserved for traditional finite state machines.
- The execution of a task produces one of three possible results: SUCCESS, FAILURE, or RUNNING. A status of RUNNING stays in effect until the node completes its processing at which point it returns either SUCCESS or FAILURE. In any case, a node's status is always passed up to its parent node.
- Nodes can also represent composite behaviors whose status depends on two or more child behaviors. The two most commonly used composite behaviors are selectors and sequences. A selector node executes each of its child behaviors in turn until one of them succeeds or it runs out of subtasks. A sequence node runs each of its child tasks in turn until one of them fails or it reaches the last subtask. Using Python, we can write these two behaviors as follows:
class Selector(Task):
"""
A selector runs each task in order until one succeeds,
at which point it returns SUCCESS. If all tasks fail, a FAILURE
status is returned. If a subtask is still RUNNING, then a RUNNING
status is returned and processing continues until either SUCCESS
or FAILURE is returned from the subtask.
"""
def __init__(self, name, *args, **kwargs):
super(Selector, self).__init__(name, *args, **kwargs)
def run(self):
for c in self.children:
status = c.run()
if status != TaskStatus.FAILURE:
return status
return TaskStatus.FAILURE
class Sequence(Task):
"""
A sequence runs each task in order until one fails,
at which point it returns FAILURE. If all tasks succeed, a SUCCESS
status is returned. If a subtask is still RUNNING, then a RUNNING
status is returned and processing continues until either SUCCESS
or FAILURE is returned from the subtask.
"""
def __init__(self, name, *args, **kwargs):
super(Sequence, self).__init__(name, *args, **kwargs)
def run(self):
for c in self.children:
status = c.run()
if status != TaskStatus.SUCCESS:
return status
return TaskStatus.SUCCESS
- Behaviors can be augmented with decorators which modify the results of other behaviors. For example, we might want to execute a sequence of subtasks but ignore failures so that the sequence continues through to the end even when individual subtasks do not succeed. For this we could use an "ignore failure" decorator that turns a result of FAILURE into a SUCCESS for the task it decorates. We will see an example of this in the next section.
-
When a task has more than one subtask, the subtasks are prioritized based on their list order; i.e. from left to right in a standard tree diagram. This property works as a kind of built-in subsumption architecture with no additional coding necessary.
- The connections between behaviors are always parent-to-child and never sibling-to-sibling. This follows directly from the structure of a tree and it allows us to move a node, or even a whole subtree, from one part of the tree and attach it somewhere else without changing any other connections. Such alterations can even be done at run time.
- The execution of a behavior tree always begins at the root node and proceeds in depth-first order beginning with the left most branch. When a given node is run, the result (SUCCESS, FAILURE or RUNNING) is passed up to its parent which then takes on the same status. Only leaf nodes result directly in the production of a behavior or the checking of a condition. Interior nodes are used to direct the flow of processing to their child nodes using selectors and sequences. An important property of behavior trees is that execution begins again at the root of the tree on every "tick" of the clock. This ensures that any change in the status of higher priority behaviors will result in the appropriate change in execution flow even if other nodes are already running.
For a nice series of diagram of this process, see the illustration on this blog entry by Bjoern Knafla
The easiest way to understand the execution of behavior trees is to dive into a couple of examples.
A Patrol Bot Example
A Patrol Bot needs to visit a series of waypoints while monitoring its battery level and recharging when necessary. Let's see how we can implement this scenario using behavior trees.
The nodes in our behavior tree will represent tasks and conditions. A task can be something relatively abstract like "patrol" or more specific like "navigate to waypoint 1". A condition could be "the battery is running low" or "there is an obstacle in the way". Conditions are really just a kind of task in disguise since the process of assessing the condition can be considered to be a task in itself. For example, the condition "the battery is running low" can be turned into the task "check battery". For this reason, we will be able to use the same programming machinery for both tasks and conditions.
Representing a "Running" Task Status
In general, tasks in a behavior tree either succeed or fail. However, for a task that might take some time to complete, we assign an intermediate status of RUNNING. This status is passed to the parent task to indicate that it too is still running. When a task is running, we don't yet know if it will ultimately succeed or fail. For this reason, we must set the status of all parent nodes to RUNNING as well so they can await the final result.
Child Tasks, Conditions and Priorities
We will build our behavior tree from the top down beginning with the root node. For our patrol bot example, the root node will have two child behaviors or subtasks: STAY_HEALTHY and PATROL. The STAY_HEATHY behavior will include checking the battery level. It could also include checking servos for overheating, watching for excessive current to the drive motors (perhaps the robot is stuck on something) or keeping an eye out for mischievous house pets. The PATROL behavior will of course move our robot from one waypoint to the next.
Using a bulleted list, we can represent our tree so far like this:
where we have used the label BEHAVE for the root node.
Note that the priority of a child behavior is determined by its order in the list since we will always run through the child nodes in list order. So in this case, the STAY_HEALTHY behavior has a higher priority than the PATROL behavior. After all, if we let the battery run down, the robot will not be able to continue its patrol.
Next, let's flesh out these two high level behaviors. The STAY_HEALTHY task will consist of two sub-tasks: CHECK_BATTERY and RECHARGE. And the PATROL task will navigate to four waypoints in succession. So the behavior tree now looks like this:
Once again, order in a list is important. For example, we want to check the battery before we decide to recharge, and we want to visit the waypoint locations in a particular order.
Finally, the RECHARGE task consists of navigating to the docking station and charging the robot yielding the tree:
With our basic tree structure in place, all that is left is to describe the connections between layers in the tree; i.e. between parent tasks and their child tasks. Let's turn to that next.
Selectors and Sequences
As we learned earlier, behavior trees use two basic types of composite behaviors: selectors and sequences. A selector tries each of its subtasks in turn until one succeeds whereas a sequence executes each of its child behaviors until one of them fails. So selectors and sequences essentially complement one another. Surprisingly, these two simple types of parent-child relationships are almost all we need to generate very complex robot behaviors. To see how, let's look at them in more detail.
A selector starts by executing the first task among its child nodes and, if the task succeeds, the selector's status is also set to SUCCESS and all other child tasks are ignored. However, if the first subtask fails, the selector's status is also set to FAILURE and the next subtask in its list is executed. In this way, the selector picks a single behavior from its collection of child behaviors, always moving in list order; i.e. from left to right if referring to a tree diagram. We can therefore think of a selector as a kind of simple "problem solver". Beginning with its highest priority sub-behavior, it tries each "solution" until one succeeds or until it runs out of behaviors, in which case it passes a final FAILURE result up to its parent which is then left to deal with the situation. (More on that later.)
The STAY_HEALTHY behavior in our example is a relatively simple selector. First we run the CHECK_BATTERY task and if it returns SUCCESS (the battery is OK), we pass this result to the parent task and and ignore the RECHARGE task. If however the CHECK_BATTERY task returns FAILURE (the battery level is low), we move on to the RECHARGE task which attempts to remedy the problem by navigating to the docking station and charging the robot. One could also add a NOTIFY behavior so that if the RECHARGE task fails, the robot could call for help using text-to-speech or alert a human via email.
A sequence also starts with the first behavior in its list of subtasks but this time, if the task succeeds, the next subtask in the list is executed. The process continues until either a subtasks fails or we run out of subtasks. If the entire sequence is completed, a status of SUCCESS is passed to the parent task. However, if the sequence is cut short because a subtask fails, then FAILURE is returned up the tree.
Should we use a sequence or a selector for the PATROL task? Suppose we use a sequence. We begin with the NAV_0 task and if the robot makes it to the first waypoint (SUCCESS), execution continues with the NAV_1 subtask. However, if NAV_0 fails, the PATROL task also fails and we return to the root node (BEHAVE) looking for alternatives. In this case, there are no other branches in the tree besides the STAY_HEALTHY branch so the patrol simply ends. We would probably prefer that the robot continue on to the next waypoint rather than simply stop. What happens if we use a selector instead? In that case, execution again begins with NAV_0 but this time if NAV_0 succeeds, the PATROL task terminates with a status of SUCCESS which again is not what we want.
So it appears that neither a sequence nor a selector will do the PATROL task exactly as we would like. Fortunately, behavior trees can get around this problem by using another class of behavior called a decorator which is the subject of the next section.
Customizing Behaviors using Decorators (Meta-Behaviors)
As we have just seen, selectors and sequences are not always enough to produce the behavior we need from our robot. There are a number of ways to add greater flexibility to behavior trees including the use of decorator patterns and metaclasses. We will use the simpler terms "decorator" and "meta-behavior" interchangeably to refer to a behavior or task whose only function is to modify the result of another behavior or task. In other words, a decorator task "decorates" another task.
For our first example, consider the IgnoreFailure meta-behavior which simply returns SUCCESS from its child behavior(s) even if the original result is FAILURE. Here's what it looks like in Python:
class IgnoreFailure(Task):
"""
Always return either RUNNING or SUCCESS.
"""
def __init__(self, name, *args, **kwargs):
super(IgnoreFailure, self).__init__(name, *args, **kwargs)
def run(self):
for c in self.children:
if c.run() != TaskStatus.RUNNING:
return TaskStatus.SUCCESS
else:
return TaskStatus.RUNNING
return TaskStatus.SUCCESS
The IgnoreFailure decorator is just what we need to make our patrol sequence work the way we want by using it to wrap each waypoint NAV task. Our behavior tree now looks like this:
-
BEHAVE
-
STAY_HEALTHY
- CHECK BATTERY
-
RECHARGE
-
PATROL
-
IGNORE_FAILURE
-
IGNORE_FAILURE
-
IGNORE_FAILURE
-
IGNORE_FAILURE
Another commonly used meta-behavior is the Loop decorator which takes a single parameter specifying the number of iterations and executes its child behavior that number of times before terminating. We could use a Loop decorator around our PATROL behavior to limit the number of patrols to a specified number.
There is nothing stopping you from creating any number of meta-behaviors for use in your behavior tree. Note also that decorators can be defined as functions on behaviors rather than meta-classes as we have done here.
How Behavior Trees are like Problem Solvers
Now that we have the PATROL behavior under control, let's return to the execution of the tree from the top. A key feature of behavior trees is that the success or failure of a task is passed back up the tree to its parent. Recall that the root node of our tree (BEHAVE) is a sequence so that on every pass through the tree we begin by checking in with the highest priority node STAY_HEALTHY. The STAY_HEALTHY node is a selector and begins by executing its highest priority node which is the CHECK_BATTERY task. Let's suppose that the CHECK_BATTERY task returns FAILURE (the battery level is low).
This result is passed up to the STAY_HEALTH selector which takes on the same status of FAILURE and passes it up to its parent, the BEHAVE sequence. Remember that a sequence will not move on to the next child behavior if the previous child failed. In this case, the next child behavior is the PATROL task so on this iteration of the tree, the entire PATROL branch is skipped which is what we want if the battery is low.
On the other hand, the STAY_HEALTY node is a selector which responds to failure by moving on to the next child behavior in its list which is the RECHARGE behavior. The RECHARGE node is a sequence and so begins with its highest priority node NAV_DOCK since we must first get to the docking station before we can actually recharge the robot. While the robot is moving toward the docking station, the status of the NAV_DOCK task is RUNNING which is passed up to the RECHARGE node and from there to the STAY_HEALTHY node and the BEHAVE node. As long as these nodes are all running, the tree is in a kind of "wait-and-see" mode to see what happens next.
If the NAV_DOCK task is successful, then the RECHARGE sequence can move on to its next child task which is to CHARGE the robot. If the robot is recharged successfully, the CHARGE task returns SUCCESS to the RECHARGE sequence which has now reached the end of its list of child nodes and therefore terminates and returns SUCCESS to the STAY_HEALTH selector. The STAY_HEATHY selector is now happy since at least one of its children succeeded so it returns SUCCESS to the BEHAVE sequence which in turn allows the BEHAVE sequence to move on to its next child behavior, PATROL.
Suppose however, that the NAV_DOCK task fails. Perhaps the robot runs down the battery before it gets there or maybe the docking station is inaccessible. Then the RECHARGE sequence also fails and this is passed up to the STAY_HEALTHY selector. Since the RECHARGE task was the last child behavior in the STAY_HEALTHY's list of behaviors, it passes FAILURE to the BEHAVE node which, being a sequence, will not advance to the PATROL task in its list. However, the tree continues to execute on every tick of the clock in the hopes that something in the world will change and the robot will still get to the docking station.
Dynamically Adding and Removing Tasks
One of the more interesting features of behavior trees is the ability to add or remove nodes or even whole subtrees at run time. For example, suppose that one of the waypoints on the robot's patrol route will be inaccessible for some period of time. Then rather than have the robot continually try (and fail) to get to that location every time it patrols its route, we can simply remove the corresponding NAV task from the tree. This can be done either by literally removing the node or by wrapping it in a decorator that returns FAILURE right away so that navigation to the target does not even start.
Even more interesting is that the robot could learn to make these modifications on its own. For example, suppose we enter a rule into our script that if a waypoint is inaccessible two times in a row, then we skip that waypoint for two loops around the patrol route before trying again.
Looking Ahead
I am currently working on a behavior tree library written in Python that will be used with ROS to manage robot task trees. So far the results are very encouraging. The code will be released as a ROS package when complete and a full explanation will appear in Volume 2 of ROS By Example when it is published.
|
|
