Introduction to BTs

Unlike a Finite State Machine, a behavior Tree is a tree of hierarchical nodes that controls the flow of execution of "tasks".

Basic Concepts

• A signal called "tick" is sent to the root of the tree and propagates through the tree until it reaches a leaf node.

• Any TreeNode that receives a tick signal executes its callback. This callback must return either

  • SUCCESS
  • FAILURE
  • RUNNING

• RUNNING means that the action needs more time to return a valid result.

• If a TreeNode has one or more children, it is its responsibility to propagate the tick; each Node type may have different rules about if, when, and how many times children are ticked.

• The LeafNodes, those TreeNodes which don't have any children, are the actual commands, i.e. the Nodes where the behavior tree interacts with the rest of the system. Action nodes are the most common type of LeafNodes.

tip

The word tick will be often used as a verb (to tick / to be ticked) and it means:

"To invoke the callback `tick()` of a `TreeNode`".

In a service-oriented architecture, the leaves would contain the "client" code that communicates with the "server", that performs the actual operation.

How tick works

To mentally visualize how ticking the tree works, consider the example below.

A Sequence is the simplest ControlNode: it executes its children one after the other and, if they all Succeed, it returns SUCCESS too.

1. The first tick sets the Sequence node to RUNNING (orange).
2. Sequence ticks the first child, "OpenDoor", that eventually returns SUCCESS.
3. As a result, the second child "Walk" and later "CloseDoor" are ticked.
4. Once the last child is completed, the entire Sequence switches from RUNNING to SUCCESS.

Types of nodes

Type of TreeNode	Children Count	Notes
ControlNode	1...N	Usually, ticks a child based on the result of its siblings or/and its own state.
DecoratorNode	1	Among other things, it may alter the result of its child or tick it multiple times.
ConditionNode	0	Should not alter the system. Shall not return RUNNING.
ActionNode	0	This is the Node that "does something"

In the context of ActionNodes, we may further distinguish between synchronous and asynchronous nodes.

The former are executed atomically and block the tree until a SUCCESS or FAILURE is returned.

Asynchronous actions, instead, may return RUNNING to communicate that the action is still being executed.

We need to tick them again, until SUCCESS or FAILURE is eventually returned.

Examples

To better understand how BehaviorTrees work, let's focus on some practical examples. For the sake of simplicity we will not take into account what happens when an action returns RUNNING.

We will assume that each Action is executed atomically and synchronously.

First ControlNode: Sequence

Let's illustrate how a BT works using the most basic and frequently used ControlNode: the SequenceNode.

The children of a ControlNode are always ordered; in the graphical representation, the order of execution is from left to right.

In short:

• If a child returns SUCCESS, tick the next one.
• If a child returns FAILURE, then no more children are ticked, and the Sequence returns FAILURE.
• If all the children return SUCCESS, then the Sequence returns SUCCESS too.

Find the BUG!

If the action GrabBeer fails, the door of the fridge will remain open since the last action CloseFridge is skipped.

Decorators

Depending on the type of DecoratorNode, the goal of this node could be either:

• to transform the result it received from the child.
• to halt the execution of the child.
• to repeat ticking the child, depending on the type of Decorator.

The node Inverter is a Decorator that inverts the result returned by its child; An Inverter followed by the node called isDoorOpen is, therefore, equivalent to

"Is the door closed?".

The node Retry will repeat ticking the child up to num_attempts times (5 in this case) if the child returns FAILURE.

Apparently, the branch on the left side means:

If the door is closed, then try to open it.
Try up to 5 times, otherwise give up and return FAILURE.

But...

Find the BUG!

If isDoorOpen returns FAILURE, we have the desired behavior. But if it returns SUCCESS, the left branch fails, and the entire Sequence is interrupted.

Second ControlNode: Fallback

FallbackNodes, also known as "Selectors", are nodes that can express, as the name suggests, fallback strategies, i.e. what to do next if a child returns FAILURE.

It ticks the children in order and:

• If a child returns FAILURE, tick the next one.
• If a child returns SUCCESS, then no more children are ticked and the Fallback returns SUCCESS.
• If all the children return FAILURE, then the Fallback returns FAILURE too.

In the next example, you can see how Sequences and Fallbacks can be combined:

Is the door open?

If not, try to open the door.

Otherwise, if you have a key, unlock and open the door.

Otherwise, smash the door.

If any of these actions succeeded, then enter the room.

"Fetch me a beer" revisited

We can now improve the "Fetch Me a Beer" example, which left the door open if the beer was not inside the fridge.

We use the color "green" to represent nodes which return SUCCESS and "red" for those which return FAILURE. Black nodes haven't been executed.

Let's create an alternative tree that closes the door even when GrabBeer returns FAILURE.

Both these trees will close the door of the fridge, eventually, but:

• the tree on the left side will always return SUCCESS, no matter if we have actually grabbed the beer.
• the tree on the right side would return SUCCESS if the beer was there, FAILURE otherwise.

Everything works as expected if GrabBeer returns SUCCESS.