PaperlayerView exact revision on arXiv

Source-linked AI summary

Behavior Trees in Robotics and AI: An Introduction

Michele Colledanchise, Petter Ögren

arXiv:1709.00084v6cs.ROcs.AI

TL;DR

Behavior Trees address the need for reactive, modular task-switching architectures for autonomous agents. This book unifies BT formulations, relates them to earlier approaches, develops analysis and design tools, and applies them to planning, learning, and stochastic execution.

  • Problem

    Autonomous agents require task-switching structures that combine reactivity with modularity and support continual monitoring, modification, and response to exogenous events.

  • Method

    The book develops a unified treatment of BTs covering their formulations, relations to other architectures, design principles, state-space analysis, stochastic frameworks, planning, and learning.

  • Results

    The book provides theoretical results and practical tools for analyzing efficiency, safety, robustness, execution time, and success probabilities, alongside BT applications in planning, learning, and game AI.

  • Takeaways & Limitations

    BTs offer modular subtrees with interfaces like atomic actions and support reactive control, automated synthesis, and learned behavior composition.

  • Takeaways & Limitations

    Utility computation for BTs remains unresolved in practice, and the division between BT structure and action-level functionality must be decided case by case.

Abstract

from arXiv · show

A Behavior Tree (BT) is a way to structure the switching between different tasks in an autonomous agent, such as a robot or a virtual entity in a computer game. BTs are a very efficient way of creating complex systems that are both modular and reactive. These properties are crucial in many applications, which has led to the spread of BT from computer game programming to many branches of AI and Robotics. In this book, we will first give an introduction to BTs, then we describe how BTs relate to, and in many cases generalize, earlier switching structures. These ideas are then used as a foundation for a set of efficient and easy to use design principles. Properties such as safety, robustness, and efficiency are important for an autonomous system, and we describe a set of tools for formally analyzing these using a state space description of BTs. With the new analysis tools, we can formalize the descriptions of how BTs generalize earlier approaches. We also show the use of BTs in automated planning and machine learning. Finally, we describe an extended set of tools to capture the behavior of Stochastic BTs, where the outcomes of actions are described by probabilities. These tools enable the computation of both success probabilities and time to completion.

Quotes on Behavior Trees

Practitioners describe Behavior Trees as expressive, reusable structures that balance goal-oriented behavior, reactivity, and modularity, while avoiding fragility associated with growing finite state machines.

  • Behavior Trees are described as a more expressive tool for modeling autonomous-agent behavior and control flow than finite state machines.
  • Practitioners report preferring Behavior Trees after using them across varied approaches to AI creation.
  • Growing hierarchical finite state-machine logic is characterized as fragile and difficult to modify safely before deployment.
  • Behavior Trees are valued for balancing goal-oriented behaviors with reactivity.
  • Their modularity supports reusing individual behaviors within higher-level behaviors without specifying subsequent relationships.

Chapter 1 What are Behavior Trees?

Behavior Trees structure task switching in autonomous agents through modular, reactive components that can be composed, executed through ticks, and extended across robotics and game applications. The chapter introduces their structure and execution, illustrates node types and examples, and reports practical use in robotics.

  • Behavior Trees structure task switching in autonomous agents and support complex systems that are modular and reactive.They have spread from computer-game programming to AI and robotics.
  • Behavior Trees support recursively designed, task-independent sub-behaviors and can reactively verify conditions during actions.The pick-and-place example checks that the ball remains located and securely grasped.
  • A Behavior Tree is a directed rooted tree with control-flow internal nodes and execution leaves, connected through parent-child relationships.The root is the only node without a parent.
  • Execution begins at the root, which sends ticks to children; nodes return Running, Success, or Failure to their parents.A node executes if and only if it receives a tick.
  • Classical Behavior Trees contain Sequence, Fallback, Parallel, and Decorator control-flow nodes plus Action and Condition execution nodes.
  • Sequence nodes tick children from the left until Failure or Running, returning Success only when all children succeed.
  • In 2015, the KTH entry using Behavior Trees achieved the best result among four teams competing with PR2 robots.The entry used Behavior Trees in both 2015 and 2016, with modularity and code reusability supporting integration across programmers.

Chapter 2 How Behavior Trees Generalize and Relate to Earlier Ideas

The chapter relates BTs to earlier control architectures and argues that BTs preserve modularity while avoiding transition structures that become difficult to maintain as systems grow. It also introduces BTs as suitable for reactive, extensible robot behavior and formal analysis.

  • BTs relate to and often generalize FSMs, Subsumption Architecture, Teleo-Reactive programs, and Decision Trees.
  • FSMs: FSMs are common, intuitive, and easy to implement, but increasing reactivity requires many transitions that reduce maintainability, scalability, and reusability.
  • HFSMs: HFSMs improve modularity through nested states and generalized transitions, but their hierarchy remains manually defined and state-dependent transitions remain difficult to maintain.
  • BTs versus FSMs: Although every BT execution can be represented by an FSM, deeper BTs correspond to increasingly complex FSMs, while BT subtrees provide reusable modules with standard return-status interfaces.
  • BTs versus HFSMs: In the humanoid-robot example, the HFSM contains complete directed graphs for reactive switching, requiring n(n −1) transitions among n nodes.
  • Motivating example: The robot example requires continual monitoring, interruption, skipped actions, responses to exogenous events, and insertion of new actions, whereas its FSM representation becomes complex even for a simple task.

Chapter 3 Design principles

The chapter presents BT design principles for making success conditions explicit, improving reactivity, handling cases, guaranteeing safety, and constructing deliberative behavior. These principles can be combined while preserving the reactivity of the resulting subtrees.

  • Improving readability: Explicit success conditions pair each action with a condition through a Fallback node, clarifying when the action is already complete.
  • Improving reactivity: Implicit sequences check the goal state before means, using preconditions to avoid re-executing unnecessary actions and improve reactivity.
  • Handling different cases: Decision-tree organization separates cases such as Ghost Close and Ghost Scared, selecting among eating pills, chasing ghosts, and avoiding ghosts.
  • Improving safety: A Sequence node can support safety by initiating recharging before the battery becomes critically low, while waiting until 100% prevents rapid switching between recharging and the main task.
  • Creating deliberative BTs: Backchaining builds deliberative BTs by replacing goal conditions and preconditions with Postcondition-Precondition-Action subtrees until the resulting tree works toward the goals.
  • Combining principles: Different design principles can be combined into one complex BT while retaining reactivity across switches among driving, braking, fighting, and stealing behaviors.

Chapter 4 Extensions of Behavior Trees

The chapter surveys Utility BTs, Stochastic BTs, temporary behavior modification, and other extensions. These mechanisms address context-dependent priorities, probabilistic outcomes, and external influence, while utility aggregation and exploration remain unresolved.

  • Utility BTs: Utility Fallbacks replace fixed child priorities with context-dependent ordering based on expected utility.
  • Utility BTs: Computing and propagating utility through complete BTs is difficult: decorator-based computation is ad hoc, while propagation through Fallbacks and Sequences has theoretical difficulties.
  • Stochastic BTs: Stochastic BTs use action success probabilities and provide theoretically straightforward aggregation across Sequences and Fallbacks, assuming each action is tried only once.
  • Stochastic BTs: Learning success probabilities introduces an explore/exploit problem because repeatedly selecting the currently favored action can prevent estimates for alternatives from converging.
  • Stochastic BTs: Combining success probabilities with costs and execution times remains an open problem despite formal treatment of probabilities and execution times.
  • Temporary modification: Temporary BT modification supports operator, collaborator, or level-designer influence, including changing priorities or disabling actions to produce styles such as aggressive or pacifist behavior.
  • Other extensions: Hinted BTs allow an external human or machine to suggest actions without editing the underlying BT.

Chapter 5 Analysis of Efficiency, Safety, and Robustness

Chapter 5 develops a mathematical state-space framework for analyzing BT efficiency, robustness, and safety, and shows how these properties behave under modular compositions. The results provide conditions for preserving finite-time success, enlarging attraction regions, preventing unsafe states, and avoiding switching chatter.

  • 5.1 Statespace Formulation of BTs: The framework represents each BT through dynamics, a time step, return status, and partitioned running, success, and failure regions.All BTs are assumed to evolve in the same continuous state space with the same time step, with larger Cartesian-product spaces accommodating heterogeneous subsystems.
  • 5.2 Efficiency and Robustness: The analysis establishes when finite-time success, execution-time bounds, and robustness properties carry across Sequence, Fallback, and Parallel compositions.For Sequence compositions, the completion-time bound is additive under the stated success-region condition; Fallback compositions can enlarge the region of attraction.
  • 5.2 Efficiency and Robustness: Global exponential stability implies finite-time success when the success region contains a neighborhood of the stable equilibrium, with no failure region.The proof uses convergence to show that the trajectory enters the success region within finite time.
  • 5.2 Efficiency and Robustness: Fallback composition can handle more initial conditions by moving states into a region handled by another BT, thereby enlarging the combined success region of attraction.In the example, the combined BT moves a larger set of initial conditions to the desired region S0 = S1.
  • 5.3 Safety: Safety guarantees can be separated from task execution: a safeguarding BT followed by an arbitrary BT remains safe when the latter’s state change stays below the safeguarding margin.The Sequence safety lemma requires maxx ||x −f2(x)|| < d, while the UAV and battery examples instantiate these conditions.

Chapter 6 Formal Analysis of How Behavior Trees Generalize Earlier Ideas

The chapter formally shows that Behavior Trees generalize several earlier switching and control architectures, while providing richer analysis and design flexibility. These correspondences are established for Decision Trees, Subsumption, Sequential Behavior Compositions, and Teleo-Reactive programs.

  • 6.1 How BTs Generalize Decision Trees: BTs generalize Decision Trees by mapping predicates to conditions and actions to BT subtrees, with all actions returning Running to preserve the executed atomic action.The resulting BT executes the same atomic action for every predicate assignment as the original Decision Tree.
  • 6.1 How BTs Generalize Decision Trees: Because Decision Tree predicates are ‘If ... then ... else ...’ statements, learned Decision Trees can be converted into BTs and extended with safety or robustness features.The chapter connects this formal correspondence to learning Decision Trees from human operators.
  • 6.1 How BTs Generalize Decision Trees: The Decision Tree mapping can also yield a more compact equivalent BT while retaining the assumption that all actions return Running.The compact formulation is shown after the direct mapping.
  • 6.2 How BTs Generalize the Subsumption Architecture: A Subsumption architecture is represented by a Fallback whose action children are ordered from highest to lowest priority and return Failure when inactive or Running when active.The BT checks controllers in priority order until one returns Running; if all return Failure, no action executes.
  • 6.3 How BTs Generalize Sequential Behavior Compositions: BTs generalize Sequential Behavior Compositions by replacing execution-region computations and controller switching with an appropriately ordered Fallback composition.When all component trees are FTS, the resulting tree is also FTS.
  • 6.4 How BTs Generalize the Teleo-Reactive approach: A Teleo-Reactive program can be translated into an equivalent BT using the BT functional form and its condition-action structure.The translation is illustrated for the Teleo-Reactive program Goto.
  • 6.4.1 Universal Teleo-Reactive programs and FTS BTs: BT analysis extends the Teleo-Reactive result by including execution time and continuous-state finite-difference models with imperfect sensing and actuation.The stronger regression property requires each action to satisfy an earlier condition without violating the current one.

Chapter 7 Behavior Trees and Automated Planning

Automated planning must handle uncertain, changing environments where static plans can become infeasible and replanning from scratch can be expensive. Combining planning with BTs supports hierarchical, modular deliberation that monitors, updates, and extends plans while acting.

  • Chapter 7 Behavior Trees and Automated Planning: Classical planning commonly assumes a known static world and returns a fixed action sequence executed through an FSM.Under that assumption, changes are produced by the controlled agent’s actions.
  • Chapter 7 Behavior Trees and Automated Planning: In uncertain environments with other agents, action effects may diverge from the planned trajectory, making subsequent actions infeasible and frequent replanning expensive.The chapter identifies continual online planning and plan repair as open challenges.
  • Chapter 7 Behavior Trees and Automated Planning: BT reactivity enables re-executing previous subplans without replanning, while modularity enables recursively extending plans without replanning the whole task.Together these properties support deliberation that is hierarchical and modular while the agent acts.
  • Chapter 7 Behavior Trees and Automated Planning: In examples, BTs recover when an object slips from a gripper and incorporate obstacle-removal actions while skipping them when an external actor removes the obstacle.These behaviors are presented as instances of reactivity and iterative plan refinement.

7.1 The Planning and Acting (PA-BT) approach

Planning and Acting using Behavior Trees (PA-BT) interleaves planning with execution by expanding failed conditions into action-and-condition subtrees. The resulting BTs monitor progress, repair or extend plans during execution, and preserve safety across the described expansions.

  • 7.1 The Planning and Acting (PA-BT) approach: PA-BT extends BT Backchaining by replacing a condition with a PPA BT that achieves that condition through actions and their preconditions.The PPA structure is used to iteratively construct the behavior tree.
  • 7.1 The Planning and Acting (PA-BT) approach: PA-BT combines infinite-state-space planning with BT reactivity and modularity, enabling hierarchical deliberation that monitors, updates, and extends plans while acting.The framework is described as addressing the need for continual plan repair during execution.
  • 7.1 The Planning and Acting (PA-BT) approach: The planning process iteratively expands conditions to produce successive BTs, beginning with a goal condition and ending when an executable action template has satisfied conditions.The example applies PPA expansion repeatedly to the previous tree.
  • 7.1 The Planning and Acting (PA-BT) approach: The PA-BT robot example uses goal, grasp, neighborhood, hand-empty, and collision-free-trajectory conditions to sequence movement and picking actions.The final tree is built through the successive expansions illustrated in the planning example.
  • 7.1 The Planning and Acting (PA-BT) approach: BT ticking allows a dropped cube to trigger immediate rechecking and repicking without replanning, while changed obstacles can cause the tree to skip obsolete removal actions.Running statuses propagate through the tree, and failed conditions redirect execution to the corresponding subtree.
  • 7.1 The Planning and Acting (PA-BT) approach: When a BT returns Failure, PA-BT uses breadth-first search to find a failing condition to expand; multiple valid action refinements are collected under a Fallback with memory.The tree is expanded until it contains an action template whose conditions hold in the current state.
  • 7.1 The Planning and Acting (PA-BT) approach: The safety-critical events are handled separately before ordinary progression, and the resulting tree and all PA-BT expansions are safe under the stated analysis.This safety claim is made for the tree in Figure 7.14 and its possible PA-BT expansions.

7.2 Planning using A Behavior Language (ABL)

ABL is a planning language that organizes behaviors, goals, conditions, and actions for multi-scale planning and execution. Its agent architecture translates ABL instructions into behavior trees and demonstrates the approach in Pac-Man and StarCraft.

  • ABL is a planning language designed to handle planning and acting across multiple scales, especially in robotics and real-time strategy games.
  • An ABL Agent: An ABL agent uses a behavior library of sequential and parallel behaviors, working memory, and an initial tree of subgoals.
  • ABL Instructions: ABL instructions include physical and mental actions, preconditions for behavior selection, conflicts for priority ordering, and subgoals for accomplishing main tasks.
  • ABL Instructions: Spawngoal instructions expand behavior trees lazily when a spawned goal is first needed, whereas subgoal instructions require execution details at design time.
  • ABL-to-BT Translation: The translation algorithm builds a behavior tree from the initial ABL tree, representing behaviors as sequences or parallels and instructions as corresponding nodes.
  • StarCraft Execution: In StarCraft, an ABL agent combines strategy, production, and tactics managers, achieving over 60% overall win rate and over 200 game actions per minute across tested conditions.

7.3 Comparison between PA-BT and ABL

PA-BT focuses on constructing behavior trees through planning, whereas ABL is a complete planning language that uses behavior trees as an execution tool. PA-BT more directly exploits BT Fallback constructs through iterative PPA expansion.

  • PA-BT creates behavior trees using a planning approach, while ABL is a complete planning language that uses behavior trees for execution.

Chapter 8 Behavior Trees and Machine Learning

Chapter 8 presents genetic programming, reinforcement learning, and learning-from-demonstration approaches for automatically creating Behavior Trees. Its GP-BT strategy combines greedy search with genetic programming, preserves safety through a dedicated subtree, and can achieve task completion while controlling tree growth.

  • Learning algorithms are used to automatically create Behavior Trees through genetic programming, reinforcement learning, and learning from demonstration.The chapter presents a mixed greedy–GP strategy, an RL algorithm, and an overview of other learning approaches.
  • Genetic Programming Applied to BTs: Genetic programming evolves Behavior Trees using crossover, mutation, and reward-based selection across successive generations.Crossover swaps subtrees between trees, mutation replaces nodes with nodes of the same type, and selection assigns survival probabilities based on reward.
  • Genetic Programming Applied to BTs: Behavior Trees avoid the logic-violation problem that can occur when genetic programming crosses over finite-state machines.BT crossover swaps subtrees while preserving the tree representation, whereas FSM crossover can produce transitions to nonexistent states.
  • The GP-BT Approach: The GP-BT approach first uses a greedy search and invokes genetic programming when needed, reducing learning time while producing a fairly compact tree.The algorithm tests actions that increase reward, applies GP at local maxima, and can simplify or generalize learned responses across situations.
  • The GP-BT Approach: GP-BT combines a manually generated or non-learning safety subtree with a learned tree, so the safety subtree can override learning when necessary.In the Mario example, the safety action is user-specified and is designed to prevent entry into selected unsafe regions with a conservative margin.
  • Experimental Results: The experiments measure reward and learned-tree complexity, finding that GP-BT reaches reward 1 within the execution time while pure GP often checks many conditions but performs few actions.The reported comparison includes scenarios 1 and 5; GP-BT’s growth rate tends to decrease over time, whereas FSM node counts increase exponentially.
  • Experimental Results: The learning agent’s accuracy converges to 97-99%, with the remaining deviation attributed to trial-and-error in learning the most effective action order.A separate reported experiment describes a learning Action node for extinguisher selection and states that its accuracy converges to 100%.
  • Learning from Demonstration: Learning from demonstration can make a learned Behavior Tree very large because each demonstrated trace is directly mapped into a new sub-tree.Subsequent approaches reduce size by finding and combining common action patterns, which also improves readability.

Chapter 9 Stochastic Behavior Trees

This chapter analyzes the reliability of reactive plan executions using execution-time distributions and success probabilities. It develops methods for computing these measures for complex plans encoded as Behavior Trees.

  • The chapter studies reactive-plan reliability through execution times and success probabilities.
  • A search plan illustrates how task ordering and action outcomes determine overall execution-time and success-probability measures.The example searches a table before opening and searching a drawer if the object is not found.
  • The methods are intended to compute reliability measures for arbitrary complex plans represented by Behavior Trees.

9.1 Stochastic BTs

Stochastic Behavior Trees model action outcomes and timing probabilistically, enabling reliability analysis through Markov-theoretic descriptions. The section defines stochastic, deterministic, and hybrid actions and their associated probability and time models.

  • Stochastic BT analysis computes execution-time and success-probability measures such as MTTS, MTTF, and probabilities over time.The section emphasizes that BT modularity and hierarchy support scalable composition of these measures.
  • Markov theory provides discrete- and continuous-time models for plan executions, using DTMCs for state-changing action sequences and CTMCs for transition rates.
  • A stochastic action has known success and failure probabilities, with success and failure times modeled by exponential distributions.
  • A deterministic action has known success and failure probabilities and deterministic success and failure times τs and τf.
  • Hybrid actions combine one exponentially distributed outcome time with one deterministic outcome time.
  • For deterministic-success hybrid actions, the probability of Running is zero after τs, when the action has either failed or succeeded.

9.2 Transforming a SBT into a DTMC

The section transforms a Stochastic Behavior Tree node into a discrete-time Markov chain by representing child outcomes as markings and feasible child completions as transitions. This creates a recursive, scalable route from action models to node-level transition probabilities.

  • Each control-flow node is represented by child-outcome markings and an execution policy before being mapped to a DTMC.
  • The construction proceeds recursively from leaves with known probabilistic parameters toward larger subtrees.
  • A child outcome event changes one marking component to −1 for Failure or 1 for Success, while zero denotes no completed outcome.
  • Feasible events are restricted by each node’s execution policy and by which children are currently ticked or unfinished.
  • The Marking Reachability Graph contains reachable markings and event transitions, which become DTMC states and one-step transition probabilities.
  • A general Parallel-node mapping is not depicted because it has a large number of states and possible transitions.

9.3 Reliability of a SBT

The reliability analysis derives time-to-success and time-to-failure measures from Markov-chain state visitation and sojourn times. Deterministic execution times require a piecewise discrete-time treatment because their probability functions have jumps.

  • Average sojourn time accounts for outcome probabilities and execution rates of running children, combining concurrent rates in Parallel nodes.The sojourn time is obtained from the inverse of the combined rate.
  • The canonized DTMC separates transient-state transitions from transitions to failure and success states.
  • MTTF and MTTS combine probabilities of reaching absorbing failure or success states with the mean time spent in transient states.
  • Mean visit-count equations describe how often transient states are visited before absorption in failure or success states.
  • For each SBT node, success and failure probabilities over time are obtained by summing the CTMC probabilities of success and failure states.
  • Deterministic nodes produce discontinuous probability functions, so a discrete-time system with zero-order hold can represent their jumps more tractably.

9.4 Examples

The examples develop analytical performance calculations for stochastic behavior trees, verify them against Monte Carlo simulation, and compare alternative timing and execution-order models. They show that stochastic timing affects failure probabilities and that reordering fallback options changes transient performance while preserving asymptotic probabilities.

  • Examples: Three examples demonstrate detailed stochastic-BT calculations, deterministic-time comparison, and numerical verification on a more complex tree.The complex example also compares performance metrics between equivalent behavior trees.
  • Analytical computation: Closed-form expressions compute mean time to success, mean time to failure, and other probabilistic parameters from the stochastic-tree model.The derivation uses matrix decompositions and transition-rate formulations.
  • Numerical verification: Analytical estimates are verified against approximately 80,000 Monte Carlo runs implemented in ROS with exponentially distributed action outcomes.The simulations record success or failure and execution time for the whole tree and selected subtrees.
  • Timing models: Stochastic and deterministic action-time models produce their largest deviation in failure probabilities.The comparison evaluates accumulated Success, Failure, and Running probabilities for the root and selected nodes.
  • Execution order: After 100s, success probability is about 30% when searching drawers first versus about 20% when searching the floor first.The drawer-first tree is therefore optimal for this example, although equivalent fallback permutations have identical asymptotic probabilities.

Chapter 10 Concluding Remarks

The concluding remarks present behavior trees as a unified framework spanning classical formulations, extensions, analysis, planning, and learning. They emphasize modularity as a practical foundation and describe BTs as promising for game AI and robotics, while noting that substantial work remains.

  • Unified framework: The book unifies classical behavior trees, extensions, relations to other approaches, design principles, and applications in planning and machine learning.It also develops formal tools for efficiency, safety, robustness, execution time, and success probabilities.
  • Modularity: Modularity gives behavior trees clear interfaces that reduce dependencies and simplify development, testing, and reuse.Each tree level has the same interface as a single action.
  • Scope and outlook: Behavior trees are presented as a promising control architecture for computer game AI and robotics, although further work remains.The book aims to provide a unified view of diverse formulations, algorithms, and applications.
Loading 1709.00084v6…