Behavior Tree

A tree-structured way of organizing actions and conditions to decide what a robot should do next.

A behavior tree is a way of organizing how a robot or game character switches among multiple tasks. It first became popular in the game industry (Damian Isla's 2005 GDC talk on Halo 2's AI is often credited with popularizing it) before spreading into robotics. A root node periodically sends a 'tick' signal down the tree, and each node returns success, failure, or running. Leaves are action nodes (such as 'grab the cup') and condition nodes (such as 'is the cup in view'); a sequence node runs its children left to right and fails as soon as one fails; a fallback (selector) node tries its children left to right and succeeds as soon as one succeeds, which is well suited to writing 'try A first, and if that fails, do B as a fallback.' Compared with a finite state machine, it doesn't require writing a transition for every pair of states, and adding or removing subtrees is easier. ROS 2's Nav2 navigation framework uses a behavior tree to orchestrate navigation and recovery actions, commonly implemented with the C++ library BehaviorTree.CPP.

ExampleA water-delivery robot's root node is a sequence: 'navigate to the table' → 'detect the cup' → a fallback node (try 'grab the cup,' and if that fails, 'reposition and retry the grab') → 'hand it to the user.' If some step returns running, the next tick simply continues that same step.

Also called

BT, Behaviour Tree

Related

Finite State Machine · BehaviorTree.CPP · ROS 2 Navigation Stack (Nav2) · Task Planning · Skill Primitive · Failure Recovery

Sources

Wikipedia: Behavior tree (artificial intelligence, robotics and control)
Colledanchise & Ögren, Behavior Trees in Robotics and AI: An Introduction (arXiv 1709.00084)
ros-navigation/navigation2 README