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. Auch das Robotik-Framework ROS enthält die SMACH-Engine, um Behavior-Tree-ähnliche Abläufe zu spezifizieren.

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.