Adaptive Modeling and Planning for Reactive Agents

Mykel J. KochenderferAAAI 2005

Abstract

Autonomous agents operating in real-world environments face the challenge of navigating infinite, continuous, and stochastic state and action spaces. This paper presents the Adaptive Modeling and Planning System (AMPS), a framework that treats the environment as a semi-Markov decision process (SMDP). AMPS utilizes decision graphs to dynamically partition both state and action spaces, allowing for incremental learning and real-time policy optimization. By incorporating both splitting and merging operations guided by principled heuristics, AMPS maintains computational efficiency while adapting to environmental complexity.

Introduction

Traditional Reinforcement Learning (RL) frameworks typically rely on Markov Decision Processes (MDPs), which assume a finite set of states and actions occurring at discrete time intervals. However, real-world scenarios—such as robotics or high-fidelity simulations—involve infinite state and action spaces and operate in continuous time.

The challenge for reactive agents is twofold: first, representing an infinite space in a way that allows for effective reasoning; and second, ensuring the agent can learn and plan "on the fly" without being overwhelmed by data volume. While existing solutions often partition state spaces into discrete regions using decision trees, they frequently overlook action space complexity or fail to simplify models when regions become redundant.

Methodology

The SMDP Framework

AMPS treats the environment as a semi-Markov decision process (SMDP). This approach is critical for continuous-time environments, as it allows for transitions between regions to have variable durations, providing a more flexible temporal model than standard MDPs.

Decision Graphs for Partitioning

Unlike previous methods that utilized rigid decision trees, AMPS employs decision graphs. This architectural choice allows nodes to have multiple parents, enabling the system to not only split regions to increase detail but also merge regions to reduce unnecessary complexity. This bidirectional adaptation prevents the model from becoming computationally bloated.

Simultaneous State and Action Partitioning

AMPS is unique in its simultaneous partitioning of the action space alongside the state space. The system uses a nested structure where each state region maintains its own decision graph to categorize actions. By partitioning actions into regions, the agent can treat groups of similar actions collectively, which is vital for handling continuous control.

Heuristic-Driven Adaptation and Planning

To determine when and where to split or merge regions, AMPS employs heuristics derived from supervised learning, including Shannon entropy (Information Gain), cross-validation, and bootstrapping. For planning, the system uses prioritized sweeping—an incremental dynamic programming approach. It prioritizes updates to state regions where the expected reward (value) is changing most significantly, ensuring that limited computational resources are spent where they are most impactful.

Implementation and Results

The system was implemented in Java and tested on various stochastic problems characterized by large state and action spaces. A custom visualization system was developed to analyze the agent's behavior and the logic behind its partitioning decisions.

As this research was presented as part of a doctoral consortium, the results are primarily qualitative but significant:

  • Feasibility: The framework demonstrated that modeling and planning can be performed in real-time for reactive agents.
  • Learning Efficiency: Initial tests indicated that AMPS learns quickly and effectively in stochastic environments that are typically unsolvable with traditional discrete MDP methods.
  • Interruptible Computation: The system successfully breaks modeling and planning steps into small, prioritized chunks. This allows the agent to remain responsive to environmental changes even during intensive computation.

Discussion and Future Work

A major insight from the development of AMPS is the challenge of "credit assignment" regarding model improvement. When a prediction error occurs, the system must determine whether the error should be rectified by refining the state definition or the action definition. Furthermore, the research confirmed that the choice of heuristics for splitting and merging is the primary driver of agent performance.

Future research will focus on:

  1. Theoretical Heuristic Study: Gaining a deeper understanding of how different heuristics affect scalability and performance.
  2. Hierarchical Behavior: Using AMPS to learn sub-behaviors that can be synthesized into complex, hierarchical tasks.
  3. Partial Observability: Extending the model to Partially Observable MDPs (POMDPs) to account for environments where the agent has incomplete information about its state.

Summary updated

BibTeX
@inproceedings{kochenderfer2005adaptive,
  author = {Mykel J. Kochenderfer},
  title = {{Adaptive Modeling and Planning for Reactive Agents}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2005},
}
Figure