Behavior Trees

A behavior tree arranges behavior as a tree that is "ticked" from the root many times per second. Each node returns success, failure, or running. A sequence runs its children in order until one fails. A fallback tries its children in order until one succeeds. Because each subtree is self-contained, trees are easy to extend.

Battery is OK An object is visible Holding an object The grasp will work

The node types

A sequence (→) ticks its children left to right and returns failure as soon as one fails, success only if all succeed. A fallback (?) ticks its children left to right and returns success as soon as one succeeds. Conditions check something and return success or failure at once. Actions do something and may return running while they work:

$$\text{Sequence}(c_1, \dots, c_n) = c_1 \wedge c_2 \wedge \dots \qquad \text{Fallback}(c_1, \dots, c_n) = c_1 \vee c_2 \vee \dots$$

What to notice

Turn the battery off and the whole top branch fails at its first condition, so the root falls back to "go charge". Make an object visible and the robot switches from exploring to picking. Turn off "the grasp will work" and picking fails, so the fallback above it moves on to exploring again. To add a behavior, you add a subtree without rewiring the rest, which is why Nav2, many game engines, and many robot frameworks use behavior trees.