1932
0
  1. Home
  2. A-Z Publications
  3. Annual Review of Control, Robotics, and Autonomous Systems
  4. Volume 5, 2022
  5. Article

Annual Review of Control, Robotics, and Autonomous Systems

Volume 5, 2022

Behavior Trees in Robot Control Systems

Abstract

In this article, we provide a control-theoretic perspective on the research area of behavior trees in robotics. The key idea underlying behavior trees is to make use of modularity, hierarchies, and feedback in order to handle the complexity of a versatile robot control system. Modularity is a well-known tool to handle software complexity by enabling the development, debugging, and extension of separate modules without detailed knowledge of the entire system. A hierarchy of such modules is natural, since robot tasks can often be decomposed into a hierarchy of subtasks. Finally, feedback control is a fundamental tool for handling uncertainties and disturbances in any low-level control system, but in order to enable feedback control on the higher level, where one module decides what submodule to execute, information regarding the progress and applicability of each submodule needs to be shared in the module interfaces. We describe how these three concepts can be used in theoretical analysis, practical design, and extensions and combinations with other ideas from control theory and robotics.

Keyword(s): autonomous system, behavior trees, feedback, hierarchical modularity, modularity, robustness, task switching, transparency
Loading

Article metrics loading...

/content/journals/10.1146/annurev-control-042920-095314
2022-05-03
2024-05-14
Loading full text...

Full text loading...

/deliver/fulltext/control/5/1/annurev-control-042920-095314.html?itemId=/content/journals/10.1146/annurev-control-042920-095314&mimeType=html&fmt=ahah

Literature Cited

  1. 1. 
    Blume M, Appel AW. 1999. Hierarchical modularity. ACM Trans. Program. Lang. Syst. 21:813–47
     [Google Scholar]
  2. 2. 
    Sacerdoti ED. 1975. A structure for plans and behavior Tech. Note 109 SRI Int. Menlo Park, CA:
  3. 3. 
    Erol K, Hendler J, Nau DS. 1994. UMCP: a sound and complete procedure for hierarchical task-network planning. Proceedings of the Second International Conference on Artificial Intelligence Planning Systems249–54 Palo Alto, CA: AAAI Press
  4. 4. 
    Mateas M, Stern A. 2002. A behavior language for story-based believable agents. IEEE Intell. Syst. 17:39–47
     [Google Scholar]
  5. 5. 
    Isla D. 2005. Handling complexity in the Halo 2 AI. Paper presented at the Game Developers Conference San Francisco: Mar. 7–11. https://www.gdcvault.com/play/1020270/Managing-Complexity-in-the-Halo
    [Google Scholar]
  6. 6. 
    Florez-Puga G, Gomez-Martin MA, Gomez-Martin PP, Diaz-Agudo B, Gonzalez-Calero PA. 2009. Query-enabled behavior trees. IEEE Trans. Comput. Intell. AI Games 1:298–308
     [Google Scholar]
  7. 7. 
    Ögren P. 2012. Increasing modularity of UAV control systems using computer game behavior trees. AIAA Guidance, Navigation, and Control Conference pap. 2012-4458 Reston, VA: Am. Inst. Aeronaut. Astronaut.
  8. 8. 
    Bagnell JA, Cavalcanti F, Cui L, Galluzzo T, Hebert M et al. 2012. An integrated system for autonomous robotics manipulation. 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems2955–62 Piscataway, NJ: IEEE
  9. 9. 
    Wikipedia 2020. Behavior tree. Wikipedia https://en.wikipedia.org/wiki/Behaviorree
    [Google Scholar]
  10. 10. 
    Harel D. 1987. Statecharts: a visual formalism for complex systems. Sci. Comput. Program. 8:231–74
     [Google Scholar]
  11. 11. 
    Biggar O, Zamani M, Shames I. 2021. An expressiveness hierarchy of behavior trees and related architectures. IEEE Robot. Autom. Lett. 6:5397–404
     [Google Scholar]
  12. 12. 
    Iovino M, Scukins E, Styrud J, Ögren P, Smith C. 2020. A survey of behavior trees in robotics and AI. arXiv:2005.05842 [cs.RO]
  13. 13. 
    Colledanchise M, Ögren P. 2018. Behavior Trees in Robotics and AI: An Introduction Boca Raton, FL: CRC
  14. 14. 
    Colledanchise M, Ögren P. 2017. How behavior trees modularize hybrid control systems and generalize sequential behavior compositions, the subsumption architecture, and decision trees. IEEE Trans. Robot. 33:372–89
     [Google Scholar]
  15. 15. 
    Ögren P. 2020. Convergence analysis of hybrid control systems in the form of backward chained behavior trees. IEEE Robot. Autom. Lett. 5:6073–80
     [Google Scholar]
  16. 16. 
    Sprague CI, Ögren P. 2021. Continuous-time behavior trees as discontinuous dynamical systems. arXiv:2109.01575 [eess.SY]
  17. 17. 
    Colledanchise M, Natale L. 2021. On the implementation of behavior trees in robotics. IEEE Robot. Autom. Lett. 6:5929–36
     [Google Scholar]
  18. 18. 
    Cortes J. 2008. Discontinuous dynamical systems. IEEE Control Syst. Mag. 28:336–73
     [Google Scholar]
  19. 19. 
    Filippov AF. 1988. Differential Equations with Discontinuous Righthand Sides: Control Systems Amsterdam: Springer
  20. 20. 
    Biggar O, Zamani M, Shames I. 2020. On modularity in reactive control architectures, with an application to formal verification. arXiv:2008.12515 [cs.AI]
  21. 21. 
    Gallai T. 1967. Transitiv orientierbare Graphen. Acta Math. Acad. Sci. Hung. 18:25–66
     [Google Scholar]
  22. 22. 
    Watson AH, McCabe TJ. 1996. Structured testing: a testing methodology using the cyclomatic complexity metric Spec. Publ. 500-235 Natl. Inst. Stand. Technol. Gaithersburg, MD:
  23. 23. 
    Burridge RR, Rizzi AA, Koditschek DE. 1999. Sequential composition of dynamically dexterous robot behaviors. Int. J. Robot. Res. 18:534–55
     [Google Scholar]
  24. 24. 
    Conner DC, Choset H, Rizzi AA 2006. Integrated planning and control for convex-bodied nonholonomic systems using local feedback control policies. Robotics: Science and Systems II GS Sukhatme, S Schaal, W Burgard, D Fox 57–64 Cambridge, MA: MIT Press
     [Google Scholar]
  25. 25. 
    Reist P, Tedrake R. 2010. Simulation-based LQR-trees with input and state constraints. 2010 IEEE International Conference on Robotics and Automation5504–10 Piscataway, NJ: IEEE
  26. 26. 
    Paxton C, Ratliff N, Eppner C, Fox D. 2019. Representing robot task plans as robust logical-dynamical systems. 2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)5588–95 Piscataway, NJ: IEEE
  27. 27. 
    Ames AD, Coogan S, Egerstedt M, Notomista G, Sreenath K, Tabuada P. 2019. Control barrier functions: theory and applications. 2019 18th European Control Conference (ECC)3420–31 Piscataway, NJ: IEEE
     [Google Scholar]
  28. 28. 
    Ögren P. 2006. Autonomous UCAV strike missions using behavior control Lyapunov functions. AIAA Guidance, Navigation, and Control Conference pap. 2006-6197 Reston, VA: Am. Inst. Aeronaut. Astronaut.
  29. 29. 
    Özkahraman, Ögren P. 2020. Combining control barrier functions and behavior trees for multi-agent underwater coverage missions. 2020 59th IEEE Conference on Decision and Control (CDC)5275–82 Piscataway, NJ: IEEE
  30. 30. 
    Endsley MR. 2015. Autonomous horizons: system autonomy in the Air Force – a path to the future. Volume I: human-autonomy teaming Tech. Rep. AF/ST TR 15-01 Off. Chief Sci., US Air Force Washington, DC:
  31. 31. 
    Paxton C, Jonathan F, Hundt A, Mutlu B, Hager GD 2017. User experience of the CoSTAR system for instruction of collaborative robots. arXiv:1703.07890 [cs.RO]
  32. 32. 
    Vinyals O, Babuschkin I, Czarnecki WM, Silver D. 2019. Grandmaster level in StarCraft II using multi-agent reinforcement learning. Nature 575:350–54
     [Google Scholar]
  33. 33. 
    Pereira RDP, Engel PM. 2015. A framework for constrained and adaptive behavior-based agents. arXiv:1506.02312 [cs.AI]
  34. 34. 
    Kartasev M. 2019. Integrating reinforcement learning into behavior trees by hierarchical composition MS Thesis KTH R. Inst. Technol. Stockholm:
  35. 35. 
    Sprague CI, Ögren P. 2018. Adding neural network controllers to behavior trees without destroying performance guarantees. arXiv:1809.10283 [cs.RO]
  36. 36. 
    Dey R, Child C. 2013. QL-BT: enhancing behaviour tree design and implementation with Q-learning. 2013 IEEE Conference on Computational Intelligence in Games (CIG) Piscataway, NJ: IEEE https://doi.org/10.1109/CIG.2013.6633623
    [Crossref]
  37. 37. 
    Fu Y, Qin L, Yin Q. 2016. A reinforcement learning behavior tree framework for game AI. Proceedings of the 2016 International Conference on Economics, Social Science, Arts, Education and Management Engineering573–79 Dordrecht, Neth: Atlantis
     [Google Scholar]
  38. 38. 
    Zhang Q, Sun L, Jiao P, Yin Q 2017. Combining behavior trees with MAXQ learning to facilitate CGFs behavior modeling. 2017 4th International Conference on Systems and Informatics (ICSAI)525–31 Piscataway, NJ: IEEE
  39. 39. 
    Zhu X. 2019. Behavior tree design of intelligent behavior of non-player character (NPC) based on Unity3D. J. Intell. Fuzzy Syst. 37:6071–79
     [Google Scholar]
  40. 40. 
    Hannaford B, Hu D, Zhang D, Li Y. 2016. Simulation results on selector adaptation in behavior trees. arXiv:1606.09219 [cs.RO]
  41. 41. 
    Whitley D. 1994. A genetic algorithm tutorial. Stat. Comput. 4:65–85
     [Google Scholar]
  42. 42. 
    Rothlauf F, Oetzel M 2006. On the locality of grammatical evolution. Genetic Programming: 9th European Conference, EuroGP 2006 P Collet, M Tomassini, M Ebner, S Gustafson, A Ekárt 320–30 Berlin: Springer
     [Google Scholar]
  43. 43. 
    Luke S, Panait L 2006. A comparison of bloat control methods for genetic programming. Evol. Comput. 14:309–44
     [Google Scholar]
  44. 44. 
    Colledanchise M, Parasuraman R, Ögren P. 2019. Learning of behavior trees for autonomous agents. IEEE Trans. Games 11:183–89
     [Google Scholar]
  45. 45. 
    Hallawa A, Schug S, Iacca G, Ascheid G 2020. Evolving instinctive behaviour in resource-constrained autonomous agents using grammatical evolution. Applications of Evolutionary Computation PA Castillo, JL Jiménez Laredo, F Fernández de Vega 369–83 Cham, Switz: Springer
     [Google Scholar]
  46. 46. 
    Lim CU, Baumgarten R, Colton S 2010. Evolving behaviour trees for the commercial game DEFCON. Applications of Evolutionary Computation D Hutchison, GN Yannakakis 100–10 Berlin: Springer
     [Google Scholar]
  47. 47. 
    Nicolau M, Perez-Liebana D, O'Neill M, Brabazon A. 2017. Evolutionary behavior tree approaches for navigating platform games. IEEE Trans. Comput. Intell. AI Games 9:227–38
     [Google Scholar]
  48. 48. 
    Iovino M, Styrud J, Falco P, Smith C 2020. Learning behavior trees with genetic programming in unpredictable environments. arXiv:2011.03252 [cs.RO]
  49. 49. 
    Paduraru C, Paduraru M. 2019. Automatic difficulty management and testing in games using a framework based on behavior trees and genetic algorithms. arXiv:1909.04368 [cs.AI]
  50. 50. 
    Styrud J, Iovino M, Norrlöf M, Björkman M, Smith C 2021. Combining planning and learning of behavior trees for robotic assembly. arXiv:2103.09036 [cs.LG]
  51. 51. 
    Neupane A, Goodrich M. 2019. Learning swarm behaviors using grammatical evolution and behavior trees. Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence S Krause 513–20 Calif: . Int. Joint Conf. Artif. Intell.
     [Google Scholar]
  52. 52. 
    Jones S, Studley M, Hauert S, Winfield A 2018. Evolving behaviour trees for swarm robotics. Distributed Autonomous Robotic Systems: The 13th International Symposium R Groß, A Kolling, S Berman, E Frazzoli, A Martinoli, et al. 487–501 Cham, Switz: Springer
     [Google Scholar]
  53. 53. 
    Martín F, Morelli M, Espinoza H, Lera FJR, Matellán V 2021. Optimized execution of PDDL plans using behavior trees. arXiv:2101.01964 [cs.RO]
  54. 54. 
    Colledanchise M, Almeida D, Ögren P. 2019. Towards blended reactive planning and acting using behavior trees. 2019 International Conference on Robotics and Automation8839–45 Piscataway, NJ: IEEE
     [Google Scholar]
  55. 55. 
    Tadewos TG, Shamgah L, Karimoddini A. 2019. Automatic safe behaviour tree synthesis for autonomous agents. 2019 IEEE 58th Conference on Decision and Control (CDC)2776–81 Piscataway, NJ: IEEE
  56. 56. 
    Tadewos TG, Shamgah L, Karimoddini A. 2019. On-the-fly decentralized tasking of autonomous vehicles. 2019 IEEE 58th Conference on Decision and Control (CDC)2770–75 Piscataway, NJ: IEEE
  57. 57. 
    Zhou H, Min H, Lin Y 2019. An autonomous task algorithm based on behavior trees for robot. 2019 2nd China Symposium on Cognitive Computing and Hybrid Intelligence (CCHI)64–70 Piscataway, NJ: IEEE
  58. 58. 
    Schwab P, Hlavacs H. 2015. Capturing the essence: towards the automated generation of transparent behavior models. Proceedings of the Eleventh Artificial Intelligence and Interactive Digital Entertainment Conference184–90 Reston, VA: Am. Inst. Aeronaut. Astronaut.
  59. 59. 
    Kuckling J, Ligot A, Bozhinoski D, Birattari M 2018. Behavior trees as a control architecture in the automatic modular design of robot swarms. Swarm Intelligence M Dorigo 30–43 Cham, Switz: Springer
     [Google Scholar]
  60. 60. 
    Neufeld X, Mostaghim S, Brand S 2018. A hybrid approach to planning and execution in dynamic environments through hierarchical task networks and behavior trees. Proceedings of the Fourteenth Artificial Intelligence and Interactive Digital Entertainment Conference201–7 Reston, VA: Am. Inst. Aeronaut. Astronaut.
  61. 61. 
    Rovida F, Grossmann B, Krüger V 2017. Extended behavior trees for quick definition of flexible robotic tasks. 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)6793–800 Piscataway, NJ: IEEE
  62. 62. 
    Segura-Muros JÁ, Fernández-Olivares J. 2017. Integration of an automated hierarchical task planner in ROS using behaviour trees. 2017 6th International Conference on Space Mission Challenges for Information Technology (SMC-IT)20–25 Piscataway, NJ: IEEE
  63. 63. 
    Hölzl M, Gabor T 2015. Reasoning and learning for awareness and adaptation. Software Engineering for Collective Autonomic Systems: The ASCENS Approach M Wirsing, M Hölzl, N Koch, P Mayer 249–90 Cham, Switz: Springer
     [Google Scholar]
  64. 64. 
    Colledanchise M, Murray RM, Ögren P. 2017. Synthesis of correct-by-construction behavior trees. 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)6039–46 Piscataway, NJ: IEEE
  65. 65. 
    Lan M, Lai S, Lee TH, Chen BM 2019. Autonomous task planning and acting for micro aerial vehicles. 2019 IEEE 15th International Conference on Control and Automation (ICCA)738–45 Piscataway, NJ: IEEE
  66. 66. 
    Biggar O, Zamani M. 2020. A framework for formal verification of behavior trees with linear temporal logic. IEEE Robot. Autom. Lett. 5:2341–48
     [Google Scholar]
/content/journals/10.1146/annurev-control-042920-095314
Loading
Behavior Trees in Robot Control Systems
Annual Review of Control, Robotics, and Autonomous Systems 5, 81 (2022); https://doi.org/10.1146/annurev-control-042920-095314
/content/journals/10.1146/annurev-control-042920-095314
/content/journals/10.1146/annurev-control-042920-095314
Loading

Data & Media loading...

  • Article Type: Review Article

Most Cited Most Cited RSS feed

This is a required field
Please enter a valid email address
Approval was a Success
Invalid data
An Error Occurred
Approval was partially successful, following selected items could not be processed due to error