Behavior Trees in Robotics and AI: An Introduction

2 How Behavior Trees Generalize and Relate to Earlier Ideas

• Section 2 compares Behavior Trees with finite state machines, hierarchical finite state machines, subsumption architectures, teleo-reactive programs, and decision trees.It also separately catalogs the advantages and disadvantages of Behavior Trees.Source: §2 · pp. 3–4
• The finite-state-machine discussion covers ordinary and hierarchical FSMs, including how to create FSMs that work like BTs and BTs that work like FSMs.Source: §2 · p. 3
• The section also addresses how BTs generalize subsumption architectures, teleo-reactive programs, and decision trees.Source: §2 · p. 3

3 Design principles

• Section 3 presents design principles for improving readability, reactivity, case handling, safety, deliberation, and control over BT reactivity and granularity.Its topics include explicit success conditions, implicit sequences, decision-tree structures, sequences, backchaining, memory nodes, granularity, and an integrated design.Source: §3 · p. 4
• The design-principles section specifically includes methods for creating deliberative BTs with backchaining and un-reactive BTs with memory nodes.Source: §3 · p. 4

4 Extensions of Behavior Trees

• Section 4 surveys utility BTs, stochastic BTs, temporary BT modification, and other extensions, including dynamic expansion.Source: §4 · p. 4

5.1 Statespace Formulation of BTs

• The section introduces a state-space formulation of Behavior Trees as the basis for subsequent analysis.Source: §5 · p. 4

5.2 Efficiency and Robustness; 5.3 Safety

• It analyzes efficiency, robustness, and safety as distinct properties of Behavior Trees.Source: §5 · p. 4

5.4 Examples

• Examples demonstrate robustness and efficiency, safety, and a more complex Behavior Tree.Source: §5 · p. 4

6.1 How BTs Generalize Decision Trees

• The section analyzes how Behavior Trees generalize decision trees.Source: §6 · p. 4

6.2–6.3

• It examines Behavior Trees in relation to the subsumption architecture and sequential behavior compositions.Source: §6 · p. 4

6.4 How BTs Generalize the Teleo-Reactive approach

• The section analyzes how Behavior Trees generalize the teleo-reactive approach, including universal teleo-reactive programs and FTS Behavior Trees.Source: §6 · p. 4

7.1 The Planning and Acting (PA-BT) approach

• The section develops the Planning and Acting (PA-BT) approach, including its algorithm, execution, reactiveness, safety, fault tolerance, and realistic-robot applications.Source: §7 · pp. 4–5

7.2 Planning using A Behavior Language (ABL)

• It then covers planning using A Behavior Language (ABL), including the agent, planning approach, and complex execution results in StarCraft.Source: §7 · p. 5

7.3 Comparison between PA-BT and ABL

• The section concludes with a comparison between PA-BT and ABL.Source: §7 · p. 5

Genetic Programming Applied to BTs

• The section introduces genetic programming applied to Behavior Trees, including the GP-BT approach, algorithm details, pruning, experimental results, and related approaches.Source: §8 · p. 5

Reinforcement Learning applied to BTs

• It presents reinforcement learning applied to Behavior Trees through Q-learning, the RL-BT approach, and experimental results.Source: §8 · p. 5

Comparison and Learning from Demonstration

• The section compares GP-BT with RL-BT and separately addresses learning from demonstration applied to Behavior Trees.Source: §8 · p. 5

9.1 Stochastic BTs

• Stochastic Behavior Trees are formulated using Markov chains and Markov processes.Source: §9 · p. 5

9.2 Transforming a SBT into a DTMC

• The section presents a transformation from an SBT into a discrete-time Markov chain and methods for computing its transition properties.Source: §9 · p. 5

9.3 Reliability of a SBT

• It analyzes SBT reliability through average sojourn time, mean times to failure and success, and probabilities over time.Source: §9 · p. 5
• The reliability analysis covers both stochastic and deterministic execution times.Source: §9 · p. 5

9.4 Examples

• The section concludes with examples illustrating the stochastic behavior-tree methods.Source: §9 · p. 5

• The excerpt lists the references on page 188 but gives no concluding findings or claims.Source: §10 · p. 5

• Behavior trees are described as more expressive than finite state machines for modeling autonomous-agent behavior and control flow. 1Source: Quotes on Behavior Trees · p. 7
• Compared with finite state machines, behavior-tree logic is characterized as less fragile as systems grow, avoiding temperamental hierarchical designs. 3Source: Quotes on Behavior Trees · p. 7
• Behavior trees are praised for balancing goal-oriented behaviors with reactivity. 4Source: Quotes on Behavior Trees · p. 7
• Behavior trees enable individual behaviors to be reused within higher-level behaviors without specifying their relations to subsequent behaviors.Source: Quotes on Behavior Trees · p. 7

What are Behavior Trees?

• BTs structure task switching for autonomous agents, enabling complex systems that are both modular and reactive across computer games, AI, and robotics.Activities are assumed to decompose into reusable sub-activities or tasks.Source: Chapter 1 What are Behavior Trees? · p. 9

1.1 A Short History and Motivation of BTs

• BTs emerged in games to improve NPC modularity and provide an alternative view of FSMs, supporting code reuse, incremental design, testing, and modular systems.They subsequently received academic attention and were used in robotic manipulation and programming tools for non-experts [56].Source: §1.1 · pp. 10–11

1.2 What is wrong with FSMs? The Need for Reactiveness and Modularity

• BTs address FSMs’ reactivity–modularity tradeoff by using two-way control transfers, allowing behaviors to be organized into independently reusable modules.FSM transitions are one-way transfers that proliferate as reactivity increases, making component removal require revisions to every transition targeting it.Source: §1.2 · p. 11

1.3 Classical Formulation of BTs

• Formally, a BT is a directed rooted tree whose internal control-flow nodes tick leaf execution nodes, which return Running, Success, or Failure.Classical BTs include Sequence, Fallback, Parallel, and Decorator control-flow nodes, plus Action and Condition execution nodes.Source: §1.3 · p. 12
• Sequence and Fallback nodes route ticks according to child statuses, while Parallel uses a user-defined success threshold and Decorator modifies or selectively permits child execution.Actions return Running during execution and Success or Failure afterward; Conditions return Success or Failure and never Running.Source: §1.3 · pp. 12–15

1.3.1 Execution Example of a BT

• In execution, changing conditions can preempt running actions and redirect ticks, enabling an agent to abandon an outdated subtask and pursue the behavior matching the current situation.When a ball is displaced, the example preempts approaching the bin and resumes approaching the ball.Source: §1.3.1 · pp. 15–16

1.3.2 Control Flow Nodes with Memory

• Memory nodes prevent unwanted re-execution of completed children, but implementations without Running are non-reactive and therefore of limited use because other actions cannot respond to changes.Memory can be represented using auxiliary conditions, making memory nodes syntactic sugar.Source: §1.3.2 · p. 16

1.4 Creating a BT for Pac-Man from Scratch

• Incremental Pac-Man BTs modularly add ghost avoidance and ghost chasing to pill collection, while mobile-manipulator BTs encode cube placement through goal, grasp, and proximity conditions.The Pac-Man example leaves the division between BT structure and action-internal spatial reasoning as a case-by-case design decision.Source: §1.4 · pp. 18–20, §1.5 · pp. 20–21

1.5 Creating a BT for a Mobile Manipulator Robot

• A mobile-manipulator BT composes separate grasping and goal-reaching behaviors, enabling green-cube placement when collision-free trajectories to the cube and goal area exist.The grasping behavior checks that the hand is free and approaches the cube when needed; the goal behavior moves to the goal while a collision-free trajectory exists.Source: §1.5 · p. 21

1.6 Use of BTs in Robotics and AI

• BTs are presented across real robot applications spanning autonomous driving and industrial robotics.The section frames these applications as projects using BTs in multiple robotics and AI domains.Source: §1.6 · p. 21

1.6.1 BTs in autonomous vehicles

• For autonomous vehicles, BTs are proposed as a potentially beneficial alternative to the FSM- and HFSM-based architectures commonly used in the DARPA Grand Challenge.The iQmatic project selected BTs for a fully autonomous heavy truck because its software needed to be reusable, maintainable, and easy to develop; developers valued human readability and easier editing.Source: §1.6.1 · pp. 22–23

1.6.2 BTs in industrial robotics

• Industrial-robotics projects use BTs to simplify subtask composition and support human-readable, reusable, modular, and inspectable robot programs.CoSTAR supports composing increasingly larger trees independently of subtask implementation; SARAFun uses BTs for learned or planned generic actions, while Intera supports manual or demonstration-based BT creation, inspection, adjustment, and simulation.Source: §1.6.2 · pp. 24–26

1.6.3 BTs in the Amazon Picking Challenge

• In the 2015 Amazon Picking Challenge, the KTH BT-based entry achieved the best result among four PR2 teams, supported by modularity and code reusability.BTs enabled integration of functionalities developed by programmers with different backgrounds and coding styles; KTH also used BTs in 2016.Source: §1.6.3 · p. 27

1.6.4 BTs inside the social robot JIBO

• BTs are a fundamental part of JIBO’s social-robot software architecture and its open SDK for external contributors developing new skills.JIBO provides home-oriented social functions including face and voice recognition, jokes, games, and information sharing.Source: §1.6.4 · p. 27

Chapter 2 How Behavior Trees Generalize and Relate to Earlier Ideas

• BTs are presented as generalizations of FSMs, Subsumption Architecture, Teleo-Reactive programs, and Decision Trees, with advantages and disadvantages discussed for each approach.Some chapter results were previously published in.Source: Chapter 2 How Behavior Trees… · p. 29

2.1.1 Advantages and disadvantages

• FSMs are common, intuitive, and easy to implement, but growing transition structures impair maintainability, scalability, reusability, and automated design.Adding states can require reevaluating many existing and new transitions, while state-dependent transitions make sub-FSMs difficult to reuse.Source: §2.1.1 · p. 30

2.2.1 Advantages and disadvantages

• HFSMs improve modularity and behavior inheritance, yet still require user-defined hierarchies and can retain densely connected transition subgraphs.In the compared example, the HFSM requires n(n −1) transitions within complete directed graphs, whereas BT subtrees act as independently interfaced modules.Source: §2.2.1 · pp. 31–32

2.2.2 Creating a FSM that works like a BTs

• Every BT execution can be represented by an FSM and vice versa, but BT modularity encapsulates complexity while FSM transitions require decisions at the destination state.A five-level BT corresponds to a potentially complex FSM, whereas BT parents decide what follows a subtree’s Success, Running, or Failure return.Source: §2.2.1 · p. 32, §2.2.2 · pp. 35–37

2.3.2 How BTs Generalize the Subsumption Architecture

• A Subsumption Architecture maps to a BT by converting each prioritized controller into an Action and composing them with a Fallback node.The controller returns Running when its binary output requests control and Failure otherwise; the mapping is also supported formally in Section 6.2.Source: §2.3 · p. 38, §2.3.2 · p. 39

2.4 Teleo-Reactive programs

• Teleo-Reactive programs prioritize continuously monitored condition-action rules, enabling reactive action switching but making complex maintenance and failure handling difficult.A BT Fallback with condition-action pairs captures the core of a general TR program; formal analysis is deferred to Section 6.4.Source: §2.4 · p. 40, §2.4.1 · p. 41, §2.4.2 · p. 41

2.5 Decision Trees

• Decision Trees provide modular, hierarchical, intuitive predicate evaluation, but their nodes transmit no information outward, making failure handling difficult.The BT mapping converts predicates to Conditions and leaves to Actions that always return Running, preserving this limitation.Source: §2.5.1 · p. 42, §2.5.2 · p. 42

2.6 Advantages and Disadvantages of Behavior Trees

• The chapter concludes its comparison by turning to a separate account of Behavior Trees’ advantages and disadvantages.The supplied passage introduces Section 2.6 but does not provide its substantive findings.Source: §2.6 · p. 43

2.6.1 Advantages

• BTs support modular, hierarchical, reusable, reactive, human-readable, and expressive control, with standardized return statuses separating tree logic from leaf-node execution.Continual ticking and traversal enable closed-loop responses to environmental changes, while subtree composition supports design, testing, reuse, and hierarchical extension.Source: §2.6.1 · p. 44
• BTs support safety, robustness, efficiency, reliability, and composability analysis, while also enabling automatic synthesis through planning and machine learning.They are at least as expressive as FSMs, Subsumption Architectures, Teleo-Reactive programs, and Decision Trees.Source: §2.6.1 · p. 45
• The robot example shows BTs continually monitoring actions, aborting or skipping them, responding to exogenous events, and supporting modular, hierarchical, analyzable, readable, extensible, and reusable policies.An FSM for the same simple behavior becomes fairly complex with many transitions.Source: §2.6.1 · p. 48

2.6.2 Disadvantages

• BTs can be complex to implement, require potentially expensive condition checking, offer little advantage in predictable environments, demand a different design mindset, and have less mature tooling.Memory nodes can support open-loop execution when closed-loop checking is too costly or infeasible, and BT engines can be reused once implemented.Source: §2.6.2 · pp. 48–49

3.1 Improving Readability using Explicit Success Conditions

• Pairing each action with an explicit success condition through a Fallback node removes ambiguity about behavior when the intended state already holds.For example, already unlocked and open doors cause condition checks to succeed, allowing the agent to proceed directly to passing through.Source: §3.1 · p. 52

3.2 Improving Reactivity using Implicit Sequences

• Implicit sequences improve reactivity by checking the goal first, then using preconditions and Fallback nodes to execute only actions needed to reach it.This construction also supports undoing actions, such as closing a door after passing through, and can be created systematically by backchaining.Source: §3.2 · p. 53

3.3 Handling Different Cases using a Decision Tree Structure

• Decision-Tree structures organize reactive policies by separating cases, such as Pac-Man eating pills, chasing a scared ghost, or avoiding an unscared ghost.The cases are selected using the conditions Ghost Close and Ghost Scared.Source: §3.3 · p. 53

3.4 Improving Safety using Sequences

• Sequences can guarantee safety by forcing recharging before a main task, while changing the threshold to 100% prevents chattering between recharging and task execution.The battery guarantee assumes the main task keeps the robot close enough to the station for 20% battery to suffice for return travel.Source: §3.4 · pp. 53–54, Figure 3.5 · p. 54, Figure 3.6 · p. 54

3.5 Creating Deliberative BTs using Backchaining

• Backchaining constructs deliberative, goal-directed BTs by recursively replacing failed preconditions with PPAs whose postconditions achieve those conditions.The resulting reactive BT tries alternative actions and precondition paths until the goal succeeds or all options fail.Source: §3.5 · pp. 55–56

3.6 Creating Un-Reactive BTs using Memory Nodes

• Memory nodes simplify BTs by preventing re-execution of completed children when no unexpected event can undo their effects.In a predictable industrial workspace, a sequence with memory can pick, move, and place an object without rechecking that it remains held during movement.Source: §3.6 · p. 57

3.7 Choosing the Proper Granularity of a BT

• Choose a leaf when behavior subparts always execute together, but use a sub-BT when parts may be recombined or need reactive re-execution.Overly fine-grained trees can become complex, whereas overly compact actions can lose reactivity when unexpected changes require retrying only part of a task.Source: §3.7 · pp. 58–59

3.8 Putting it all together

• BT modularity preserves reactivity when independently designed subtrees are combined, enabling context-dependent switches among driving, forced entry, fighting, and stealing behaviors.The combined tree integrates implicit sequences, safety design, and backchaining while maintaining reactivity across its parts.Source: §3.8 · pp. 60–61

Chapter 4 Extensions of Behavior Trees

• BT extensions commonly target Fallback ordering, whose children may represent equivalent alternatives, although ordering becomes consequential when Fallbacks encode reactive implicit sequences.The chapter introduces these extensions as responses to the spread of BTs across AI and robotics.Source: Chapter 4 Extensions of Behavior Trees · p. 63

4.1 Utility BTs

• Utility Fallbacks reorder actions by normalized expected utility, replacing fixed priorities with context-dependent choices such as escaping or fighting.Utility computation remains difficult for modular trees because utility must be aggregated and propagated through Fallbacks and Sequences.Source: §4.1 · p. 64

4.2 Stochastic BTs

• Stochastic BTs aggregate action success probabilities across Sequences and Fallbacks, assuming each action is attempted only once.State-dependent probability learning can select situation-appropriate actions, but exploration is needed to avoid favoring initially successful alternatives; combining success, cost, and time remains open.Source: §4.2 · pp. 64–65

4.3 Temporary Modification of BTs

• Temporary BT modifications let operators, collaborators, level designers, or AI engineers alter priorities or disable behaviors without permanently redesigning the tree.Styles disable selected actions, while hinted BTs use positive or negative hints to reorder Fallbacks and add hint-dependent conditions.Source: §4.3 · pp. 65–67
• Positive and negative hints can concretely prioritize fighting or door braking, or discourage spending money, while changing corresponding conditions.These mechanisms influence both Fallback ordering and whether specific action requirements are checked.Source: §4.3 · p. 67

4.4.1 Dynamic Expansion of BTs

• Dynamic Expansions defer selected BT details to runtime search using specified action features such as taxonomy categories.This allows newly created actions to be used by existing BTs when they satisfy the tree’s specified desired features.Source: §4.4.1 · p. 67

Chapter 5 Analysis of Efficiency, Safety, and Robustness

• The chapter’s framework analyzes BT efficiency through execution-time bounds, robustness through region-of-attraction size, and safety through avoidance of specified state-space regions.These properties are presented as requirements for large-scale autonomous agents.Source: Chapter 5 Analysis of Efficiency,… · p. 69

5.1 Statespace Formulation of BTs

• BTs are formalized as state-space systems whose recursive return statuses—Running, Success, or Failure—support modular composition under shared-space and time-step assumptions.Different subsystem spaces can be embedded in a Cartesian-product state space.Source: §5.1 · pp. 69–70

5.2 Efficiency and Robustness

• Finite-time success composes across BTs: Sequence compositions add time bounds, while Fallback compositions can enlarge attraction regions and handle more diverse initial conditions.Robustness here means large regions of attraction, not disturbance rejection; Parallel compositions remain finite-time successful under the stated assumptions.Source: §5.2 · pp. 72–73

5.3 Safety

• A safeguarding BT followed by an arbitrary bounded-step BT remains safe under Sequence composition, allowing separate safety and task-execution controllers while avoiding the obstacle region.The second BT must satisfy max_x ||x − f2(x)|| < d, where d is the safeguarding margin.Source: §5.3 · pp. 76–78
• A Sequence(T1,T2) composition is chatter-free at a switching boundary for sufficiently small ∆t when λ1(x) < 0 or λ2(x) > 0.The condition ensures the vector field points outward on at least one side; it is not satisfied on the right side of Figure 5.8.Source: §5.3 · p. 79

5.4 Examples

• The examples were implemented with the ROS BT library to analyze robustness, efficiency, safety, performance estimates, and complex BT properties.The chapter identifies separate examples for robustness and efficiency, safety, and a more complex BT.Source: §5.4 · p. 79

5.4.1 Robustness and Efficiency

• The humanoid BT T3 = Fallback(T4,T5,T6) is FTS over R′3 = {x : 0 < x1 ≤0.5,0 ≤x2 ≤0.55} with completion-time bound τ3 = 24.The bound combines τ4 = 10, τ5 = 4, and τ6 = 10, while fallback actions expand robustness by combining their regions of attraction.Source: Figure 5.9 · p. 80, §5.4.1 · p. 83

5.4.2 Safety

• For T1 given by (5.44)-(5.48) and any BT T2 satisfying maxx ||x − f2(x)|| < 5, T0 = Sequence(T1,T2) is safe with respect to I and O, so x(t) ≠ O for all t > 0 when x(0) ∈ I.The obstacle is the Empty Battery state O = {x : x2 = 0}. Guarantee Power Supply starts when Do Other Task lowers the battery below 20%, and the remaining battery is enough to return to the recharging station within reachable space x1k ∈[0,100].Source: §5.4.2 · p. 85

5.4.3 A More Complex BT

• The complex humanoid BT is safe when reachable states remain within 100 distance units of the station and battery decrease is below 5% per timestep, while its Play Ball Game subtree remains FTS.Under the FTS assumption, Play Ball Game has completion-time bound τ1 +τ2 +τ3 and region of attraction R′1 ∪R′2 ∪R′3; adding recovery fallbacks yields bound τ1 +τ2 +τ3 +τ5 +τ6.Source: §5.4.3 · p. 88

Chapter 6 Formal Analysis of How Behavior Trees Generalize Earlier Ideas

• BTs generalize four earlier switching structures: Decision Trees, the Subsumption Architecture, Sequential Behavior Compositions, and the Teleo-Reactive Approach.The chapter formalizes these results using the analysis tools developed in Chapter 5; some results were previously published in.Source: Chapter 6 Formal Analysis of How… · p. 89

6.1 How BTs Generalize Decision Trees

• A Decision Tree can be mapped to an equivalent BT that executes the same atomic action for every predicate assignment.The mapping represents predicates as BT conditions and requires actions to return Running, disabling BT feedback; learned Decision Trees can then be extended with safety or robustness features.Source: §6.1 · p. 90

6.2 How BTs Generalize the Subsumption Architecture

• The Subsumption Architecture is equivalent to a priority-ordered Fallback whose controllers return Running when active and Failure otherwise.Controllers are checked from highest to lowest priority until one returns Running; if all return Failure, no action executes.Source: §6.2 · p. 92, Then we write an equivalent BT as… · p. 93

6.3 How BTs Generalize Sequential Behavior Compositions

• Sequential Behavior Compositions are captured by ordering controllers under a Fallback according to the construction’s queue, replacing explicit region computation and controller switching.If all component controllers are finite-time successful, the resulting BT is also finite-time successful.Source: §6.3 · p. 94

6.4 How BTs Generalize the Teleo-Reactive approach

• A Teleo-Reactive program can be translated into a BT by converting True/False conditions to Success/Failure and making actions return Running.The resulting BT executes the same action selected by the first satisfied Teleo-Reactive condition, including for the Goto and Amble examples [51].Source: §6.4 · pp. 95–96

6.4.1 Universal Teleo-Reactive programs and FTS BTs

• BT analysis provides a richer Teleo-Reactive guarantee by modeling execution time and continuous-state dynamics while accommodating imperfect sensing and actuation.This extends the strong assumptions used in Lemma 6.5 and enables control-theoretic analysis of Teleo-Reactive designs.Source: §6.4.1 · p. 97
• The original Universal Teleo-Reactive guarantee is incomplete because actions can violate their current condition before satisfying a lower-numbered condition, breaking progress toward the goal.The BT formulation instead requires attraction-region conditions; under the illustrative assumptions, the goal is reached in less than τ0 = τ1 + τ2 time units when S2 ⊂ R′1.Source: §6.4.1 · p. 97
• The stronger regression property requires every action ai to reach some earlier condition cj without ever violating its own condition ci.This prevents the chain of decreasing condition numbers from being broken.Source: §6.4.1 · p. 97

Get All Action Templates

• In dynamic environments, PA-BT extends plans to remove newly blocking obstacles, then skips obsolete recovery actions when conditions change, preserving continual execution without replanning.The robot can drop and recover an object, handle an obstructing sphere, and resume the original task through BT reactivity.Source: Chapter 7 Behavior Trees and Automated… · p. 100, Get All Action Templates · p. 107, §7.1.3 · p. 107

7.1 The Planning and Acting (PA-BT) approach

• PA-BT combines planning in infinite state spaces with BT reactivity and modularity, allowing agents to monitor, update, and extend plans while acting.The approach addresses hierarchical and continual deliberation and adds improved reactivity, safety, and fault-tolerance compared with HPN.Source: §7.1 · p. 100

7.1.1 Algorithm Overview

• PA-BT incrementally replaces failed conditions with PPA behavior trees whose preconditions, actions, and fallbacks expand until an executable action is available.The process starts from goal constraints and repeatedly expands conditions, producing successive BTs until the final tree can execute the task.Source: §7.1.1 · p. 104

Refine Actions (Algorithm 5 Line 5)

• PA-BT’s action templates specify descriptive preconditions and effects, which are mapped online to executable action primitives using a Reachability Graph for efficient sampling.This mapping connects what an action should accomplish with how it is operationally performed.Source: Refine Actions (Algorithm 5 Line 5) · p. 105
• When an action refinement becomes invalid, PA-BT uses breadth-first search to expand failed conditions and re-refines the tree; multiple valid actions are retained as fallback alternatives.The approach guarantees finite expansion under the stated assumptions but does not seek the optimal action.Source: Refine Actions (Algorithm 5 Line 5) · p. 105

Conflicts and Increases in Priority (Algorithm 5 Lines 11 and 12)

• PA-BT resolves conflicts between newly added actions and earlier effects by moving the new subtree leftward, incrementally increasing its execution priority until the tree is feasible.Under certain assumptions, a feasible tree is proved to exist.Source: Conflicts and Increases in Priority… · p. 106

7.1.4 Algorithm Execution on Graphs

• On a graph shortest-path example, PA-BT expands conditions in breadth-first order and executes the resulting path identically to graph BFS, while targeting more complex problems.The execution reaches the goal through the sequence s0 →s1, s1 →s3, and s3 →sg.Source: §7.1.4 · p. 109

7.1.5 Algorithm Execution on an existing Example

• The chapter also applies PA-BT to a more complex example adapted from prior work.This application is introduced but its findings are not included in the supplied passage.Source: §7.1.5 · p. 110
• PA-BT continually monitors execution, automatically recovering from changed conditions and prioritizing conflict-free subtrees without requiring replanning.In the example, it re-picks a slipped object, abandons an obstructed subplan, and accepts the cost of non-optimal actions to avoid extensive modeling and deliberation.Source: §7.1.5 · p. 112

7.1.6 Reactiveness

• PA-BT reacts within a bounded time by evaluating affected conditions and control nodes, enabling subgoal re-satisfaction, preemption, and exploitation of externally achieved subgoals without replanning.Examples show recovery after an object slips, expansion to remove a newly blocking object, and skipping work when another agent removes an obstruction.Source: §7.1.6 · pp. 117–118

7.1.7 Safety

• Safety is enforced by adding safety-critical sub-BTs before plan expansion, and all resulting PA-BT expansions preserve the specified safety guarantee.A temperature-monitoring subtree preempts actions at TMAX and waits for cooling below that threshold, using hysteresis to prevent immediate restart.Source: §7.1.7 · pp. 118–119

7.1.8 Fault Tolerance

• PA-BT provides fault tolerance by placing alternative actions in prioritized Fallback compositions, allowing execution to switch options after failure without replanning or extending the tree.With two robot arms, a failed grasp using one gripper directly triggers an attempt with the other.Source: §7.1.8 · p. 119

7.1.9 Complex Execution on Realistic Robots

• Realistic-robot experiments in V-REP demonstrate PA-BT on dynamic, unpredictable environments and long action sequences, including continued demonstrations of reactiveness, safety maintenance, and fault tolerance.The evaluation uses KUKA Youbot and ABB Yumi platforms with in-house low-level controllers and an open-source BT library.Source: §7.1.9 · p. 120

7.1.9.1 KUKA Youbot experiments

• KUKA Youbot experiments show recovery from grasp loss, battery depletion, arm failure, and environmental changes while completing the placement task.The robot re-executes grasping, switches to charging, uses an auxiliary arm, expands plans for new obstacles, and skips subplans when external robots remove obstacles.Source: §7.1.9.1 · pp. 120, 123, 125, 127

7.1.9.2 ABB Yumi experiments

• ABB Yumi experiments demonstrate long-horizon cellphone assembly requiring repeated transfers between two grippers to reorient parts for assembly.The manipulation strategy compensates for simple parallel grippers that cannot perform dexterous reorientation directly.Source: §7.1.9.2 · p. 130

7.2 Planning using A Behavior Language (ABL) / 7.2.1 An ABL Agent

• ABL supports planning and acting across multiple time scales through a dynamically extended execution tree containing goals, sequential or parallel behaviors, actions, mental actions, sensors, and working memory.The Pac-Man example combines short-term ghost avoidance with the long-term goal of eating all pills; the initial tree contains handleGhosts and eatAllPills subgoals.Source: §7.2 · p. 133, §7.2.1 · p. 134

7.2.1 An ABL Agent

• ABL represents behaviors with preconditions, conflicts, and spawngoals: preconditions gate selection, conflicts prioritize shared actuators, and spawngoals lazily expand needed subgoals.Unlike greedy subgoal instructions, spawngoals defer expansion until the spawned goal is first needed.Source: §7.2.1 · pp. 134–135

7.2.2 The ABL Planning Approach

• The ABL planning algorithm translates each subgoal into a BT Sequence or Parallel node, converts preconditions and actions into condition and action nodes, and expands spawngoal placeholders when ticked.It first builds a parallel tree from the initial ABL tree and then extends it recursively; in Pac-Man, ghost-related branches remain unexpanded until ghostClose becomes true.Source: §7.2.2 · p. 137

7.2.3 Brief Results of a Complex Execution in StarCraft

• The ABL StarCraft agent achieved over 60% overall win rate against the built-in AI across three maps, three races, and 20 trials, while performing over 200 actions per minute.The evaluation combined low-level tactical tasks with high-level strategic reasoning.Source: §7.2.3 · p. 141, Table 7.1 · p. 141

7.3 Comparison between PA-BT and ABL

• PA-BT focuses on constructing BTs through planning, whereas ABL is a complete planning language that uses BTs for execution; PA-BT more explicitly exploits fallback constructs by expanding conditions into fallback-enabled PPAs.The comparison characterizes the approaches by their planning roles and treatment of fallback options.Source: §7.3 · p. 141

8.1 Genetic Programming Applied to BTs

• The GP framework evolves BT populations through subtree crossover, same-type node mutation, and reward-based selection across generations.Crossover swaps subtrees between BTs, mutation increases diversity, and selection assigns survival probabilities according to the reward function.Source: §8.1 · pp. 143–144
• BTs avoid the inconsistent logic structures that can arise when Genetic Programming crosses over finite-state machines.The BT representation preserves valid control and execution structure during subtree exchange, unlike the cited FSM crossover problem.Source: §8.1 · pp. 143–144

8.2 The GP-BT Approach

• GP-BT combines greedy single-action learning with GP fallback, reducing learning time versus pure GP while producing a fairly compact tree.GP is invoked only when no single action improves the reward; the resulting tree can also be simplified by generalizing situations with the same response.Source: §8.2 · p. 145, New BT · p. 148, §8.2.2.4 · p. 150

New BT

• GP-BT initializes a safety subtree, identifies the current situation, tests individual actions, invokes GP for combinations when needed, and adds or generalizes the learned response until the goal is reached.The safety subtree can override the learned tree; action responses are stored in fallback compositions, and duplicate responses are merged to reduce node count.Source: §8.2 · p. 145, New BT · p. 149, §8.2.2.2 · p. 149

8.2.4. Experimental Results

• The experiments apply GP-BT to Mario AI and to a KUKA Youbot, covering a complex dynamic benchmark and a real robot with partially known or unknown environments.The Mario evaluation uses cross-validation on different episodes of equal complexity, while the Youbot evaluation includes three environmental-knowledge conditions.Source: §8.2.4 · p. 150, §8.2.4.1 · pp. 151–152, §8.2.4.2 · p. 154

8.2.4.1 Mario AI

• In Mario AI, FSM size grows exponentially, GP-BT growth tends to decrease, and pure GP grows slowly because finding reward-improving candidates takes substantial time.The authors attribute GP-BT’s behavior to merging situations that require the same actions, while pure GP often constructs condition-heavy trees with few or no actions.Source: §8.2.4.1 · pp. 152–153
• GP-BT is the only compared method that reaches reward 1 within the execution time in both the simplest and most complex Mario AI scenarios.The comparison includes a FSM-based algorithm and a pure GP-based algorithm; Figure 8.8 reports reward and learned-tree complexity.Source: §8.2.4.1 · pp. 152–153, Figure 8.8 · p. 154

8.2.4.2 KUKA Youbot

• The KUKA Youbot application learns condition-to-action switching policies in simulation before execution on a real robot across corridor, context-dependent, and action-composition scenarios.The setup uses camera-recognized objects mapped into V-REP; GP-BT learns different responses to the same object in different situations and can compose actions to reach a goal.Source: §8.2.4.2 · pp. 154–155

8.2.5 Other Approaches using GP applied to BTs

• GP-based BT synthesis includes grammar-constrained BehaviorBlocks for Mario AI and mutation-based evolution of sensory-motor BTs for micro air vehicles.The grammatical-evolution approach placed fourth in the 2010 Mario AI gameplay track, while pure GP used micro and macro mutations on randomly generated BTs.Source: §8.2.5 · p. 155

8.3.1 Summary of Q-Learning

• Q-learning updates state-action values from observed rewards and new states, converging to an optimal reward-maximizing policy when every admissible pair is updated infinitely often.Hierarchical RL uses Semi-Markov Decision Processes and options to divide problems into subproblems and represent temporally extended actions.Source: §8.3.1 · p. 156

8.3.2 The RL-BT Approach

• RL-BT replaces selected nodes in a manually designed BT with Learning Action or Learning Control Flow nodes that use rewards to improve local behavior.Learning Action nodes encapsulate Q-learning, while Learning Control Flow nodes learn the ordering of Fallback children; the formalization connects these nodes to hierarchical options.Source: §8.3.2 · pp. 156–157

8.3.3 Experimental Results

• In the single-learning-node experiment, the agent’s extinguisher-selection accuracy converged to 100%.The state was fire type, available actions were extinguisher choices, and rewards were 10 for putting out the fire and −10 otherwise.Source: §8.3.3 · p. 158, Figure 8.9 · p. 158
• RL-BT achieved 97-99% accuracy in the two-learning-node experiment, while trial-and-error in action ordering caused the deviation from 100%.The experiment used a learning Action node for extinguisher selection and a Learning Control Flow node for ordering room actions.Source: §8.3.3 · p. 159

8.4 Comparison between GP-BT and RL-BT

• GP-BT evolves the BT structure from a global reward, whereas RL-BT preserves a user-specified structure and learns designated nodes using local states, actions, and rewards.RL-BT uses modular subproblems to address dimensionality but requires more structural and local task specification than GP-BT.Source: §8.4 · p. 159

8.5 Learning from Demonstration applied to BTs

• Learning from demonstration converts designer action traces into editable BT behavior, but direct trace mapping can make BTs very large; pattern-based generalization reduces size and improves readability.Trained BTs replace a Trainer Node with a machine-generated sub-behavior that selects tasks matching the game state and stored traces.Source: §8.5 · p. 160

Chapter 9 Stochastic Behavior Trees

• SBTs support reliability analysis of arbitrary complex BT plans in terms of execution-time distributions and success probabilities, extending results previously published in.The chapter organizes this analysis around SBT definitions, DTMC transformation, reliability computation, and examples.Source: Chapter 9 Stochastic Behavior Trees · p. 161

9.1 Stochastic BTs

• BT modularity lets probabilistic measures such as Mean Time to Succeed, Mean Time to Fail, and probabilities over time carry across hierarchical compositions.The chapter identifies modularity and hierarchy as the basis for scalability.Source: §9.1 · p. 161, §9.1.2 · p. 170

9.1.1 Markov Chains and Markov Processes

• Markov theory models memoryless plan execution with DTMCs for action sequences and CTMCs for state transition rates.The chapter defines transition probabilities for DTMCs and transition rates, generator matrices, and sojourn times for CTMCs.Source: §9.1.1 · pp. 162, 164

9.1.2 Formulation

• SBT formulation permits stochastic, deterministic, and hybrid actions with known outcome probabilities and specified temporal models, enabling recursive computation of subtree and whole-tree probabilistic descriptions.Stochastic action times use exponential distributions, deterministic actions use known success and failure times, and hybrid actions combine exponential and deterministic components.Source: §9.1.2 · pp. 165, 167, 170

9.2 Transforming a SBT into a DTMC

• The SBT-to-DTMC method represents each control-flow node by a marking vector of child outcomes, constructs its transition matrix from execution policies, and computes success and failure probabilities over time recursively.Analysis begins with leaves whose probabilistic parameters are known and progresses upward through the modular tree structure.Source: §9.2 · pp. 170–171
• Feasible events define reachable markings, which form the Marking Reachability Graph used to construct a DTMC for each Behavior Tree node.Fallback, Sequence, and Parallel nodes restrict child outcomes according to which children have been ticked and whether their success or failure conditions are already satisfied.Source: Feasibility condition in the Parallell… · p. 172, Feasibility condition in the Fallback… · p. 172, Feasibility condition in the Sequence… · p. 172

9.2.1 Computing Transition Properties of the DTMC

• The DTMC transition matrix assigns probabilities to jumps between reachable markings, while a CTMC with generator Q incorporates the average sojourn times of those markings.The general Parallel-node mapping is not depicted because it has many states and possible transitions.Source: §9.2.1 · pp. 172, 173, 175

9.3.1 Average sojourn time

• Average sojourn time is obtained from child outcome probabilities and rates; for multiple running children, their rates sum and the marking’s sojourn time is the inverse combined rate.An auxiliary CTMC represents the execution of the running child so that both outcome probabilities and time rates contribute to the calculation.Source: §9.3.1 · p. 175

9.3.2 Mean Time To Fail and Mean Time To Succeed

• MTTF and MTTS are computed from canonized transient-to-transient and transient-to-absorbing transitions, using mean visits before absorption and transition times.The transient-state transition matrix is nilpotent when transient states have no self-loops, so the expected visit counts are finite.Source: §9.3.2 · pp. 177–178

9.3.3 Probabilities Over Time

• Node success and failure probabilities over time equal the DTMC probability mass in success and failure markings, respectively.Given known probabilistic measures for child nodes, the procedure recursively computes each parent node’s DTMC and aggregates its success and failure states.Source: §9.3.4 · p. 178, §9.3.3 · p. 178

9.3.4 Stochastic Execution Times

• For stochastic execution times, time to succeed or fail is modeled as an exponential random variable with rate equal to the inverse MTTS or MTTF.The same probability-over-time proposition also applies to deterministic and hybrid Behavior Trees because the governing equation has a unique Carathéodory solution.Source: §9.3.4 · pp. 178–179

9.3.5 Deterministic Execution Times

• For deterministic execution times, success and failure probabilities remain unchanged between transition times, producing piecewise-constant evolution computed with a discrete-time system and zero-order hold.This avoids computational difficulties associated with directly handling Dirac delta functions.Source: §9.3.5 · pp. 179–180

9.4 Examples

• The examples demonstrate closed-form probabilistic parameters, deterministic-time calculations, Monte Carlo verification against analytical results, and differing performance metrics for equivalent Behavior Trees.The complex example is explicitly used both to verify the approach numerically and to show how structural changes in a stochastic Behavior Tree affect performance metrics.Source: §9.4 · pp. 181, 183, 185
• The two-armed robot example models alternative search locations and one- versus two-handed grasps, whose differing likelihoods and checking times yield multiple possible performance trade-offs.The selected plan is represented as a Stochastic Behavior Tree for finding and collecting objects on the floor, in drawers, or in a closet.Source: §9.4 · p. 185, Figure 9.17 · p. 185
• Analytical estimates for the behavior tree matched approximately 80,000 ROS Monte Carlo runs, with all estimates within 0.18% of analytical results.The comparison covered tree and subtree success or failure probabilities, mean times to success, and mean times to failure.Source: §9.4 · pp. 185–186, Table 9.1 · p. 186, Table 9.2 · p. 186
• Stochastic timing produces the largest deviation in failure probabilities: the cumulative failure probability rises immediately, unlike deterministic timing, which remains zero until required fallbacks have failed.The comparison uses accumulated success, failure, and running probabilities for the root and subtrees.Source: §9.4 · p. 186, Figure 9.20 · p. 189, Figure 9.21 · p. 190
• After 100 seconds, success probability is about 30% when searching drawers first versus about 20% when searching the floor first, making drawers-first optimal.Permuting fallback order preserves asymptotic probabilities for equivalent behavior trees, even though finite-time performance changes.Source: §9.4 · pp. 186–187, Figure 9.22 · p. 191

• BTs offer a unified framework spanning classical formulations, extensions, theoretical analyses, stochastic execution estimates, design principles, planning, and learning.The analysis addresses efficiency, safety, robustness, execution time, and success probabilities.Source: Chapter 10 Concluding Remarks · p. 193
• Modularity is central to BTs’ success because consistent interfaces reduce dependencies and make complex systems easier to develop, test, maintain, and reuse.Each tree level shares the interface of a single action, while internal nodes keep action implementations independent of context and usage order.Source: Chapter 10 Concluding Remarks · p. 193
• BTs constitute a promising control architecture for computer game AI and robotics, although their varied formulations leave substantial work toward a unified field.The book seeks to unify the field’s diverse ideas, algorithms, and applications.Source: Chapter 10 Concluding Remarks · p. 193