Using Abstraction and Nondeterminism to Plan Reaction Loops

David J. MuslinerAAAI 1994

Abstract

Traditional AI planners often struggle with the continuous and uncertain nature of the real world, leading to state-space explosion when handling repetitive tasks. This paper proposes a method to automatically generate "reaction loops" by applying structured abstractions to complex domains. By modeling actions as nondeterministic and using indexical features, the proposed CIRCA architecture can synthesize plans that provide formal guarantees on both logical correctness and real-time safety.

Introduction

Classical planners, such as STRIPS, are designed for deterministic environments where actions have predictable outcomes. However, real-world tasks like hammering a nail until it is flush require feedback-driven repetition. Enumerating every possible state in a continuous domain (e.g., every possible height of a nail) is computationally infeasible. Conversely, while hand-coded reactive systems handle uncertainty well, they lack formal verification and timing guarantees. This research bridges this gap by enabling automated planners to reason about loops through abstraction.

Methodology: Abstraction Recipes

The authors introduce three primary "recipes" to transform continuous, complex domains into manageable abstract representations:

  1. Eliminating Counting Variables via Nondeterminism: Instead of tracking continuous values, the system uses binary states. For example, a nail's height is abstracted to nail-flush. The action of hammering is modeled as nondeterministic: it may result in the nail being flush or remaining un-flush, creating a loop in the plan.
Figure 2: Nondeterministic action definition and the resulting reaction loop for a hammering task.
  1. Eliminating Named Objects (Indexical Features): To avoid infinite state spaces from tracking specific object IDs, the system uses "indexical" features (e.g., "the-open-salsa-jar" instead of "jar-21"). This focuses the planner on the agent's immediate relationship with its environment.
  2. Temporal Abstraction: The system tracks the minimum time for environmental failure and the maximum time for agent actions. This allows the planner to ensure that reactive behaviors execute frequently enough to preempt failures.

The CIRCA Architecture

These methods are implemented within the Cooperative Intelligent Real-Time Control Architecture (CIRCA). CIRCA decouples high-level reasoning from low-level execution.

Figure 5: The CIRCA architecture, showing the interaction between the AI Subsystem (planning) and the Real-Time Subsystem (execution).

The AI Subsystem performs the planning and scheduling, while the Real-Time Subsystem executes the generated reaction loops. The Scheduler ensures that the selected reactions can meet the required deadlines based on the temporal abstractions provided.

Evaluation and Key Insights

The approach was evaluated using two domains: a simple Hammering domain and a more complex Salsa (grocery stocking) domain. The Salsa domain involves resource management and "avoidance goals," such as ensuring a grocery store never runs out of stock.

Key insights include:

  • Nondeterminism as a Feature: By treating uncertain outcomes as nondeterministic branches, the planner can "close" loops when it encounters a previously planned state.
  • Preemption for Safety: Reasoning about worst-case timing allows the system to guarantee that safety-critical actions (e.g., restocking) occur before a failure state is reached.

Conclusion and Future Work

The paper demonstrates that structured abstraction allows classical planners to generate robust, timely, and logically sound reactive behaviors. However, the process of selecting and applying these abstractions currently requires human intervention. Future work aims to automate the selection of abstraction "recipes" and refine timing models to be less conservative, improving the system's ability to find valid plans in highly constrained environments.

Summary updated

BibTeX
@inproceedings{musliner1994using,
  author = {David J. Musliner},
  title = {{Using Abstraction and Nondeterminism to Plan Reaction Loops}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1994},
}
Figure