Behavior Trees in Robotics and Al Chapman & Hall/CRC Artificial Intelligence and Robotics Series Series Editor: Roman Yampolskiy Contemporary Artificial Intelligence Richard E. Neapolitan The Virtual Mind Designing the Logic to Approximate Human Thinking Niklas Hageback Intelligent Autonomy of UAVs Advanced Missions and Future Use Yasmina Bestaoui Sebbane Artificial Intelligence With an Introduction to Machine Learning, Second Edition Richard E. Neapolitan, Xia Jiang Artificial Intelligence and the Two Singularities Calum Chace Behavior Trees in Robotics and Al An Introduction Michele Colledanchise, Petter Ögren For more information about this series please visit: https://www.crcpress.com/Chapman--HallCRC-Artificial-Intelligence-and-Robotics- Series/book-series/ARTILRO Behavior Trees in Robotics and Al An Introduction Michele Colledanchise Petter Ögren CRC Press Taylor & Francis Group 6000 Broken Sound Parkway NW, Suite 300 Boca Raton, FL 33487-2742 © 2019 by Taylor & Francis Group, LLC CRC Press is an imprint of Taylor & Francis Group, an Informa business No claim to original U.S. Government works Printed on acid-free paper Version Date: 20180410 International Standard Book Number-13: 978-1-138-59373-2 (Hardback) This book contains information obtained from authentic and highly regarded sources. Reasonable efforts have been made to publish reliable data and information, but the author and publisher cannot assume responsibility for the validity of all materials or the consequences of their use. The authors and publishers have attempted to trace the copyright holders of all material reproduced in this publication and apologize to copyright holders if permission to publish in this form has not been obtained. If any copyright material has not been acknowledged please write and let us know so we may rectify in any future reprint. Except as permitted under U.S. Copyright Law, no part of this book may be reprinted, reproduced, transmitted, or utilized in any form by any electronic, mechanical, or other means, now known or hereafter invented, including photocopying, microfilming, and recording, or in any information storage or retrieval system, without written permission from the publishers. For permission to photocopy or use material electronically from this work, please access www.copyright.com (http://www.copyright.com/) or contact the Copyright Clearance Center, Inc. (CCC), 222 Rosewood Drive, Danvers, MA 01923, 978-750-8400. CCC is a not-for-profit organization that provides licenses and registration for a variety of users. For organizations that have been granted a photocopy license by the CCC, a separate system of payment has been arranged. Trademark Notice: Product or corporate names may be trademarks or registered trademarks, and are used only for identification and explanation without intent to infringe. Visit the Taylor & Francis Web site at http://www.taylorandfrancis.com and the CRC Press Web site at http://www.crcpress.com ToPaola MC ToGustav,JuliaandViktoria PÖ Contents Preface XIII CHAPTER 1(cid:4) 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 ExecutionexampleofaBT 10 1.3.2 Controlflownodeswithmemory 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 BTsinautonomousvehicles 18 1.6.2 BTsinindustrialrobotics 19 1.6.3 BTsintheAmazonpickingchallenge 21 1.6.4 BTsinsidethesocialrobotJIBO 22 CHAPTER 2(cid:4) HowBehaviorTreesGeneralizeandRelateto Earlier Ideas 23 2.1 FINITE STATE MACHINES 23 2.1.1 Advantagesanddisadvantages 23 2.2 HIERARCHICAL FINITE STATE MACHINES 24 2.2.1 Advantagesanddisadvantages 24 2.2.2 CreatingaFSMthatworkslikeaBT 29 2.2.3 CreatingaBTthatworkslikeaFSM 32 2.3 SUBSUMPTION ARCHITECTURE 32 VII VIII (cid:4) Contents 2.3.1 Advantagesanddisadvantages 33 2.3.2 HowBTsgeneralizethesubsumptionarchitecture 33 2.4 TELEO-REACTIVE PROGRAMS 34 2.4.1 Advantagesanddisadvantages 35 2.4.2 HowBTsgeneralizeteleo-reactiveprograms 35 2.5 DECISION TREES 35 2.5.1 Advantagesanddisadvantages 36 2.5.2 HowBTsgeneralizedecisiontrees 36 2.6 ADVANTAGESANDDISADVANTAGESOFBEHAVIOR TREES 38 2.6.1 Advantages 38 2.6.2 Disadvantages 42 CHAPTER 3(cid:4) 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(cid: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 DynamicexpansionofBTs 62 Contents IX (cid:4) CHAPTER 5(cid:4) 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 Robustnessandefficiency 73 5.4.2 Safety 77 5.4.3 AmorecomplexBT 80 CHAPTER 6(cid:4) 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 Universalteleo-reactiveprogramsandFTSBTs 91 CHAPTER 7(cid:4) Behavior Trees and Automated Planning 93 7.1 THE PLANNING AND ACTING (PA-BT) APPROACH 94 7.1.1 Algorithmoverview 96 7.1.2 Thealgorithmstepsindetail 98 7.1.3 Commentsonthealgorithm 101 7.1.4 Algorithmexecutionongraphs 101 7.1.5 Algorithmexecutiononanexistingexample 103 7.1.6 Reactiveness 111 7.1.7 Safety 112 7.1.8 Faulttolerance 113 7.1.9 Realisticcomplexexecution 114 7.1.9.1 KUKAYoubotexperiments 114 7.1.9.2 ABBYumiexperiments 124