Source-linked AI summary
A Survey of Behavior Trees in Robotics and AI
Matteo Iovino, Edvards Scukins, Jonathan Styrud, Petter Ögren, Christian Smith
TL;DR
This paper surveys Behavior Trees in AI and robotics, organizing the literature by methods and application areas. It analyzes 166 papers and identifies open research challenges, including limited application to autonomous driving.
Problem
Automatic Behavior Tree synthesis remains insufficiently mature to compete with manual design, especially for fairly small trees.
Method
The paper surveys Behavior Tree research and classifies the literature according to methods, topics, and application areas.
Results
166 papers remained after removing functional-requirements papers, dead links, and duplicates, and the survey analyzes them by topic and application area.
Takeaways & Limitations
The survey provides an overview of Behavior Tree research and identifies open challenges for the research community.
Takeaways & Limitations
Autonomous driving has not yet received extensive Behavior Tree applications; decision layers are usually based on FSMs or POMDPs.
Abstract
from arXiv · showhide
Behavior Trees (BTs) were invented as a tool to enable modular AI in computer games, but have received an increasing amount of attention in the robotics community in the last decade. With rising demands on agent AI complexity, game programmers found that the Finite State Machines (FSM) that they used scaled poorly and were difficult to extend, adapt and reuse. In BTs, the state transition logic is not dispersed across the individual states, but organized in a hierarchical tree structure, with the states as leaves. This has a significant effect on modularity, which in turn simplifies both synthesis and analysis by humans and algorithms alike. These advantages are needed not only in game AI design, but also in robotics, as is evident from the research being done. In this paper we present a comprehensive survey of the topic of BTs in Artificial Intelligence and Robotic applications. The existing literature is described and categorized based on methods, application areas and contributions, and the paper is concluded with a list of open research challenges.
1. Introduction
Behavior Trees organize task-switching logic hierarchically, with execution elements at the leaves and control flow in non-leaf nodes. This structure supports modular, reactive, and reusable agent policies and is surveyed here across AI and robotics.
- Core concept: A BT policy maps an agent’s state to actions, using action nodes for commands and condition nodes to analyze the world state.
- Control flow: Sequences execute dependent tasks in order, while Fallbacks select alternative ways to achieve a similar goal.
- Control flow: Reactivity allows more important tasks to interrupt less important ones, while common node interfaces return success, failure, or running.
- Core concept: BTs encode task-switching logic in hierarchical non-leaf nodes, while basic actions and conditions occupy the leaves.
- Motivation and scope: BTs were developed in game programming as an alternative to difficult-to-extend FSM-based AI and later attracted substantial robotics research.
- Motivation and scope: The survey searches three scholarly databases, retains 166 papers after filtering, and classifies them by topic and application area.
2. Fundamental theory
The survey traces BT theory from its relationship to FSMs and core control-flow semantics toward extensions for reactivity, probabilistic analysis, planning, and formal guarantees.
- Reactivity: Modern BT reactivity combines recurrent root ticks with the Running status to reevaluate conditions and interrupt actions when external events require switching.Stopping an action before completion enables urgent behaviors to replace less urgent ones.
- BT foundations: BTs organize task-switching logic hierarchically, unlike FSMs’ dispersed transitions, making subtrees easier to debug, update, and extend.FSMs can represent equivalent overall behavior, but their n^2 possible transitions can form a complex monolithic structure.
- Control-flow extensions: BT research extends static Fallback priorities using utility scores or data-driven success probabilities to reorder alternatives according to the situation.Utility values may be aggregated from children, while probability-based ordering uses observed leaf success and failure outcomes.
- Probabilistic analysis: Stochastic BT analysis aggregates subtree success, failure, and execution-time estimates, with later work extending this to Hidden Markov models.These analyses move from leaf statistics toward quantitative predictions for entire subtrees.
- Control-flow extensions: Sequence nodes advance only after child success, while reactive reevaluation can require memory or decorators when completed actions leave no persistent trace.Waypoint following motivates a memoryful Sequence or a decorator that continues returning Success without ticking its child.
- Formal analysis: Formal state-space methods analyze robustness, safety, and efficiency, and can preserve some guarantees even when a learning subtree performs unreliably.Related work also proves convergence and stochastic convergence-time properties for sequences under bounded external state transitions.
3. Applications
The survey reviews BT applications across different areas and summarizes how BTs have been used in those domains.
- Applications: The applications section organizes examples by application area and gives a short overview of BT usage in each area.The paper refers readers to Figure 1 for the application-area overview.
3.1. Game AI and Chatbots
BTs originated in dialogue-game AI and became a tool for game characters across genres, while research also explores learning, reuse, and robot-oriented applications.
- Game AI and chatbots: BTs were first created for dialogue-game AI and are now used to develop non-player-character AI in genres ranging from strategy games to shooters.The survey presents dialogue games as the origin and broader game AI as a later application area.
- Real-time strategy games: RTS applications use BTs for tactical decisions across units, squads, platoons, and armies, with evolutionary methods generating trees for strategy games.Examples include BTs evaluated against hand-coded DEFCON AI and approaches for turn-based strategy games.
- Real-time strategy games: StarCraft research used ABL for reactive planning and proposed a human-level agent, illustrating BT-related work in complex RTS environments.The passage identifies StarCraft as a demonstration setting for reactive planning.
- First-person shooters: FPS research applies BTs to highly dynamic combat involving many NPCs and studies extensions incorporating time, risk, emotions, and demonstrations from human gameplay.Other work addresses reuse as an agent’s available actions grow by querying categorized actions and selecting among goal-specific BTs.
- Platform games: Platform-game studies use Mario AI to test evolutionary BT learning, while Pac-Man supports Monte Carlo Tree Search, hybrid evolution, and manual BT-design tools.These examples cover both automated learning and tools intended to support human construction of BTs.
- Game AI and chatbots: Dialogue-game research extends beyond the original application to waiter interactions, human-robot interaction, interactive narratives, negotiations, and question-answering.The cited examples include virtual teddy bears asking players to retrieve a ball and buyer-seller conversations.
3.2. Robotics
BT research in robotics spans manipulators, mobile ground robots, aerial and underwater robots, and swarm systems. Across these applications, authors emphasize modularity, reactivity, transparency, automated synthesis, and evolutionary design.
- Robotics: BTs entered robotics independently in 2012 through work on object grasping, dexterous manipulation, and UAV control.The survey organizes robotic applications into manipulators, mobile ground robots, and aerial and underwater robots.
- Manipulation: Robotic manipulation studies use BTs for grasping, transport, assembly, kitting, and mobile manipulation across simulated and real platforms.Implementations include manually constructed trees and trees synthesized with LTL, STRIPS, PDDL, and A*-like planners.
- Mobile Ground Robots: BTs support reactive and fault-aware control for mobile robots, including responses to faults, unknown obstacles, and discrepancies between expected and sensed world states.Parallel nodes are also used to improve fault tolerance in multi-robot applications.
- Mobile Ground Robots: In RoboCup soccer, BT decision outputs were combined with RRT planning or Fuzzy logic, with Fuzzy obstacle avoidance outperforming other planners on computed-path time and length.The authors also associate BT modularity with easier extension and maintainability for complex decision making.
- Swarm Robotics: Evolutionary BTs produced swarm behaviors that outperformed a hand-coded behavior for single-source foraging, nest maintenance, and cooperative transportation.The tree structure supports mutation and crossover, while modularity can help variations remain functional.
- Autonomous Driving: Autonomous driving remains comparatively underexplored, although simulations report that BTs scale better than FSMs as more behaviors are added.The cited driving examples include lane following, overtaking, and parking.
3.3. Other
Beyond robotics, BTs are used to represent and execute procedures for medical care, human workflows, cognitive problem solving, and smart-home automation. These applications exploit BTs as a general language for workflows and their reactive execution.
- Medicine: BTs have been proposed for online emergency-medical procedure guidance and for agent-agnostic descriptions of surgical procedures.The survey presents medicine as one class of tasks beyond the preceding application areas.
- Medicine: A brain surgeon’s expertise was used to choose actions through a Fallback node for brain-tumor ablation, demonstrated in simulation and experiments on mice.The approach uses human expertise as input to the decision structure.
- Human Workflows: BTs encode observed human workflows, including cooking procedures and activities of daily living represented from interaction constraints between tracked objects.These descriptions can be automatically converted into BT representations.
- Problem Solving: BTs formalize structured problem-solving procedures such as closed-form inverse kinematics for serial manipulators and automated power-grid design.The survey reports these as procedures that are complex but sufficiently well structured for BT encoding.
- Smart Homes: Reactive BT execution has been used in smart homes to balance domestic power loads, engage backup generation, and control lighting or appliances based on human actions.These examples apply BT reactivity to automated domestic systems.
4. Methodology
The survey reviews learning-based and planner-based approaches for synthesizing or improving BTs. These methods aim to combine BT modularity and reactivity with automated design, planning, formal specifications, or evolutionary search, while exposing important scalability trade-offs.
- Overview: BTs serve as policy representations for learning and planning because their modularity benefits both manual and automatic synthesis.The stated motivation is improving performance and design time.
- Learning Approaches: Learning-based BT design includes Reinforcement Learning, evolution-inspired learning, Case Based Reasoning, and Learning from demonstration.Some methods generate BTs automatically, while others optimize parameters in predefined trees.
- Evolution-inspired Learning: Evolutionary methods exploit BT modularity and locality through population-based mutation and crossover, and genetic programming has produced solutions outperforming manual designs.The survey connects small design changes with small performance changes as a useful property for evolutionary search.
- Case Based Reasoning: Case Based Reasoning reuses stored behaviors for new problems but has difficulty refining previously learned strategies, with Reinforcement Learning providing additional adaptability.The approach constructs rules from experiences of previously encountered problems.
- Planning and Analytic Design: Planner-based synthesis commonly computes a plan first and then converts it into a BT, combining goal-directed planning with BT reactivity.Hierarchical Task Network planners map naturally to BT hierarchy, while STRIPS-style backchaining can support runtime expansion and environmental reactivity.
- Planning and Analytic Design: Hybrid approaches pair HTN planners for high-level strategic plans with BTs for low-level task management.Other automatic approaches generate restricted BT topologies and evaluate them in simulation and reality.
- Planning and Analytic Design: LTL-based synthesis models robot capabilities and goals, uses an I/O automaton to synthesize a strategy, and implements the result as a BT.The survey notes that complex LTL and automaton formulations scale poorly, and the generated BT is produced offline.
5. Implementation
The survey reviews BT implementation libraries across languages, interfaces, ROS support, openness, and usage, while highlighting maintenance, execution, and modularity trade-offs.
- Library survey: The library overview compares implementation language, GUI availability, ROS communication, open-source status, and GitHub usage data.The authors caution that the list is not complete because many alternatives exist.
- Robotics libraries: py_trees is open source and well maintained, with ROS extensions, but restricts data sharing, parallel execution, and concurrent behavior initialization.Its constraints allow only one behavior to initialize or execute at a time.
- Execution behavior: py_trees uses a memoryful Sequence by default, which removes a BT reactivity advantage when unexpected events can undo subtree execution.Users can implement a memoryless Sequence using Fallbacks and negations.
- Modularity: Blackboard information sharing supports nodes within one BT but is inherently task specific, limiting subtree reuse across tasks.This creates a tension between BT modularity and the data required by particular tasks.
- Game-oriented libraries: Behavior3 offers a visual editor and exports trees to JSON and Python or Javascript clients, but lacks extensive documentation, periodic maintenance, and ROS support.The visual editor simplifies design and readability.
- Execution models: BehaviorTree.js supports only Success or Failure node returns, while NPBehave uses event-driven execution without requiring root ticks at every cycle.NPBehave’s design is claimed to be more efficient and simpler to use.
- Robotics libraries: ROS-Behavior-Tree lacks current ROS support and has not been updated since October 2018, whereas BehaviorTree.CPP provides the Groot GUI and ROS implementation.The survey links this transition to the authors’ collaboration on BehaviorTree.CPP.
6. Open challenges
The survey identifies explainable AI, human-robot interaction, safe autonomy, and learning-enabled BTs as four open challenges. It links these challenges to BT transparency and modularity while emphasizing that substantial work remains.
- Research agenda: The survey names Explainable AI, human-robot interaction, safe AI, and combining learning with BTs as four important open challenges.These areas frame the paper’s proposed research agenda.
- Explainable AI: BTs may support explainable AI because they capture human workflows, suit manual design, and are human-readable.The survey proposes incorporating data-driven methods into BTs or learning BTs from data-driven policies.
- Human-robot interaction: BT transparency and modularity may simplify programming by non-experts and human-in-the-loop collaboration in human-robot interaction.The survey notes progress but states that much remains to be done.
- Safe autonomy: Safe autonomy becomes increasingly important when autonomous systems capable of harming humans share spaces with people.The survey identifies BT transparency and modularity as potentially important, while noting that many questions remain.
- Learning and BTs: End-to-end reinforcement learning may be infeasible when state spaces are too large to explore efficiently or when explainability and safety guarantees are lacking.The survey discusses BTs as a way to improve individual leaf and interior nodes while retaining structure.
7. Conclusions
The paper surveys more than 160 research papers on BTs in game AI and robotics, organizing them by application areas and methods and identifying open challenges.
- Scope and contribution: The survey covers over 160 papers on Behavior Trees as an AI tool for games and robotics.It partitions and analyzes the literature by application areas and methods, then describes open challenges.