selector

This is the second part of the tutorial on Behavior Trees for games and robotics.

Fast links for other parts and tutorials:

If you’re looking for actual code to use, check it out:


The Behavior Tree (BT) was born in the game industry and was quickly adopted and adapted by game developers around the world. However, the formalism required by the academy was developed later, mainly because its use in robotics. The lack of documentation and formalism, in conjunction with the fast adaptation of the BT, resulted in inconsistencies (of names, structure and definition) among papers and tutorials, for both robotics and games. We follow the definition of (Marzinotto, 2014)  and (Ogren, 2012) to describe how a Behavior Tree is structured and how it works.

As discussed in the previous post, Behavior Trees provide some improvements over the Finite State Machines, having some advantages such as:

  • maintainability: transitions in BT are defined by the structure, not by conditions inside the states. Because of this, nodes can be designed independent from each other, thus, when adding or removing new nodes (or even subtrees) in a small part of the tree, it is not necessary to change other parts of the model.
  • scalability: when a BT have many nodes, it can be decomposed into small subtrees saving the readability of the graphical model.
  • reusability: due to the independence of nodes in BT, the subtrees are also independent. This allows the reuse of nodes or subtrees among other trees or projects.
  • goal-oriented: although the nodes of BT are independent, they are still related due to the tree structure of the model. This allows the designer to build specific sub-trees for a given goal without losing  flexibility of the model.
  • parallelization: BT can specify parallel nodes which run all children at the same time without losing the control of the model execution. This is possible because the parallelization is locally contained to the parallel node.

Despite the name, the Behavior Tree is actually defined as a directed acyclic graph, because a node can have many parents. This structure may not be found in some papers but it have some advantages in the reusability and performance. The multi-parenting will be discussed in the part 3 of this post.

The model is composed of nodes and edges. For a pair of nodes connected by an edge, the outgoing node is called the parent and the incoming node is the child. There is no limit of how much children a node can have. The child-less nodes are called leaves while the parent-less node is called root; the nodes that stand between the root and the leaves can be of two types, composite or decorator nodes. Each subtree defines a different behavior, which can be simple ones (composed of few nodes) or complex behaviors (composed of a large number of modes).

The root of the BT generates a signal (called tick) periodically following a frequency f. The tick is propagated through the tree branches according to the algorithm defined by each node type. When the tick reaches a leaf, the node perform some computation and return a state value SUCCESS, FAILURE, RUNNING or ERROR). Then the returned value is propagated back through the tree according to each node type. The process is completed when a state value is returned to the root. Notice that, the tick frequency of the tree is independent of the control loop frequency of the
agent.

Node Types

The nodes types are divided into 3 categories: composite, decorator or leaf, which are described in detail below. In the nodes description, I present a graphicall example of how to use a node in a real situation and I also present their algorithms. The algorithms may use the Tick function in the statement Tick(child[i]), which triggers the algorithm corresponding to the i-th child node.

Leaf Nodes

The leaf nodes are the primitive building blocks of the behavior tree. These nodes do not have any child, thus, they do not propagate the tick signal, instead, they perform some computation and return a state value. There are two types of leaf nodes (conditions and actions) and are categorized by their responsibility.

Conditions

A condition node checks whether a certain condition has been met or not. In order to accomplish this, the node must have a target variable (e.g.: a perception information such as “obstacle distance'” or “other agent visibility”; or an internal variable such as “battery level” or “hungry level”; etc.) and a criteria to base the decision (e.g.: “obstacle distance > 100m?” or “battery power < 10%?”). These nodes return SUCCESS if the condition has been met and FAILURE otherwise. Notice that, conditions do not return RUNNING nor change values of system. Graphically, condition nodes are presented by gray ellipsis, as shown in the image below.

 node_condition

Actions

Action nodes perform computations to change the agent state. The actions implementation depends on the agent type, e.g., the actions of a robot may involve sending motor signals, sending sounds through speakers or turning on lights, while the actions of a NPC may involve executing animations, performing spacial transformations, playing a sound, etc.

Notice that action may not be only external (i.e, actions that changes the environment as result of changes on the agent), they can be internal too, e.g., registering logs, saving files, changing internal variables, etc.

An action returns SUCCESS if it could be completed; returns FAILURE if, for any reason, it could not be finished; or returns RUNNING while executing the action. The action node is represented as a gray box, as shown in the figure below, which presents 4 different example actions.

node_action

Composite Nodes

A composite node can have one or more children. The node is responsible to propagate the tick signal to its children, respecting some order. A composite node also must decide which and when to return the state values of its children, when the value is SUCCESS or FAILURE. Notice that, when a child returns RUNNING or ERROR, the composite node must return the state immediately. All composite nodes are represented graphically as a white box with a certain symbol inside.

Priority

The priority node (sometimes called selector) ticks its children sequentially until one of them returns SUCCESS, RUNNING or ERROR. If all children return the failure state, the priority also returns FAILURE.

For instance, suppose that a cleaning robot have a behavior to turn itself off, as shown in the figure below. When the robot try to turn itself off, the first action is performed and the robot try to get back to its charging dock and turn off all its systems, but if this action fail for some reason (e.g., it could not find the dock) an emergency shutdown will be performed.

node_selector

for i = 1 to N:
    state = Tick(child[i])

    if state != FAILURE:
        return state

return FAILURE

 Sequence

The sequence node ticks its children sequentially until one of them returns FAILURE, RUNNING or ERROR. If all children return the success state, the sequence also returns SUCCESS.

The figure below presents an example of the sequence node in a behavior that can be part of a real unmanned aerial vehicle (UAV) or a jet plane in a war game. In this behavior, the agent first verify if there is a missile following it, if it is true, the agent fires flares and then performs an evasive maneuver. Notice that, if there is no missile, there is not reason to fire flares nor to perform an evasive maneuver.

node_sequence

for i = 1 to N:
    state = Tick(child[i])

    if state != SUCCESS:
        return state

return SUCCESS

 Parallel

The parallel node ticks all children at the same time, allowing them to work in parallel. This node is a way to use concurrency in Behavior Trees. Notice that, using this node, the parallelization is contained locally, avoiding losing control of the execution flow as happens on the FSM.

Parallel nodes return SUCCESS if the number of succeeding children is larger than a local constant S (this constant may be different for each parallel node); return FAILURE if the number of failing children is larger than a local constant F; or return RUNNING otherwise.

As an example of use of a parallel node, consider an agent that is an intelligent house (real or virtual). The house have a behavior to turn the lights on and play music when it identifies that a human just entered the room.

node_parallel

for i = 1 to N:
    state_i = Tick(child[i])

if nSucc(state) >= S:
    return SUCCESS
else if nFail(state) >= F:
    return FAILURE
else
    return RUNNING

Decorator Nodes

Decorators are special nodes that can have only a single child. The goal of the decorator is to change the behavior of the child by manipulating the returning value or changing its ticking frequency. For example, a decorator may invert the result state of its child, similar to the NOT operator, or it can repeat the execution of the child for a predefined number of times. The figure below shows an example of the decorator “Repeat 3x”, which will execute the action “ring bell” three times before returning a state value.

node_decorator

There is no default algorithm for decorators, it depends on their purpose. Next post I will present some common decorators used in games.

State Values

Following the definition proposed in (Champanard, 2012), we consider four different values for the node states:

  • SUCCESS: returned when a criterion has been met by a condition node or an action node has been completed successfully;
  • FAILURE: returned when a criterion has not been met by a condition node or an action node could not finish its execution for any reason;
  • RUNNING: returned when an action node has been initialized but is still waiting the its resolution.
  • ERROR: returned when some unexpected error happened in the tree, probably by a programming error (trying to verify an undefined variable). Its use depends on the final implementation of the leaf nodes.

 

Read more