Preliminary Studies in Agent Design in Simulated Environments

Scott B. HunterAAAI 1994

Abstract

In the early 1990s, artificial intelligence research was characterized by a dichotomy between purely reactive systems and classical planning architectures. This paper investigates the lack of formal criteria for selecting architectural compromises between these two extremes. By utilizing the XChomp (a Pac-Man variant) environment as a discrete combinatorial testbed, this study proposes a systematic approach to matching agent designs to specific environment/task (E/T) pairs. The ultimate goal is to move beyond individual "existence proofs" toward a predictive framework that facilitates the automatic synthesis of agents based on environmental parameters.

Introduction

The field of agent design has historically focused on demonstrating that a specific architecture can solve a specific task. However, as Scott B. Hunter argues, this approach provides little guidance for future designers. If an environment is modified—for instance, by increasing the speed of adversaries or changing the layout of a maze—there is no established theory to predict how an agent's performance will degrade or which architectural adjustments are necessary to maintain efficacy.

This research addresses the gap between "purely reactive" systems, which prioritize immediate response to stimuli, and "classical planning" systems, which rely on extensive internal modeling and projection. Rather than proposing a single hybrid architecture, this study seeks to define the criteria for determining which compromise is best suited for a given problem domain.

The XChomp Testbed

To explore these architectural trade-offs, the study utilizes XChomp, a dynamic simulator based on the classic game Pac-Man. XChomp was selected because it offers a more complex and tunable environment than the simpler domains often used in contemporary AI research, such as Agre and Chapman’s Pengi.

Unlike simpler grid-worlds, XChomp presents a "discrete combinatorial problem domain" where the agent must navigate a maze while managing multiple, often conflicting, objectives. The environment is easily parameterized, allowing for the systematic variation of ghost behavior, maze complexity, and scoring rules. This makes it an ideal laboratory for perturbation analysis.

Methodology

The research methodology is structured into four primary phases:

  1. Isolation of E/T Combinations: Defining specific versions of the game that represent distinct environmental challenges and task requirements.
  2. Controller Implementation: Developing a spectrum of controllers ranging from simple reflex-based agents to sophisticated planners that utilize forward projection and optimal pathfinding.
  3. Perturbation Analysis: Experimentally varying environmental specifications (e.g., the number of pellets, ghost speed, or maze connectivity) to observe how different architectures respond to stress.
  4. Theoretical Modeling: Developing a formal basis to justify agent behavior. This involves identifying which environmental features are critical for decision-making and which can be safely ignored by the agent’s internal model.

Key Architectural Challenges

Through the lens of XChomp, Hunter identifies several fundamental challenges in agent design:

Non-Local Constraints

Many tasks in XChomp cannot be solved through local sensing alone. For example, the objective to "clear all pellets" involves universal quantification over the entire state space. An agent must have a mechanism to track global progress and navigate toward distant goals that are not currently visible.

Dynamic Object Classification

The role of objects in the environment can change based on the agent's state. A ghost is typically a lethal threat (a negative goal), but upon the consumption of a power pellet, it becomes a "positive concrete goal." Managing these transitions requires the agent to handle objects whose functional roles are determined by projections of possible futures.

The High Cost of Movement

In a maze environment, movement is highly restricted. At most intersections, an agent has only two or three viable choices. A single wrong turn can lead to a dead end or a fatal encounter. Hunter suggests that this high cost of error justifies the computational overhead of more complex planning, as the price of a "reactive mistake" is significantly higher than in open-field environments.

Preliminary Results and Framework

As a preliminary study, the results are primarily methodological. The research successfully established XChomp as a superior testbed for agent design, providing a richer set of challenges than its predecessors.

The study also produced a framework for action selection based on three critical questions:

  1. What do we project? (The extent of the agent's internal simulation of the future).
  2. What do we sense? (The granularity and scope of environmental input).
  3. How do we map state to action? (The logic used to translate internal and external data into movement).

By systematically perturbing the environment's rules, the study demonstrated that agent robustness is not a universal trait but is deeply tied to how well the architecture's internal assumptions match the environment's actual dynamics.

Conclusion and Future Work

This work represents an early step toward the automatic synthesis of agents. While the current study is limited to discrete 2D simulations, it lays the groundwork for a theory of agent-environment fit. Future research will focus on refining the theoretical basis for these architectural compromises and exploring how these insights might scale to continuous, high-dimensional domains like real-world robotics. The ultimate objective remains a system that can analyze an environment's specification and automatically generate the most efficient agent architecture to navigate it.

Summary updated

BibTeX
@inproceedings{hunter1994preliminary,
  author = {Scott B. Hunter},
  title = {{Preliminary Studies in Agent Design in Simulated Environments}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1994},
}

Loading related content...

Figure