Introduction
In AI planning, a "domain" is a formal model—typically written in PDDL—that defines the rules of a world and how actions modify its state. Crafting these models is a notoriously difficult and error-prone process, even for seasoned experts. While modern development environments provide syntax highlighting, they offer little help with "semantic" debugging: identifying why a logically sound plan fails to execute within a specific domain model. This paper presents an automated approach to bridge this gap, treating domain repair as a model-based diagnosis task.
The Domain Repair Problem
The authors address a common bottleneck in model engineering: a modeler possesses a "test case" plan they know should be valid, yet the domain model rejects it because a precondition is not met or an effect is missing. The objective is to find a cardinality-minimal set of repairs—the fewest possible modifications to action preconditions and effects—that transforms the flawed domain into one where the target plan successfully executes. By focusing on minimal changes, the system avoids trivial but useless solutions, such as deleting all preconditions in the entire domain.
Methodology: Diagnosis via Hitting Sets
The researchers frame the repair process as a Model-Based Diagnosis problem. In this framework, the domain is the "system," and the flaws are "faulty components." The goal is to identify a minimal set of repairs (a diagnosis) that resolves all failures.
Key technical innovations include:
- Hitting Set Algorithm: The system iteratively identifies "conflicts" (sets of repairs where at least one must be applied to fix a failure point) and uses a hitting-set algorithm to find the smallest selection of repairs that resolves all known conflicts.
- Lifted Representations: Unlike previous methods that required "grounded" (constant-specific) models, this approach operates on "lifted" models—general action schemas with variables—which are the standard in real-world PDDL modeling.
- Conditional Conflicts: To handle negative preconditions (e.g., "Action A requires X to be false"), the authors introduced conditional conflicts. This ensures that fixing one part of the domain does not inadvertently break another, maintaining consistency across the search space.
Experimental Evaluation
To test the approach, the authors developed two new benchmarks based on the Fast Downward suite:
- $G_1$ (5,460 instances): Pairs a flawed domain (with 10%, 30%, or 50% of schemas modified) with a single valid plan.
- $G_2$ (243 instances): Requires repairing a domain to satisfy multiple plans simultaneously.
Key Results and Performance
The algorithm demonstrated exceptional efficiency and accuracy. In the $G_1$ benchmark, almost every flawed domain was repaired in less than 0.5 seconds, with even the most complex cases rarely exceeding one second.
Beyond speed, the system proved highly accurate. It correctly identified the original introduced errors approximately 72.6% of the time in $G_1$, rising to 76.4% in the multi-plan $G_2$ benchmark. The approach proved robust enough to handle plans with hundreds of steps and domains with dozens of interacting tasks, making it a viable candidate for real-world modeling assistants.
Conclusion and Future Work
This research provides a powerful foundation for a "debugger" for AI planning. By automating the discovery of minimal repairs, it allows modelers to focus on high-level logic rather than tedious troubleshooting. Future work aims to expand the types of supported repairs—such as adding new preconditions or changing action parameters—and incorporating "negative" test cases to ensure the model does not become overly permissive. Ultimately, the goal is to integrate these algorithms into standard IDEs like VS Code to provide real-time modeling assistance.
Summary updated