The Automatic Programming of Agents that Learn Mental Models and Create Simple Plans of Action

IJCAI 1995

TL;DR

This paper introduces MAPMAKER, a novel genetic programming approach that enables agents to automatically learn and store mental models of their environment, then use these models to generate simple, effective plans. This method successfully tackles the "gold collection" problem, demonstrating that agents can evolve sophisticated internal representations and decision-making strategies without explicit programming.

What Problem Does This Paper Address?

Creating intelligent agents that can learn and adapt to their environment is a fundamental challenge in AI. Traditional approaches to program induction, particularly in genetic programming, have often focused on evolving "reactive" programs that act based on immediate sensory input without maintaining any internal state or memory of past experiences. This limits their ability to solve problems requiring planning, foresight, or understanding of the environment's structure. The paper addresses this gap by proposing a method to evolve agents that can not only perceive their environment but also build and utilize internal "mental models" (like maps) to make informed decisions and create plans of action.

Methods

The core of the paper is the MAPMAKER architecture, which uses genetic programming to evolve multi-part agents. Key aspects include:

  • Modular Architecture: Agents are split into two distinct modules:
  • MapMaker: This module observes the environment and encodes information into a shared memory. It cannot act in the world.
  • MapUser: This module is "blind" to the direct environment and must rely solely on the information stored in memory by the MapMaker to generate a plan of action.
  • Genetic Programming: The entire agent (both modules) is evolved using genetic programming, a technique that breeds computer programs using principles of natural selection.
  • Constrained Evolution: To encourage the development of memory and planning, the fitness environment is designed to necessitate the use of memory. The separation of perception (MapMaker) and action (MapUser) forces the MapUser to rely on the MapMaker's stored representation.
  • Automatically Defined Functions (ADFs): For more complex agents, ADFs are used, allowing for the co-evolution of reusable subroutines, enhancing the power and modularity of the evolved programs.

Datasets

The paper uses a simulated environment called the "gold collection problem" as its benchmark. This problem involves agents navigating a grid-world (2x2, 4x4, 8x8 toroidal worlds) to collect "gold" without digging in empty squares. The worlds are generated with varying gold densities and arrangements, and the agents are trained on a subset of these worlds, with evaluation on unseen worlds to test generalization. No specific pre-existing datasets are mentioned; the worlds are generated for the experiments.

Key Insights and Ideas

  • Emergent Mental Models: The most striking insight is that complex, interpretable mental models of the environment can emerge automatically through genetic programming, without being explicitly programmed or constrained to a specific representation format.
  • Separation of Concerns: The MapMaker/MapUser architecture effectively forces the evolution of memory and planning by separating perception from action, making the use of internal state a necessity for success.
  • Generalization: Evolved agents demonstrate remarkable generalization capabilities, performing correctly on worlds they were not trained on, indicating they learned underlying principles rather than memorizing specific solutions.
  • Provable Solutions: In some cases, the evolved programs were not only empirically successful but also provably correct for all possible configurations within a given world size.
  • Random Search Ineffectiveness: The paper provides strong evidence that random search is orders of magnitude less effective than genetic programming for this problem, highlighting the power of the evolutionary search process.

Key Results

  • MAPMAKER successfully evolved agents that could solve the gold collection problem across various world sizes (2x2, 4x4, 8x8) and gold densities.
  • Many evolved solutions were "completely general," meaning they worked perfectly on any configuration of gold in the tested world sizes, even when trained on only a fraction of possible worlds.
  • For the 8x8 world with 1 gold, an agent evolved that produced "optimal plans" for collecting the single gold.
  • The paper demonstrates that agents can evolve diverse representation schemes, including direct mappings, offsets, and translations, showing flexibility in how mental models are formed.
  • Comparison to random search showed that MAPMAKER found 100% correct solutions significantly faster and more effectively than random individuals, which performed poorly.

Limitations and Future Work

  • Toy Problem: The authors acknowledge that the gold collection problem is a "toy problem," and while the solutions are noteworthy for their automatic generation, they are not necessarily exemplary in their complexity.
  • Future Work: The authors suggest several avenues for future research:
  • Examining more complex representational schemes.
  • Tackling more difficult problems.
  • Investigating the evolution of memory structures themselves.
  • Exploring cooperation among multiple agents.
  • Investigating how agents can learn even with limited memory damage.

Summary updated

BibTeX
@inproceedings{1995automatic,
  title = {{The Automatic Programming of Agents that Learn Mental Models and Create Simple Plans of Action}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1995},
}
Figure