Behavior Tree

Hierarchical Model

Behavior Trees sind weiterentwickelte endliche Automaten zur Steuerung von Computerspielen. Sie wurden ab dem Jahr 2000 eingesetzt und sind fester Bestandteil in Spiel-Engines wie der Unreal Engine.<ref name="unrealAPI" /> Auch das Robotik-Framework ROS enthält die SMACH-Engine, um Behavior-Tree-ähnliche Abläufe zu spezifizieren.<ref name="Bohren2011" /><ref name="Nguyen2013" />

Geschichte

Die Steuerung von Echtzeitsystemen wurde traditionell in der Kybernetik diskutiert.<ref name="Wiener1961" /> Relativ früh war klar, dass man eine Art von künstlicher Intelligenz benötigt, um Entscheidungen zu treffen. Wenn beispielsweise im Spiel Pong der Paddel bewegt wird, muss irgendwo spezifiziert sein, wann das zu geschehen hat und mit welcher Intensität. Geschichtlich sind Behavior Trees aus den "Hierarchical Finite State Machines" hervorgegangen. Es handelt sich um endliche Automaten, die um Unterfunktionen erweitert wurden.<ref name="Lim2010" /><ref name="klockner2013behavior" />

Behavior Trees in der Spieleprogrammierung kamen erstmals im Jahr 2005 in dem Ego-Shooter Halo 2 zum Einsatz.<ref name="gaudl2013behaviour" /> Zuvor wurden Vorläuferkonzepte ab den 1980ern in der Behaviorbased Robotik von Rodney Brooks verwendet.<ref name="Brooks1986" /> Brooks war unzufrieden mit den klassischen Topdown-Planungssystemen, wie sie im PDDL und STRIPS Umfeld verwendet wurden, und suchte eine Methode, die ohne explizites Umgebungsmodell auskommt. Während man bei PDDL zunächst die Domäne umfassend spezifiziert und darin dann mit einem Solver nach einer Aktionsfolge sucht, geht man bei der Subsumption-Architektur genau umgekehrt vor: Man programmiert zuerst den Roboter und schaut dann, welche Probleme damit gelöst werden können.<ref name="Ouali2015" />

Automatentheorie

In der Informatik relativ gut erforscht sind Finite-States-Machines. Damit wird ein System so spezifiziert, dass es in genau einem Zustand sein kann. Finite-States-Machines sind deshalb so verbreitet, weil von der Hardwareseite Digitalschaltungen nach dieser Methode aufgebaut sind. Dieses Konzept lässt sich auf Echtzeitsysteme übertragen. Man spricht dann von „timed automation“.<ref name="atterer2001hybride" /> Bei Behavior Trees handelt es sich um eine vereinfachte Programmiermethode. Es können ähnliche Aufgaben bewältigt werden, wie mit einer Finite-State-Maschine. Der Fachbegriff lautet „timed Behavior Tree“, was eine Tautologie darstellt. Behavior Trees werden ausschließlich für Echtzeitsysteme verwendet, sind also immer mit einem Timer versehen.<ref name="Colvin2007" />

Praktische Realisierung

In der Game-Engine Unity werden Behavior Trees als grafischer Prozessflow realisiert.<ref name="Maggiorini2013" /> Der Entwickler kann mit der Maus neue Unterfunktionen einfügen und if-then-Bedingungen formulieren. Man kann Behavior Trees aber auch rein textuell in einer Hochsprache wie Modelica implementieren, sie sind dann ähnlich aufgebaut wie ein normales Computerprogramm. Inhaltlich werden sie jedoch für Prozess-Steuerungsaufgaben eingesetzt und erzeugen zeitlich abgestimmte Abläufe.<ref name="myers2011comodeling" />

Codebeispiel in Python

<syntaxhighlight lang="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

</syntaxhighlight>

Weiterentwicklungen

Es gibt Bestrebungen, das ursprüngliche Behavior-Tree-Konzept zu erweitern. GOAP (Goal-Oriented Action Planning) ist ein Planungssystem, bei dem ein Solver automatisch die passenden Einzelbefehle ermittelt.<ref name="bjarnolf2008threat" /> Im Bereich Reinforcement Learning werden Behavior Trees durch maschinelles Lernen erzeugt.<ref name="Perez2011" /> Auch hier ist die Intention, die manuelle Erstellung von Code zu vermeiden. In der Domäne Computerspiele sind sogenannte „Behavior Objects“ im Gespräch. Damit würde das Behavior-Tree-Konzept ergänzt um objektorientierte Elemente, wodurch man von der strukturierten Programmierung hin zur Verwendung von Klassen wechseln würde.<ref name="cerny2016using">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 and AI in Games IEEE. 2016, doi:10.1109/tciaig.2016.2528499 (arxiv.org [PDF; 731 kB]). </ref>

Einzelnachweise

<references> <ref name="unrealAPI"> Epic Games: Behavior Trees - Unreal Engine Dokumentation. (unrealengine.com).  </ref> <ref name="atterer2001hybride"> Atterer, Richard: Hybride automaten. In: TU München, Hauptseminar Design hybrider, eingebetteter Systeme. 2001 (atterer.org (Memento vom 11. Februar 2017 im Internet Archive) [PDF; 222 kB]).  </ref> <ref name="bjarnolf2008threat"> 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; 793 kB]).  </ref> <ref name="Bohren2011"> 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 (Memento vom 11. Februar 2017 im Internet Archive) [PDF; 1,8 MB]).  </ref> <ref name="Brooks1986"> 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). Band 2, 1986, S. 14–23, doi:10.1109/jra.1986.1087032 (mit.edu [PDF; 1,7 MB]).  </ref> <ref name="Colvin2007"> Robert Colvin and Lars Grunske and Kirsten Winter: Probabilistic Timed Behavior Trees. In: Lecture Notes in Computer Science Springer Nature. 2007, S. 156–175, doi:10.1007/978-3-540-73210-5_9 (amazonaws.com [PDF; 32 kB]).  </ref> <ref name="gaudl2013behaviour"> Gaudl, Swen E and Davies, Simon and Bryson, Joanna J: Behaviour oriented design for real-time-strategy games. In: FDG. 2013, S. 198--205 (cs.bath.ac.uk (Memento vom 13. Mai 2014 im Internet Archive) [PDF; 747 kB]).  </ref> <ref name="klockner2013behavior"> Klöckner, Andreas: Behavior trees for UAV mission management. In: INFORMATIK 2013: Informatik angepasst an Mensch, Organisation und Umwelt Köllen Druck+ Verlag GmbH, Bonn. 2013, S. 57--68 (dlr.de [PDF; 460 kB]).  </ref> <ref name="Lim2010"> Chong-U Lim and Robin Baumgarten and Simon Colton: Evolving Behaviour Trees for the Commercial Game DEFCON. In: Applications of Evolutionary Computation Springer Nature. 2010, S. 100–110, doi:10.1007/978-3-642-12239-2_11 (mit.edu [PDF; 492 kB]).  </ref> <ref name="Maggiorini2013"> 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.  </ref> <ref name="myers2011comodeling"> 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. Nr. 056, 2011, S. 97–106 (liu.se [PDF; 1,1 MB]).  </ref> <ref name="Nguyen2013"> 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 (smartech.gatech.edu (Memento vom 11. Februar 2017 im Internet Archive) [PDF; 1,8 MB]).  </ref> <ref name="Ouali2015"> Lydia Ould Ouali and Charles Rich and Nicolas Sabouret: Plan Recovery in Reactive HTNs Using Symbolic Planning. In: Artificial General Intelligence Springer Nature. 2015, S. 320–330, doi:10.1007/978-3-319-21365-1_33 (semanticscholar.org [PDF; 4,0 MB]).  </ref> <ref name="Perez2011"> Diego Perez and Miguel Nicolau and Michael O’Neill and Anthony Brabazon: Evolving Behaviour Trees for the Mario AI Competition Using Grammatical Evolution. In: Applications of Evolutionary Computation Springer Nature. 2011, S. 123–132, doi:10.1007/978-3-642-20525-5_13 (researchrepository.ucd.ie (Memento vom 11. Februar 2017 im Internet Archive) [PDF; 389 kB]).  </ref> <ref name="Wiener1961"> 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).  </ref> </references>