*** Welcome to piglix ***

Behavior tree (artificial intelligence, robotics and control)



A behavior tree (BT) is a mathematical model of plan execution used in computer science, robotics, control systems and video games. They describe switchings between a finite set of tasks in a modular fashion. Their strength comes from their ability to create very complex tasks composed of simple tasks, without worrying how the simple tasks are implemented. BTs present some similarities to hierarchical state machines with the key difference that the main building block of a behavior is a task rather than a state. Its ease of human understanding make BTs less error prone and very popular in the game developer community. BTs have shown to generalize several other control architectures.

BTs originates from the computer game industry as a powerful tool to model the behavior of non-player characters (NPCs). They have been extensively used in high profile video games such as Halo, Bioshock, and Spore. Recent works propose BTs as a multi-mission control framework for UAV, complex robots, robotic manipulation, and multi-robot systems. BT have now reached the maturity to be treated in Game AI textbooks as well as generic game environments such as PyGame and Unreal Engine (see links below).

It has been shown that BTs generalize a number of earlier control architectures, such as

BT is graphically represented as a directed tree in which the nodes are classified as root, control flow nodes, or execution nodes (tasks). For each pair of connected nodes the outgoing node is called parent and the incoming node is called child. The root has no parents and exactly one child, the control flow nodes have one parent and at least one child, and the execution nodes have one parent and no children. Graphically, the children of a control flow node are placed below it, ordered from left to right.


...
Wikipedia

...