Behavior Trees in Robotics and AI: An Introduction (Chapman & Hall/CRC Artificial Intelligence and Robotics Series)

"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" -- From the publisher Contents......Page 3 Preface......Page 8 Behavior Trees......Page 11 A SHORT HISTORY AND MOTIVATION OF BTs......Page 12 WHAT IS WRONG WITH FSMs? THE NEED FOR REAC- TIVENESS AND MODULARITY......Page 13 CLASSICAL FORMULATION OF BTs......Page 14 CREATING A BT FOR PAC-MAN FROM SCRATCH......Page 21 CREATING A BT FOR A MOBILE MANIPULATOR ROBOT......Page 23 USE OF BTs IN ROBOTICS AND AI......Page 26 FINITE STATE MACHINES......Page 31 HIERARCHICAL FINITE STATE MACHINES......Page 32 SUBSUMPTION ARCHITECTURE......Page 40 TELEO-REACTIVE PROGRAMS......Page 42 DECISION TREES......Page 43 ADVANTAGES AND DISADVANTAGES OF BEHAVIOR TREES......Page 46 IMPROVING READABILITY USING EXPLICIT SUCCESS CONDITIONS......Page 52 IMPROVING REACTIVITY USING IMPLICIT SEQUENCES......Page 53 IMPROVING SAFETY USING SEQUENCES......Page 54 CREATING DELIBERATIVE BTs USING BACKCHAINING......Page 55 CREATING UN-REACTIVE BTs USING MEMORY NODES......Page 57 CHOOSING THE PROPER GRANULARITY OF A BT......Page 58 PUTTING IT ALL TOGETHER......Page 60 Extensions of Behavior Trees......Page 63 STOCHASTIC BTs......Page 64 TEMPORARY MODIFICATION OF BTs......Page 65 OTHER EXTENSIONS OF BTs......Page 68 STATE-SPACE FORMULATION OF BTs......Page 69 EFFICIENCY AND ROBUSTNESS......Page 72 SAFETY......Page 76 EXAMPLES......Page 79 HOW BTs GENERALIZE DECISION TREES......Page 89 HOW BTs GENERALIZE THE SUBSUMPTION ARCHI- TECTURE......Page 92 HOWBTs GENERALIZE SEQUENTIAL BEHAVIOR COM- POSITIONS......Page 94 HOW BTs GENERALIZE THE TELEO-REACTIVE AP- PROACH......Page 95 Behavior Trees & Automated Planning......Page 98 THE PLANNING AND ACTING (PA-BT) APPROACH......Page 99 PLANNING USING A BEHAVIOR LANGUAGE......Page 132 COMPARISON BETWEEN PA-BT AND ABL......Page 140 GENETIC PROGRAMMING APPLIED TO BTs......Page 141 THE GP-BT APPROACH......Page 143 REINFORCEMENT LEARNING APPLIED TO BTs......Page 152 COMPARISON BETWEEN GP-BT AND RL-BT......Page 155 LEARNING FROM DEMONSTRATION APPLIED TO BTs......Page 156 Stochastic Behavior Trees......Page 157 STOCHASTIC BTs......Page 158 TRANSFORMING A SBT INTO A DTMC......Page 166 RELIABILITY OF A SBT......Page 170 EXAMPLES......Page 175 Concluding Remarks......Page 185 Biblio......Page 187 Index......Page 194