Behavior Tree

A behavior tree is a directed tree that models decision-making as a hierarchy of tasks. Each node ticks (executes) and returns one of three states: success, failure, or running. The tree is evaluated from the root on every tick, and control flows through composite nodes that decide which children to run.

Originally developed for game AI (Halo 2 is the usual citation), behavior trees have spread to robotics, autonomous agents, and task automation wherever you need modular, composable decision logic that's easier to reason about than a state machine.

Node types

Composite nodes control the flow:

• Sequence — runs children left to right, stops on the first failure. Succeeds only if all children succeed. The AND gate of behavior trees.
• Selector (also called Fallback or Priority) — runs children left to right, stops on the first success. Fails only if all children fail. The OR gate.
• Parallel — runs all children simultaneously, with configurable success/failure thresholds.

Decorator nodes wrap a single child and modify its result:

• Inverter — flips success to failure and vice versa (NOT gate).
• Repeat — re-runs the child N times or until failure.
• Timeout — fails if the child doesn't complete within a time limit.
• Retry — re-runs a failed child up to N times.

Leaf nodes do the actual work:

• Action — executes a function, returns success or failure.
• Condition — checks a predicate against shared state (the blackboard), returns success or failure without side effects.

The blackboard

Nodes communicate through a shared data store called the blackboard. Actions write to it, conditions read from it. This avoids passing data through the tree structure and keeps nodes decoupled — a condition node doesn't need to know which action set the value it's checking.

Why not a state machine?

Finite state machines (FSMs) become unwieldy as complexity grows. Adding a new state requires considering transitions to and from every existing state — the number of transitions grows quadratically. Behavior trees are hierarchical: adding a new behavior means adding a subtree, and the composite nodes handle priority and fallback logic. Subtrees are also reusable across different trees.

The tradeoff is that behavior trees evaluate from the root every tick, which can be wasteful if most of the tree is irrelevant on a given tick. Event-driven behavior trees and reactive variants address this by only re-evaluating when relevant state changes.

The running state

The third return value — running — is what makes behavior trees work for tasks that span multiple ticks. A node returns running to say "I'm not done yet, come back next tick." The parent composite remembers which child was running (in a "memory" variant like MemSequence) and resumes from there on the next tick. Without this, every tick would restart from the beginning of the sequence.

Implementations

• go-bt — minimalist Go library with generic typed blackboard and time-travel testing
• Unreal Engine's built-in behavior tree editor (the most visible mainstream implementation)
• BehaviorTree.CPP — widely used in ROS2 robotics