A Theory of Debugging Plans and Interpretations

Reid G. SimmonsAAAI 1988

This 1988 classic from the MIT AI Lab introduces a robust framework for fixing "broken" plans and interpretations. Instead of starting from scratch when a heuristic guess fails, Reid Simmons proposes a system that treats bugs as surface symptoms of deeper, faulty assumptions. The paper presents a domain-independent theory for debugging within the "Generate, Test, and Debug" (GTD) paradigm. By tracing causal dependencies and regressing values through a model, the system identifies which underlying assumptions caused a failure and applies principled repair strategies to transform a buggy hypothesis into a working solution.

Addressing the Brittle Nature of Heuristics

In complex domains like geologic interpretation or robot planning, using simple "rules of thumb" (heuristics) is efficient but prone to error. When these heuristics produce an incorrect hypothesis, most AI systems of the era either failed or relied on narrow, domain-specific "bug patches."

Simmons addresses the challenge of creating a robust, general-purpose debugger. The goal is a system that can take a nearly-correct but failing plan and—using a general understanding of causality—figure out exactly what went wrong and how to fix it without needing a human to hard-code every possible error type.

Methodology: The GORDIUS System

The author implemented these ideas in a system called GORDIUS. The debugging process follows four sophisticated steps:

1. Causal Tracing and Value Regression

When a "test" fails, the debugger looks at a causal dependency structure (an acyclic graph) that explains why the system predicted a certain outcome. It traces the failure back to its "leaves"—the fundamental assumptions, such as event ordering or specific parameter values (e.g., a tilt angle of 12°).

Causal dependency graph used by GORDIUS to trace predicted values back to fundamental assumptions.

To find the correct values, the debugger regresses the desired goal state back through the dependencies. If the goal is a 12° orientation but the current plan results in 17°, the system calculates exactly how much a previous step needs to change to close that 5° gap.

2. Domain-Independent Repair Strategies

GORDIUS uses six general strategies to replace faulty assumptions:

  • Occurs: Deleting or replacing an event.
  • Parameter-of: Changing a specific value (like a tilt angle).
  • Ordering: Re-sequencing events.
  • Closed-World Assumptions (CWA): Handling cases where the system assumed nothing happened, but an event was actually needed (or vice versa).

3. Global Evaluation

Since one fix might break something else, the debugger uses a best-first search to evaluate repairs, preferring those that fix the most bugs with the fewest new events.

Domain Applications

As a seminal piece of symbolic AI research, the paper evaluates the theory on three distinct problem domains:

  • Geologic Interpretation (Primary): Explaining how layers of rock (shale, sandstone) reached their current orientation through sequences of deposition, tilting, and erosion.
  • Blocks-World Planning: The classic AI "toy" domain of stacking blocks.
  • Tower of Hanoi: A standard logical puzzle used to test recursive planning.
A geologic interpretation problem showing layers and the sequence of events required to reach the final state.

Key Insights and Results

  • Bugs as Faulty Assumptions: The core insight is that every bug is rooted in an assumption. By making these assumptions explicit in a Truth Maintenance System (TMS), debugging becomes a logical search for the "weakest link."
  • Transformational vs. Refinement Planning: Most planners of the time only added information (refinement). Simmons argues for a transformational approach where the debugger can delete or change previous decisions, allowing the system to recover from early, "greedy" heuristic errors.
  • Successful Geologic Reasoning: GORDIUS demonstrated the ability to solve complex geologic "puzzles" that required reasoning about 3D orientations and temporal sequences. In a sample problem, the debugger correctly identified that changing a single tilt angle was the most elegant solution compared to adding entirely new geologic events.
  • Generality: The same six repair strategies worked across geology, blocks-world, and puzzles, proving that the theory of debugging is largely independent of the specific domain.

Limitations and Future Work

Tracing every assumption and evaluating the global impact of repairs is computationally expensive, with the number of assumptions growing exponentially in complex domains. Additionally, the current strategies struggle with "local minima" where multiple parameters are simultaneously incorrect. Finally, the debugger assumes the domain model is perfect; it can fix a plan, but it cannot fix its own fundamental understanding of physics or geology if the model itself is flawed.

Summary updated

BibTeX
@inproceedings{simmons1988theory,
  author = {Reid G. Simmons},
  title = {{A Theory of Debugging Plans and Interpretations}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1988},
}
Figure