Behavior tree (artificial intelligence, robotics and control)

A control flow node is used to control the subtasks of which it is composed. A control flow node may be either a selector (fallback) node or a sequence node. They run each of their subtasks in turn. When a subtask is completed and returns its status (success or failure), the control flow node decides whether to execute the next subtask or not.

Figure I. Graphical representation of a fallback composition of N tasks.

Fallback nodes are used to find and execute the first child that does not fail. A fallback node will return immediately with a status code of success or running when one of its children returns success or running (see Figure I and the pseudocode below). The children are ticked in order of importance, from left to right.

In pseudocode, the algorithm for a fallback composition is:

1 for i from 1 to n do
2     childstatus ← Tick(child(i))
3     if childstatus = running
4         return running
5     else if childstatus = success
6         return success
7 end
8 return failure

Figure II. Graphical representation of a sequence composition of N tasks.

Sequence nodes are used to find and execute the first child that has not yet succeeded. A sequence node will return immediately with a status code of failure or running when one of its children returns failure or running (see Figure II and the pseudocode below). The children are ticked in order, from left to right.

In pseudocode, the algorithm for a sequence composition is:

1 for i from 1 to n do
2     childstatus ← Tick(child(i))
3     if childstatus = running
4         return running
5     else if childstatus = failure
6         return failure
7 end
8 return success

The execution of a behavior tree is described by the following standard ordinary difference equations:

${\displaystyle x_{k+t}(t_{k+1})=f_{i}(x_{k}(t_{k}))}$

${\displaystyle t_{k+1}=t_{k}+\Delta t}$

where ${\displaystyle k\in \mathbb {N} }$ represent the discrete time, and ${\displaystyle x\in \mathbb {R} ^{n}}$ is the state space of the system modelled by the behavior tree.

Two behavior trees ${\displaystyle T_{i}}$ and ${\displaystyle T_{j}}$ can be composed into a more complex behavior tree ${\displaystyle T_{0}}$ using a Sequence operator.

${\displaystyle T_{0}={\mbox{sequence}}(T_{i},T_{j}).}$

Then return status ${\displaystyle r_{0}}$ and the vector field ${\displaystyle f_{0}}$ associated with ${\displaystyle T_{0}}$ are defined (for ${\displaystyle {\mathcal {S}}_{1}}$) as follows:

${\displaystyle r_{0}(x_{k})={\begin{cases}r_{j}(x_{k})&{\text{ if }}x_{k}\in {\mathcal {S}}_{1}\\r_{i}(x_{k})&{\text{ otherwise }}.\end{cases}}}$

${\displaystyle f_{0}(x_{k})={\begin{cases}f_{j}(x_{k})&{\text{ if }}x_{k}\in {\mathcal {S}}_{1}\\f_{i}(x_{k})&{\text{ otherwise }}.\end{cases}}}$