Behavior Tree

from Wikipedia, the free encyclopedia
Hierarchical model

Behavior trees are further developed finite automata for controlling computer games . They were used from the year 2000 and are an integral part of game engines such as the Unreal Engine . The robotics framework ROS also contains the SMACH engine to specify behavior tree-like processes.

history

The control of real-time systems was traditionally discussed in cybernetics . It was clear relatively early on that you needed some kind of artificial intelligence to make decisions. If, for example, the paddle is moved in the game of pong , it must be specified somewhere when this has to happen and with what intensity. Historically, behavior trees have emerged from the "Hierarchical Finite State Machines". These are finite automata that have been expanded to include sub-functions .

Behavior trees in game programming were first used in 2005 in the first-person shooter Halo 2 . Previously, from the 1980s onwards, predecessor concepts were used in behavior-based robotics by Rodney Brooks . Brooks was dissatisfied with the classic topdown planning systems as they were used in the PDDL and STRIPS environment, and was looking for a method that does not require an explicit environment model. While with PDDL you first specify the domain comprehensively and then search for a sequence of actions with a solver , with the subsumption architecture you proceed in exactly the opposite way: you first program the robot and then see which problems can be solved with it.

Automata theory

Finite state machines have been researched relatively well in computer science. A system is specified in such a way that it can be in exactly one state. Finite-state machines are so widespread because, on the hardware side, digital circuits are built according to this method. This concept can be transferred to real-time systems. One then speaks of “timed automaton ”. Behavior Trees is a simplified programming method. Similar tasks can be performed as with a finite state machine. The technical term is "timed behavior tree", which is a tautology . Behavior trees are used exclusively for real-time systems, so they are always provided with a timer .

Practical implementation

In the game engine Unity , behavior trees are implemented as a graphic process flow. The developer can insert new sub-functions with the mouse and formulate if-then conditions. Behavior trees can also be implemented purely textually in a high-level language such as Modelica ; they are then structured in a similar way to a normal computer program. In terms of content, however, they are used for process control tasks and generate time-coordinated processes.

Code example in Python

class Behaviortree:
  def __init__(self):
    t = threading.Thread(target=self.taskmain)
    t.start()
  def taskmain():
    self.gehe_durch_tuer()
    time.sleep(1)
    self.schliesse_tuer()
  def gehe_durch_tuer(self):
    self.benutze_schluessel()
    self.druecke_tuerklinke()
  def schliesse_tuer(self):
    pass
  def benutze_schluessel(self):
    pass
  def druecke_tuerklinke(self):
    pass

Further developments

There are efforts to expand the original behavior tree concept. GOAP (Goal-Oriented Action Planning) is a planning system in which a solver automatically determines the appropriate individual commands. In the area of reinforcement learning , behavior trees are generated through machine learning . Again, the intention is to avoid the manual creation of code. In the domain of computer games, so-called “behavior objects” are being discussed, so that the behavior tree concept is supplemented by object-oriented elements, so that the transition is made from structured programming to the use of classes.

Individual evidence

  1. ↑ Epic Games: Behavior Trees - Unreal Engine Documentation . ( unrealengine.com ).
  2. ↑ Jonathan Bohren and Radu Bogdan Rusu and E. Gil Jones and Eitan Marder-Eppstein and Caroline Pantofaru and Melonee Wise and Lorenz Mosenlechner and Wim Meeussen and Stefan Holzer: Towards autonomous robotic butlers: Lessons learned with the {PR} 2 . In: 2011 {IEEE} International Conference on Robotics and Automation Institute of Electrical and Electronics Engineers ({IEEE}) . 2011, doi : 10.1109 / icra.2011.5980058 ( meloneewise.com [PDF]).
  3. ↑ Hai Nguyen and Matei Ciocarlie and Kaijen Hsiao and Charles C. Kemp: ROS commander (Rosco): Behavior creation for home robots . In: 2013 IEEE International Conference on Robotics and Automation Institute of Electrical and Electronics Engineers (IEEE) . 2013, doi : 10.1109 / icra.2013.6630616 ( gatech.edu [PDF]).
  4. ^ Norbert Wiener: Cybernetics, or control and communication in the animal and the machine (2nd ed.). In: American Psychological Association (APA) . 1961, doi : 10.1037 / 13140-000 ( hathitrust.org ).
  5. ↑ Chong-U Lim and Robin Baumgarten and Simon Colton: Evolving Behavior Trees for the Commercial Game DEFCON . In: Applications of Evolutionary Computation Springer Nature . 2010, p. 100--110 , doi : 10.1007 / 978-3-642-12239-2_11 ( with.edu [PDF]).
  6. ^ Klöckner, Andreas: Behavior trees for UAV mission management . In: INFORMATIK 2013: Computer science adapted to people, organization and the environment Köllen Druck + Verlag GmbH, Bonn . 2013, p. 57--68 ( dlr.de [PDF]).
  7. ↑ Gaudl, Swen E and Davies, Simon and Bryson, Joanna J: Behavior oriented design for real-time strategy games. In: FDG . 2013, p. 198-205 ( bath.ac.uk [PDF]).
  8. ^ R. Brooks: A robust layered control system for a mobile robot . In: IEEE Journal on Robotics and Automation Institute of Electrical and Electronics Engineers (IEEE) . tape 2 , no. 1 , 1986, pp. 14--23 , doi : 10.1109 / jra.1986.1087032 ( with.edu [PDF]).
  9. ^ Lydia Ould Ouali and Charles Rich and Nicolas Sabouret: Plan Recovery in Reactive HTNs Using Symbolic Planning . In: Artificial General Intelligence Springer Nature . 2015, p. 320-330 , doi : 10.1007 / 978-3-319-21365-1_33 ( semanticscholar.org [PDF]).
  10. ↑ Atterer, Richard: Hybrid automata . In: TU Munich, advanced seminar on the design of hybrid, embedded systems . 2001 ( atterer.org [PDF]).
  11. ↑ Robert Colvin and Lars Grunske and Kirsten Winter: Probabilistic Timed Behavior Trees . In: Lecture Notes in Computer Science Springer Nature . 2007, p. 156--175 , doi : 10.1007 / 978-3-540-73210-5_9 ( amazonaws.com [PDF]).
  12. ↑ Dario Maggiorini and and Laura Ripamonti and Samuele Panzeri: Follow the Leader: a Scalable Approach for Realistic Group Behavior of Roaming NPCs in MMO Games . In: Advances in Artificial Life, ECAL 2013 MIT Press - Journals . 2013, doi : 10.7551 / 978-0-262-31709-2-ch101 ( psu.edu [PDF]).
  13. ↑ Myers, Toby and Schamai, Wladimir and Fritzon, Peter: Comodeling revisited: Execution of behavior trees in modelica . In: Proceedings of the 4th International Workshop on Equation-Based Object-Oriented Modeling Languages ​​and Tools; Zurich; Switzerland; September 5; 2011 Linköping University Electronic Press . No. 056 , 2011, pp. 97-106 ( liu.se [PDF]).
  14. ↑ Bjarnolf, Philip and Gustavsson, Per M and Brax, Christoffer and Fredin, Mikael: Threat analysis using goal-oriented action planning . In: University of Skövde . 2008 ( researchgate.net [PDF]).
  15. ^ Diego Perez and Miguel Nicolau and Michael O'Neill and Anthony Brabazon: Evolving Behavior Trees for the Mario AI Competition Using Grammatical Evolution . In: Applications of Evolutionary Computation Springer Nature . 2011, p. 123--132 , doi : 10.1007 / 978-3-642-20525-5_13 ( online [PDF]). Evolving Behavior Trees for the Mario AI Competition Using Grammatical Evolution ( Memento of the original dated February 11, 2017 in the Internet Archive ) Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice.  @1@ 2Template: Webachiv / IABot / researchrepository.ucd.ie
  16. ↑ Cerny, Martin and Plch, Tomas and Marko, Matej and Gemrot, Jakub and Ondracek, Petr and Brom, Cyril: Using Behavior Objects to Manage Complexity in Virtual Worlds . In: IEEE Transactions on Computational Intelligence nd AI in Games IEEE . 2016, doi : 10.1109 / tciaig.2016.2528499 ( arxiv.org [PDF]).