Source-linked AI summary
Learning of Behavior Trees for Autonomous Agents
Michele Colledanchise, Ramviyas Parasuraman, Petter Ögren
TL;DR
Automated planning can be impractical when accurate environment models are unavailable, and existing planners may be difficult to scale or extend. This paper combines a greedy strategy and genetic programming to generate behavior trees for autonomous agents in unknown environments. In Mario AI tests, results are described as encouraging and comparable to the state of the art.
Problem
Real-world automated planning often lacks practical accurate task models, while planners can be difficult to scale and extend across domains.
Source: §I · p. 1Method
Results
In the Mario AI benchmark, the results are described as encouraging and comparable to the state of the art.
Source: §VII · p. 7Takeaways & Limitations
The behavior-tree approach divides a goal into subgoals within a modular framework.
Source: §I · p. 2More rigorous analysis and validation are needed before extending the approach to real-world robots.
Source: §VII · p. 7
Abstract
from arXiv · showhide
Definition of an accurate system model for Automated Planner (AP) is often impractical, especially for real-world problems. Conversely, off-the-shelf planners fail to scale up and are domain dependent. These drawbacks are inherited from conventional transition systems such as Finite State Machines (FSMs) that describes the action-plan execution generated by the AP. On the other hand, Behavior Trees (BTs) represent a valid alternative to FSMs presenting many advantages in terms of modularity, reactiveness, scalability and domain-independence. In this paper, we propose a model-free AP framework using Genetic Programming (GP) to derive an optimal BT for an autonomous agent to achieve a given goal in unknown (but fully observable) environments. We illustrate the proposed framework using experiments conducted with an open source benchmark Mario AI for automated generation of BTs that can play the game character Mario to complete a certain level at various levels of difficulty to include enemies and obstacles.
I. INTRODUCTION
The introduction frames automated planning as difficult to specify and scale in unknown real-world settings, motivating behavior trees and a model-free framework. It positions the approach against related work that uses grammatical evolution or requires an initial behavior tree.
I. INTRODUCTION
- Accurate planning-task descriptions are often impractical for real-world problems, while automated planning can be hard to scale and extend across domains.The paper also notes that search-control knowledge can require expertise in both the task and the planning algorithm.Source: §I · p. 1
- Behavior trees offer a modular alternative to conventional transition systems, with tree structure that supports connecting subtrees and applying genetic operators.Parent-child relations allow whole subtrees to cross over and mutate during genetic programming.Source: §I · pp. 1–2
- The proposed model-free framework generates a behavior tree for an autonomous agent to achieve a goal in an unknown environment, dividing the goal into subgoals.The approach uses a greedy algorithm first and genetic programming when greedy search fails, cannot produce results, or solution complexity increases.Source: §I · p. 2
II. RELATED WORK
- Unlike Perez et al.'s grammatical-evolution approach to evolving behavior trees, this work uses genetic programming and does not require an initial behavior tree.The authors also state that they do not directly compare their framework with other relevant work.Source: §II · p. 2
III. BACKGROUND: BT AND GP
Behavior Trees (BTs) represent action execution as a rooted tree whose nodes pass execution status between parents and children. Their control-flow nodes organize execution, while action and condition nodes perform or check task behavior.
III. BACKGROUND: BT AND GP
- BTs are a graphical language for executing actions based on system conditions and observations, and resemble hierarchical finite-state machines or task-network planners.The section introduces BTs and genetic programming as background.Source: A. Behavior Tree · p. 2, §III · p. 2
A. Behavior Tree
- A BT is a rooted tree with control-flow nodes that organize execution and execution nodes that have no children.Children of control-flow nodes are executed from left to right.Source: A. Behavior Tree · p. 2
- Ticks allow children to execute, and each child returns running, success, or failure to its parent.The root sends ticks to its child at a given frequency.Source: A. Behavior Tree · p. 2
- Selectors stop at the first child returning success or running, whereas sequences stop at the first child returning failure or running.A selector fails only when all children fail; a sequence succeeds only when all children succeed.Source: A. Behavior Tree · pp. 2–3
- Parallel nodes tick children concurrently, decorators manipulate a child’s return status, actions perform actions, and conditions return success or failure.A parallel node returns running unless its success or failure threshold is met; conditions never return running.Source: A. Behavior Tree · p. 3
B. Genetic Programming
Genetic programming (GP) evolves Behavior Trees as computer programs, selecting them by a user-defined fitness function. The approach uses genetic operations to improve goal achievement and applies bloat control to reduce unnecessary tree size.
B. Genetic Programming
- GP evolves Behavior Trees as computer programs according to a user-defined fitness function measuring their ability to achieve a goal.The population begins with randomly generated BTs.Source: B. Genetic Programming · p. 3
- Bloat control is applied at the end because GP can generate BTs larger than necessary despite equivalent fitness and performance.The evolution process uses reproduction, crossover, and mutation and continues until a BT satisfies the goal.Source: B. Genetic Programming · p. 3
- Crossover exchanges subtrees, mutation replaces a node, and selection chooses BTs for the next population in proportion to fitness.The selected BTs form the parent population for the next generation.Source: B. Genetic Programming · pp. 3–4
1) Two-point crossover in two BTs:
The crossover operation swaps subtrees between two Behavior Trees. The figures depict the trees before and after the highlighted subtrees are exchanged.
1) Two-point crossover in two BTs:
- Crossover randomly swaps a subtree from one BT with a subtree from another at any level.The paper notes that using BTs as the representation avoids the logic-violation problem during crossover described in.Source: 1) Two-point crossover in two BTs · p. 4
- Fig. 6 shows two BTs before the highlighted subtrees are exchanged.The following figure shows them after crossover.Source: Figure 6 · p. 4, Figure 7 · p. 4
- Fig. 7 shows two BTs after the highlighted subtrees are exchanged.Crossover exchanges subtrees between two BTs.Source: Figure 7 · p. 4, 1) Two-point crossover in two BTs · p. 4
2) Mutation operation in BT:
The formulation assumes an unknown but fully observable environment with a finite action set, and asks for actions that move an initial state to a goal state. The learning method combines mutation with fitness- and diversity-based selection.
2) Mutation operation in BT:
- Unary mutation replaces a BT node with another node of the same type, while gradually reducing the number of mutated nodes across generations.The initial population receives mutations on several nodes; the number is reduced over successive generations to shift from high to smaller diversity.Source: 2) Mutation operation in BT · p. 4
3) Selection mechanism:
- Selection chooses offspring BTs for the next population, with rank-space probabilities assigned after sorting individuals by fitness.The diversity-rank method also makes selection probability encompass both diversity and fitness.Source: 3) Selection mechanism · p. 4
IV. PROBLEM FORMULATION
- The problem setup knows only the initial and final states, while the fitness function returns 1 exactly when the action set changes the initial state to a goal-satisfying final state.Source: §IV · p. 4
- Given a goal function γ and initial state s0, derive a finite action sequence Σ such that γ(s0,Σ) = 1.The environment is unknown but fully observable, and the framework assumes some finite action set can reach the goal.Source: §IV · p. 4
V. PROPOSED APPROACH
The proposed framework learns a BT in an unknown environment by evaluating progress toward a user-defined goal. It uses greedy search before GP and represents the knowledge as a rule-based BT.
V. PROPOSED APPROACH
- A user-defined fitness function scores how closely an executed BT approaches the goal, with evaluations based on the preceding τ seconds of execution.The BT runs continuously while the fitness function is evaluated over a moving time window.Source: §V · p. 4
- The learner tries a greedy algorithm first and invokes GP when greedy search fails or solution complexity increases.The authors state that this mixed strategy is intended to reduce learning time compared with pure GP while still achieving a goal-satisfying BT.Source: §V · p. 4
- When progress stalls, recently changed conditions are composed into a subtree; greedy search adds actions, with GP used if no action increases fitness.The process repeats until the goal is achieved, then anti-bloat control removes possibly unnecessary nodes.Source: §V · p. 5
A. Knowledge representation
- A BT represents knowledge as rules specifying which action to perform when conditions are satisfied.Source: A. Knowledge representation · p. 5
B. Extraction of the experience
The framework extracts experience as observable conditions and learns a BT by tracking condition and fitness changes. It iteratively extends the learned tree until the goal is reached, then removes possibly inefficient nodes.
B. Extraction of the experience
- Agent experience is represented by conditions observed through sensory perceptions, such as obstacle position, energy level, or an enemy being in front.Source: B. Extraction of the experience · p. 5
C. Learning algorithm
- Starting from s0, the learner tries actions greedily when fitness does not increase and uses GP if no action works, producing the initial BT T0.If the framework learns only one action, T0 is a degenerate BT consisting of that action.Source: C. Learning algorithm · p. 5
- During each τ window, Tcond composes conditions that changed from true to false or from false to true.The composition is depicted in Fig. 8.Source: C. Learning algorithm · p. 5, Figure 8 · p. 5
- When fitness decreases, the learner composes recently changed conditions into a subtree, learns actions for it, and repeats until the goal is reached.The final BT is pruned with anti-bloat control to remove possibly inefficient nodes introduced by a large τ window or GP randomness.Source: C. Learning algorithm · p. 5
D. Exploitation of the collected knowledge
BTs are evaluated in simulated or real environments, and the goal-specific fitness function determines the learner's next step.
D. Exploitation of the collected knowledge
- At each stage, BTs run in simulated or real environments and a goal-specific fitness function guides the learning algorithm's next course.For completing a game level, fitness may reflect points, distance traversed, time spent, and enemies shot.Source: D. Exploitation of the collected… · p. 6
E. Anti-bloat control
The paper applies a separate breadth-first procedure after GP generates a behavior tree (BT), removing ineffective subtrees while aiming to preserve BT properties and performance.
E. Anti-bloat control
- After GP generates a BT without size or depth restrictions, a separate breadth-first algorithm reduces its size and depth while keeping its properties and performance.The procedure targets a complex yet practical BT before applying bloat control.Source: E. Anti-bloat control · p. 6
- The procedure tests subtrees in breadth-first order, removing one when omitting it does not lower the fitness value, then repeats on the updated BT.It stops when no ineffective subtree remains.Source: E. Anti-bloat control · p. 6
- The paper notes that this removal procedure is straightforward for BTs because of their tree structure.Source: E. Anti-bloat control · p. 6
VI. PRELIMINARY EXPERIMENTS
The preliminary experiments use Mario AI to test BT generation in game levels, from a simple setting without enemies or cliffs to a testbed focused on movement and obstacles.
VI. PRELIMINARY EXPERIMENTS
- Mario AI tests agents moving Mario through side-view 2D levels, with walking, running, jumping, and state-dependent fireball shooting.The main level goal is to reach its end; auxiliary goals include collecting coins, finishing quickly, and scoring highly.Source: §VI · p. 6
- The 5×5 receptive field supplies 50 conditions: each grid box is checked for an enemy and an obstacle.The fitness function combines distance passed, enemies killed, hurts, and remaining time at the level's end.Source: §VI · p. 6, Figure 9 · p. 6
A. Testbed 1: No enemies and no cliffs
- In this simple Testbed 1 case, the agent learns to move toward the level’s end and jump obstacles, with GP selection using the rank-space method; Fig. 10 illustrates a resulting learned BT.Source: A. Testbed 1: No enemies and no cliffs · p. 6, Figure 10 · p. 7
B. Testbed 2: Walking Enemies and No Cliffs
The paper reports encouraging, state-of-the-art-comparable results in the Mario AI simulator, while noting that further validation is needed before extending the approach to real-world robots. It also describes increasingly challenging testbeds and identifies further experiments and methods for future work.
B. Testbed 2: Walking Enemies and No Cliffs
- Compared with Testbed 1, Testbed 2 is slightly more complex: the agent must move toward the end of the level, jump obstacles, and kill the enemies; Fig. 11 illustrates a resulting BT.Source: B. Testbed 2: Walking Enemies and No… · p. 7, Figure 11 · p. 7
C. Testbed 3: Flying Enemies and Cliffs
- For this testbed, the agent must learn to move toward the level’s end, jump obstacles, kill flying enemies, and avoid cliffs; the final generated BT is omitted for size restrictions (about 20 nodes).Source: C. Testbed 3: Flying Enemies and Cliffs · p. 7
VII. CONCLUSIONS
- The authors describe the Mario AI results as encouraging and comparable to the state of the art, but call for more rigorous validation before real-world robot extensions.The reported tests simulate Mario behavior in the benchmark simulator.Source: §VII · p. 7
VIII. FUTURE WORK
- Future work proposes extensive Mario AI experiments and comparisons with approaches such as, exploration of dynamic environments, and supervised learning for BT generation.The supervised-learning work aims to learn tasks separately from training examples, with preliminary Mario AI examples for shooting and jumping.Source: §VIII · p. 7