Evolution-Based Discovery of Hierarchical Behaviors

AAAI 1996

TL;DR

This paper introduces Adaptive Representation through Learning (ARL), a novel genetic programming approach that simultaneously learns hierarchical behaviors and adapts its own representation system. By discovering and reusing subroutines, ARL significantly improves the performance and generalization of agents in complex, dynamic environments, outperforming traditional genetic programming methods.

What Problem Does This Paper Address?

Learning effective control policies for agents in complex, dynamic environments is a significant challenge in artificial intelligence. Traditional approaches often struggle with the sheer scale of possible situations and the difficulty of representing knowledge in a modular, reusable way. This paper addresses the problem of discovering hierarchical control structures that can generalize well and adapt to new situations. The authors argue that modularity, where a problem is broken down into smaller, reusable components (like subroutines), is crucial for scaling up learning systems, much like how complex systems in nature are built from simpler, interacting parts. They aim to develop a method that can automatically discover these hierarchical behaviors without requiring a predefined architecture.

Methods

The core contribution is the Adaptive Representation through Learning (ARL) algorithm. ARL is an extension of genetic programming (GP) that operates on two tiers:

  • Bottom Tier (GP Search): This tier uses standard GP operations (like crossover and reproduction) to evolve programs that control an agent. Programs with higher fitness (better performance) are more likely to have their substructures passed on to the next generation.
  • Top Tier (Subroutine Discovery): This is the novel part. ARL actively searches for "useful" blocks of code within the population of programs. It identifies these blocks based on:
  • Differential Fitness: Blocks that contribute to a significant improvement in a program's fitness over its parent.
  • Block Activation: Blocks that are frequently executed during program evaluation.
  • Generalization: Identified blocks are then generalized by replacing terminals with variables, effectively creating new subroutines. These subroutines are added to the system's vocabulary, making them available for future program evolution.
  • Subroutine Utility: Subroutines are assigned utility values, and less useful ones are pruned to keep the vocabulary manageable.

This process allows ARL to adapt its representation system (the set of available functions and subroutines) dynamically, biasing the search towards more effective and modular solutions. The paper also compares ARL to other methods like random search, simulated annealing (PSA), and standard GP with automatically defined functions (ADF).

Datasets

The paper uses the Pat-Man game as its primary application task and benchmark. This is a simulated environment similar to the well-known Pac-Man game, involving an agent navigating a maze, collecting food, avoiding monsters, and collecting power-ups. The environment is dynamic and nondeterministic, with monsters moving randomly. The authors do not introduce a new dataset but rather use this established benchmark to evaluate their algorithm's performance.

Key Insights and Ideas

  • Adaptive Architecture Discovery: The most significant insight is that the system's "architecture" (its vocabulary of available functions and subroutines) can be learned and adapted alongside the control policies themselves. This contrasts with methods like ADF-GP, which require a fixed architecture upfront.
  • Subroutine Discovery as a Bias Mechanism: By discovering and reusing subroutines, ARL effectively biases the GP search towards more structured and potentially more efficient solutions. This is akin to how humans learn by building upon existing knowledge and skills.
  • Modularity for Generalization: The discovered subroutines often correspond to distinct "behaviors" (e.g., chasing food, attracting monsters). This modularity not only makes the programs more interpretable but also significantly improves their ability to generalize to unseen situations.
  • Differential Fitness as a Heuristic: Using differential fitness to identify promising blocks of code is an effective heuristic for finding parts of programs that are genuinely contributing to improved performance, rather than just being present.

Key Results

  • Superior Performance: ARL consistently outperformed other tested methods (random search, PSA, SGP, ADF) in the Pat-Man game, achieving the highest average fitness (game points) for both representations A and B.
  • Best Result with Representation B: The ARL algorithm with representation B (which uses typed primitives and resembles decision trees) achieved the best overall performance, with an average fitness of 4439 points.
  • Effective Generalization: ARL solutions demonstrated strong generalization capabilities, as evidenced by their performance on 100 random test cases, outperforming other approaches.
  • Emergent Modularity: ARL discovered a hierarchy of subroutines that represented distinct behaviors, with the best-of-run program in one experiment being guided by five key subroutines.

Limitations and Future Work

  • Parameter Tuning: The paper mentions that the cooling schedule parameters for simulated annealing (PSA) were set using a simple rule and not optimized. Further work could explore optimal parameter settings.
  • Computational Effort: While ARL achieved good results, the paper notes that the computational effort for PSA and GP techniques was made similar by setting the number of generations. A more direct comparison of computational cost for achieving similar performance levels might be valuable.
  • Comparison with Memoryless/State-Maintaining RL: The authors suggest further investigation into comparing ARL with memoryless and state-maintaining reinforcement learning algorithms.
  • Procedural vs. Representational Bias: ARL can be studied as an example of how procedural bias (the structure of programs) interacts with representational bias (the available vocabulary of functions and subroutines), which could shed light on how GP exploits structures and constructs solutions.

Summary updated

BibTeX
@inproceedings{1996evolution,
  title = {{Evolution-Based Discovery of Hierarchical Behaviors}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1996},
}
Figure