Decision-Theoretic Plan Failure Debugging and Repair

Lisa J. BurnellAAAI 1994

Introduction

In the field of automated planning, the transition from theoretical models to real-world execution is often fraught with unexpected outcomes. When a plan fails, an autonomous system must perform two critical tasks: diagnosis (identifying what went wrong) and repair (determining how to recover). Historically, research has been divided between heuristic methods, which are computationally efficient but brittle in the face of novel errors, and logic-based methods, which are theoretically robust but often too slow for real-time or resource-constrained environments. This paper proposes a decision-theoretic framework designed to bridge this gap by treating failure as a probabilistic challenge rather than a deterministic one.

The Proposed Framework

The research outlines a unified pipeline that integrates probabilistic modeling, meta-reasoning, and machine learning to handle plan failures under uncertainty. The framework is composed of four primary stages:

1. Probabilistic Diagnosis via Belief Networks

Rather than assuming a single, certain cause for a failure, the system employs belief networks to model the complex, uncertain relationships between planning actions and potential error classes. This approach allows the system to generate a ranked list of likely error sources, providing a more nuanced understanding of the failure than traditional binary logic.

2. Value of Information (VoI) Calculations

A standout feature of this framework is the explicit modeling of the "cost of thinking." Before the system engages in computationally expensive logical analysis, it calculates the Value of Information (VoI). If the situation is time-critical or the potential insight gained from deep reasoning is unlikely to change the recovery strategy, the system may bypass complex analysis in favor of a "best guess" based on the initial probabilistic diagnosis.

3. Decision-Theoretic Repair Selection

Once a failure is diagnosed, the system must choose a recovery strategy. This selection is made using decision-theoretic principles, weighing the probability of the error type against the criticality of the failure and the resources currently available. Strategies can range from simple, reactive local fixes to requesting a comprehensive global replan from a higher-level agent.

4. Planner Modification and Learning

To move beyond simple error recovery, the framework incorporates a machine learning component. By analyzing failures, the system attempts to refine the planner’s internal domain model. This "closes the loop," allowing the autonomous agent to evolve and prevent the recurrence of similar failure modes in future tasks.

Key Insights and Contributions

The proposed research introduces several modern concepts to the 1990s planning landscape:

  • Uncertainty as a First-Class Citizen: By moving away from deterministic failure models, the framework acknowledges the inherent incompleteness of knowledge in multi-agent and dynamic environments.
  • Reasoning Under Resource Constraints: The inclusion of VoI recognizes that in real-world applications, a "perfect" diagnosis is a failure in itself if it takes too long to compute while the environment continues to change.
  • Autonomous Evolution: The integration of learning suggests that failure should be viewed as an opportunity for system improvement rather than just a hurdle to be cleared.

Limitations and Future Directions

While the framework offers a robust theoretical approach, several challenges remain. The computational overhead of managing large belief networks can be significant, potentially offsetting the gains made by the VoI calculations. Furthermore, the effectiveness of the entire system is heavily dependent on the accuracy of the underlying probabilistic models. Building and maintaining these models for highly complex or dynamic domains remains a significant engineering challenge.

Despite these hurdles, the framework’s successful application in software debugging (as noted in Burnell & Horvitz 1993) suggests that this decision-theoretic approach is a viable path forward for creating more resilient autonomous planners.

Summary updated

BibTeX
@inproceedings{burnell1994decision,
  author = {Lisa J. Burnell},
  title = {{Decision-Theoretic Plan Failure Debugging and Repair}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1994},
}

Loading related content...

Figure