Contents
Preface XIII
CHAPTER 1 What Are Behavior Trees? 3
1.1 A SHORT HISTORY AND MOTIVATION OF BTs 4
1.2 WHAT IS WRONG WITH FSMs? THE NEED FOR
REACTIVENESS AND MODULARITY 5
1.3 CLASSICAL FORMULATION OF BTs 6
1.3.1 Execution example of a BT 10
1.3.2 Control flow nodes with memory 11
1.4 CREATING A BT FOR PAC-MAN FROM SCRATCH 13
1.5 CREATING A BT FOR A MOBILE MANIPULATOR
ROBOT 15
1.6 USE OF BTs IN ROBOTICS AND AI 18
1.6.1 BTs in autonomous vehicles 18
1.6.2 BTs in industrial robotics 19
1.6.3 BTs in the Amazon picking challenge 21
1.6.4 BTs inside the social robot JIBO 22
CHAPTER 2 How Behavior Trees Generalize and Relate to
Earlier Ideas 23
2.1 FINITE STATE MACHINES 23
2.1.1 Advantages and disadvantages 23
2.2 HIERARCHICAL FINITE STATE MACHINES 24
2.2.1 Advantages and disadvantages 24
2.2.2 Creating a FSM that works like a BT 29
2.2.3 Creating a BT that works like a FSM 32
2.3 SUBSUMPTION ARCHITECTURE 32
2.3.1 Advantages and disadvantages 33
2.3.2 How BTs generalize the subsumption architecture 33
2.4 TELEO-REACTIVE PROGRAMS 34
2.4.1 Advantages and disadvantages 35
2.4.2 How BTs generalize teleo-reactive programs 35
2.5 DECISION TREES 35
2.5.1 Advantages and disadvantages 36
2.5.2 How BTs generalize decision trees 36
2.6 ADVANTAGES AND DISADVANTAGES OF BEHAVIOR
TREES 38
2.6.1 Advantages 38
2.6.2 Disadvantages 42
CHAPTER 3 Design Principles 45
3.1 IMPROVING READABILITY USING EXPLICIT
SUCCESS CONDITIONS 45
3.2 IMPROVING REACTIVITY USING IMPLICIT
SEQUENCES 46
3.3 HANDLING DIFFERENT CASES USING A DECISION
TREE STRUCTURE 47
3.4 IMPROVING SAFETY USING SEQUENCES 47
3.5 CREATING DELIBERATIVE BTs USING
BACKCHAINING 48
3.6 CREATING UN-REACTIVE BTs USING MEMORY
NODES 50
3.7 CHOOSING THE PROPER GRANULARITY OF A BT 51
3.8 PUTTING IT ALL TOGETHER 53
CHAPTER 4 Extensions of Behavior Trees 57
4.1 UTILITY BTs 58
4.2 STOCHASTIC BTs 58
4.3 TEMPORARY MODIFICATION OF BTs 59
4.4 OTHER EXTENSIONS OF BTs 62
4.4.1 Dynamic expansion of BTs 62
CHAPTER 5 Analysis of Efficiency, Safety, and
Robustness 63
5.1 STATE-SPACE FORMULATION OF BTs 63
5.2 EFFICIENCY AND ROBUSTNESS 66
5.3 SAFETY 70
5.4 EXAMPLES 73
5.4.1 Robustness and efficiency 73
5.4.2 Safety 77
5.4.3 A more complex BT 80
CHAPTER 6 Formal Analysis of How Behavior Trees
Generalize Earlier Ideas 83
6.1 HOW BTs GENERALIZE DECISION TREES 83
6.2 HOW BTs GENERALIZE THE SUBSUMPTION
ARCHITECTURE 86
6.3 HOW BTs GENERALIZE SEQUENTIAL BEHAVIOR
COMPOSITIONS 88
6.4 HOW BTs GENERALIZE THE TELEO-REACTIVE
APPROACH 89
6.4.1 Universal teleo-reactive programs and FTS BTs 91
CHAPTER 7 Behavior Trees and Automated Planning 93
7.1 THE PLANNING AND ACTING (PA-BT) APPROACH 94
7.1.1 Algorithm overview 96
7.1.2 The algorithm steps in detail 98
7.1.3 Comments on the algorithm 101
7.1.4 Algorithm execution on graphs 101
7.1.5 Algorithm execution on an existing example 103
7.1.6 Reactiveness 111
7.1.7 Safety 112
7.1.8 Fault tolerance 113
7.1.9 Realistic complex execution 114
7.1.9.1 KUKA Youbot experiments 114
7.1.9.2 ABB Yumi experiments 124
7.2 PLANNING USING A BEHAVIOR LANGUAGE 127
7.2.1 An ABL agent 127
7.2.2 The ABL planning approach 129
7.2.3 Brief results of a complex execution in StarCraft 134
7.3 COMPARISON BETWEEN PA-BT AND ABL 135
CHAPTER 8 Behavior Trees and Machine Learning 137
8.1 GENETIC PROGRAMMING APPLIED TO BTs 137
8.2 THE GP-BT APPROACH 139
8.2.1 Algorithm overview 140
8.2.2 The algorithm steps in detail 142
8.2.2.1 GetSituation (Line 5) 142
8.2.2.2 LearnSingleAction (Line 6) 143
8.2.2.3 LearnActionsUsingGP (Line 8) 143
8.2.2.4 Simplify (Line 11) 143
8.2.3 Pruning of ineffective sub-trees 143
8.2.4 Experimental results 143
8.2.4.1 Mario AI 144
8.2.4.2 KUKA Youbot 146
8.2.5 Other approaches using GP applied to BTs 148
8.3 REINFORCEMENT LEARNING APPLIED TO BTs 148
8.3.1 Summary of Q-Learning 148
8.3.2 The RL-BT approach 149
8.3.3 Experimental results 150
8.4 COMPARISON BETWEEN GP-BT AND RL-BT 151
8.5 LEARNING FROM DEMONSTRATION APPLIED
TO BTs 152
CHAPTER 9 Stochastic Behavior Trees 153
9.1 STOCHASTIC BTs 154
9.1.1 Markov chains and Markov processes 154
9.1.2 Formulation 157
9.2 TRANSFORMING A SBT INTO A DTMC 162
9.2.1 Computing transition properties of the DTMC 165
9.3 RELIABILITY OF A SBT 166
9.3.1 Average sojourn time 166
9.3.2 Mean time to fail and mean time to succeed 167
9.3.3 Probabilities over time 169
9.3.4 Stochastic execution times 169
9.3.5 Deterministic execution times 170
9.4 EXAMPLES 171
CHAPTER 10 Concluding Remarks 181
Bibliography 183
Index 191
Preface
This book is about behavior trees (BTs), a way to structure the behavior, or more
precisely the task switching, of an artificial agent such as a robot or a non-player
character in a computer game.
The problems regarding task switching are very similar in robotics and virtual
agent design. However, these problems have received far more attention from game
developers than from the robotics community. One reason for this is that designing
individual tasks, such as grasping, localization, and mapping are research topics of
their own in robotics, while being trivial in a virtual world. A game character does
not need to worry about real-world physics and mechanics, and is free to directly
access the positions of itself and other objects in some world coordinates, or setting
the position of an object to be the same as its hand. Thus it is not a coincidence that
BTs were invented in the game development community, while robotics researchers
were busy making robots able to execute individual tasks.
Modularity and reactivity, the two key features of BTs compared to other task
switching structures, are also very important in game development. A computer game
is an example of a very large software development project, and the importance of
modularity in software development is well known. Reactivity, or the ability of agents
to react to external events in general, and the actions of the human players in particular,
is also of key importance. But although switching structures have not been a
focus area in robotics, the need for a modular and reactive switching structure will
grow as robots become more capable in terms of individual task.
This book will guide you to the subject of BTs from simple topics, such as semantics
and design principles, to complex topics, such as learning and task planning.
For each topic we provide a set of examples, ranging from simple illustrations to realistic
complex behaviors, to enable the reader to successfully combine theory with
practice.
