Behavior Trees in Robotics and AI: An Introduction

by Michele Colledanchise, Petter Ögren

Overview

Behavior Trees (BTs) provide a way to structure the behavior of an artificial agent such as a robot or a non-player character in a computer game. Traditional design methods, such as finite state machines, are known to produce brittle behaviors when complexity increases, making it very hard to add features without breaking existing functionality. BTs were created to address this very problem, and enables the creation of systems that are both modular and reactive. Behavior Trees in Robotics and AI: An Introduction provides a broad introduction as well as an in-depth exploration of the topic, and is the first comprehensive book on the use of BTs.

This book introduces 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, the authors provide a set of examples, ranging from simple illustrations to realistic complex behaviors, to enable the reader to successfully combine theory with practice.

Starting with an introduction to BTs, the book then describes how BTs relate to, and in many cases, generalize earlier switching structures, or control architectures. These ideas are then used as a foundation for a set of efficient and easy to use design principles. The book then presents a set of important extensions and provides a set of tools for formally analyzing these extensions using a state space formulation of BTs.

With the new analysis tools, the book then formalizes the descriptions of how BTs generalize earlier approaches and shows how BTs can be automatically generated using planning and learning. The final part of the book provides 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.

This book targets a broad audience, including both students and professionals interested in modeling complex behaviors for robots, game characters, or other AI agents. Readers can choose at which depth and pace they want to learn the subject, depending on their needs and background.

Product Details

ISBN-13:	9780367571337
Publisher:	CRC Press
Publication date:	06/30/2020
Series:	Chapman & Hall/CRC Artificial Intelligence and Robotics Series
Pages:	206
Product dimensions:	6.12(w) x 9.19(h) x (d)

About the Author

Michele Colledanchise is currently a postdoctoral researcher in the iCub Facility at the Italian Institute of Technology, Genoa, Italy. He received his Ph.D. degree in computer science from the Royal Institute of Technology (KTH), Stockholm, Sweden, in 2017. In the spring of 2016, he visited the Control and Dynamical Systems, Californa Institute of Technology (Caltech), Pasadena, CA. His research interests include control systems, system architectures, and automated planning, with a strong focus on robotic applications.

Petter Ögren was born in Stockholm, Sweden, in 1974. He received theM.S. degree in engineering physics and the Ph.D. degree in applied mathematics from the Royal Institute of Technology (KTH), Stockholm, Sweden, in 1998 and 2003, respectively. In the fall of 2001, he visited the Mechanical Engineering Department, Princeton University, Princeton, NJ. From 2003 to 2012 he worked as a senior scientist and deputy research director in Autonomous Systems at the Swedish Defence Research Agency (FOI). He is currently an Associate Professor at the Robotics, Perception and Learning lab (RPL) at KTH. His research interests include robot control architectures and multi-agent coordination.

Table of 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 LearnSingle Action (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