Behavior Tree

Behavior Trees sind weiterentwickelte endliche Automaten zur Steuerung von Computerspielen. Sie wurden ab dem Jahr 2000 eingesetzt und sind fester Bestandteil in Gameengines wie der Unreal Engine. Auch das Robotik-Framework ROS enthält die SMACH-Engine, um Behavior-Tree-ähnliche Abläufe zu spezifizieren.

Hierarchical Model

Geschichte

Die Steuerung von Echtzeitsystemen wurde traditionell in der Kybernetik diskutiert. 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.

Behavior Trees in der Spieleprogrammierung kamen erstmals im Jahr 2005 in dem Ego-Shooter Halo 2 zum Einsatz. Zuvor wurden Vorläuferkonzepte ab den 1980ern in der Behaviorbased Robotik von Rodney Brooks verwendet. 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.

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“. 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.

Praktische Realisierung

In der Game-Engine Unity werden Behavior Trees als grafischer Prozessflow realisiert. 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.

Codebeispiel 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 

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. Im Bereich Reinforcement Learning werden Behavior Trees durch maschinelles Lernen erzeugt. Auch hier ist die Intention die manuelle Erstellung von Code zu vermeiden. In der Domäne Computerspiele sind sogenannten „Behavior Objects“ im Gespräch, damit wird das Behavior-Tree-Konzept ergänzt um objektorientierte Elemente, dass man also den Übergang vollzieht von der strukturierten Programmierung hin zur Verwendung von Klassen.

Einzelnachweise

1. Epic Games: Behavior Trees - Unreal Engine Dokumentation. (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 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]). 
6. 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]). 
7. Gaudl, Swen E and Davies, Simon and Bryson, Joanna J: Behaviour oriented design for real-time-strategy games. In: FDG. 2013, S. 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). Band 2, 1986, S. 14–23, doi:10.1109/jra.1986.1087032 (mit.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, S. 320–330, doi:10.1007/978-3-319-21365-1_33 (semanticscholar.org [PDF]). 
10. Atterer, Richard: Hybride automaten. In: TU München, Hauptseminar Design hybrider, eingebetteter Systeme. 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, S. 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. Nr. 056, 2011, S. 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 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 ( (Memento vom 11. Februar 2017 im Internet Archive) [PDF]). 
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 and AI in Games IEEE. 2016, doi:10.1109/tciaig.2016.2528499 (arxiv.org [PDF]).