Extending Behavior Trees with Classical Planning

Udvidelse af Adfærds Træer med Klassisks Planlægning

Larsen, Søren ; Groth, Jonas Øgendahl

2. term

Computer Science, Master

2011

2011-06-09

72

AI i videospil bruger ofte adfærdstræer—trælignende strukturer, der styrer en agents handlinger. Vi forklarer, hvordan adfærdstræer er defineret og fungerer, og skitserer klassisk planlægning (at finde en række handlinger, der flytter verdenen fra en starttilstand til en måltilstand) samt den udbredte A*-søgealgoritme. Vi sammenligner scripting med adfærdstræer for at tydeliggøre, hvorfor adfærdstræer er attraktive i spil, og bruger disse fordele til at sikre, at vores foreslåede udvidelse ikke undergraver dem. Vores bidrag er en udvidelse, der kombinerer adfærdstræer med klassisk planlægning, inklusive en måde at håndtere tilstande i et ellers tilstandsløst adfærdstræsformal. Vi foreslår også en A*-implementering, der søger efter en sekvens af adfærdstræer, som når en foruddefineret måltilstand. I tests klarer tilgangen sig godt og bevarer de forventede fordele ved adfærdstræer.

Video game AI often uses behavior trees—tree-like structures that control an agent’s actions. We explain how behavior trees are defined and how they work, and we outline classical planning (finding a sequence of actions that moves the world from an initial state to a goal state) and the widely used A* search algorithm. We compare scripting with behavior trees to clarify why behavior trees are attractive in games, and we use those advantages to check that our proposed extension does not undermine them. Our contribution is an extension that combines behavior trees with classical planning, including a way to handle states inside an otherwise stateless behavior-tree formalism. We also propose an A* implementation that searches for a sequence of behavior trees to reach a predefined goal state. In tests, the approach performs well and preserves the expected advantages of behavior trees.

[This abstract was generated with the help of AI]

behavior trees ; behavior tree ; classical planning ; A* search ; A*

Download
View record in AAU Student Projects

Larsen, Søren:

• Applying Behavior Trees to StarCraft AI (2010)

Groth, Jonas Øgendahl:

• Applying Behavior Trees to StarCraft AI (2010)