Expecting the Unexpected: Detecting and Reacting to Unplanned-for World States

AAAI 1996

TL;DR

Autonomous systems often struggle when the real world deviates from their pre-programmed models. This paper introduces a method for systems like CIRCA to detect and react to "unhandled" world states – situations not explicitly planned for. By classifying these states and using machine learning to build detection rules, the system can avoid catastrophic failures and adapt to unexpected events.

What Problem Does This Paper Address?

Developing robust autonomous systems, especially in complex domains like aircraft flight, is challenging because it's impossible to create perfect, all-encompassing models of the world. Real-world scenarios can present unexpected situations that deviate from the system's plan. These "unhandled" states can lead to system failure if not detected and reacted to appropriately. The authors tackle the problem of how an autonomous system can identify when it's in such an unhandled state and then respond effectively, rather than simply failing.

Methods

The core contribution is a method for detecting and responding to unhandled world states within the Cooperative Intelligent Real-time Control Architecture (CIRCA). The approach involves:

  • State Classification: Identifying and categorizing unhandled states into subclasses:
  • Deadend (D): States from which the goal is unreachable.
  • Removed (R): States that were deemed improbable and removed from the plan due to resource constraints.
  • Imminent-Failure (IF): States that are not explicitly modeled but lead to failure if reached.
  • Machine Learning for Detection: Using the ID3 algorithm (a decision tree learning algorithm) to build test conditions for detecting these unhandled states.
  • For deadend states, ID3 is trained on actual deadend states as positive examples and all other reachable states as negative examples.
  • For removed states, ID3 is used to detect states that become reachable after backtracking.
  • For imminent-failure states, ID3 is trained on states that lead to failure via a single temporal transition.
  • Reactive Response: Upon detecting an unhandled state, CIRCA replans based on the current situation to find a way to recover or mitigate the failure.

Datasets

Not discussed in the paper. The authors mention using an aircraft simulator for testing.

Key Insights and Ideas

  • The world is messy: Perfect models are a myth in complex domains. Autonomous systems must be prepared for the unexpected.
  • Categorizing the unexpected: Not all unhandled states are equal. Classifying them (Deadend, Removed, Imminent-Failure) allows for more targeted detection and response strategies.
  • Learning to detect: Machine learning (specifically ID3) is a powerful tool for building compact, effective rules to identify these unhandled states, leveraging past experiences or known failure modes.
  • Detection enables reaction: The ability to detect an unhandled state is the crucial first step that allows the system to then execute recovery actions, preventing catastrophic failure.

Key Results

The paper reports on tests conducted using an aircraft simulator. When CIRCA encountered an unhandled state (simulated by altering the aircraft's gear model, leading to different types of unhandled states), it was able to:

  • Detect and respond: CIRCA successfully detected the unhandled states (D, R, or IF) and executed appropriate recovery actions (e.g., "go-around," "gear-down").
  • Avoid failure: In contrast, without the detection mechanism, the system would have consistently failed (i.e., the plane would have crashed).

Limitations and Future Work

  • Limitations: The paper focuses on detecting and responding to specific subclasses of unhandled states (D, R, IF). It doesn't explicitly detail how it handles completely unmodeled states that don't fall into these categories. The current approach relies on the planner's ability to build a "deadend state list" or identify temporal transitions to failure, which might have its own limitations.
  • Future Work: The authors suggest continuing tests with more complex flight examples. A key area for future research is imposing time bounds on CIRCA's planner to guarantee timely responses to unhandled states, which is critical for real-time applications.

Summary updated

BibTeX
@inproceedings{1996expecting,
  title = {{Expecting the Unexpected: Detecting and Reacting to Unplanned-for World States}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1996},
}
Figure