Abstract
Reliability in AI planning is paramount for safety-critical applications. This paper introduces the first executable, formally verified SAT encoder for classical AI planning, implemented and proven correct using the Isabelle/HOL theorem prover. By establishing a mathematically sound translation from planning problems to Boolean logic, the researchers bridge the "trustworthiness gap" inherent in unverified state-of-the-art planners. The verified system not only guarantees the correctness of generated plans and unsatisfiability claims but also identifies existing bugs in established planners like Madagascar.
Introduction
In classical AI planning, the objective is to determine a sequence of actions that transitions a system from an initial state to a desired goal. A highly effective approach involves encoding these planning problems into Boolean Satisfiability (SAT) formulas. If a SAT solver finds a satisfying assignment, it can be decoded into a valid plan.
However, the encoders themselves—the software responsible for this translation—are complex and often unverified. In safety-critical domains, a bug in the encoder could lead to the execution of unsafe plans or the false conclusion that a goal is unreachable. This research addresses this vulnerability by formally verifying the entire encoding and decoding pipeline, ensuring that the logic produced is a faithful representation of the original planning problem.
Methodology: Verified Stepwise Refinement
The authors utilized the Isabelle/HOL interactive theorem prover to develop and verify their system. The core of their approach is a "stepwise refinement" strategy that decomposes the translation into several verified stages:
- FD-AST to FDR: The input format (Fast Downward’s abstract syntax tree) is translated into a Finite Domain Representation.
- FDR to STRIPS: Multi-valued variables are compiled into simpler Boolean (STRIPS) variables.
- STRIPS to SAT: The problem is encoded into propositional logic using a parallel $\forall$-step encoding, allowing for concurrent non-interfering actions.
- SAT to DIMACS-CNF: The logic is formatted for standard SAT solvers.
The verification covers both the encoder (ensuring the SAT formula is satisfiable if and only if a plan exists) and the decoder (ensuring a SAT model correctly maps back to a valid plan). To handle proofs of unsatisfiability, the system integrates a verified certificate checker (GRAT).
Evaluation and Key Results
The system was evaluated against standard benchmarks from the International Planning Competitions (IPC), including domains like logistics, space exploration (Rover, Satellite), and classic puzzles (Blocks-world).
Performance and Robustness
While the verified encoder is approximately an order of magnitude slower than unverified counterparts due to the use of functional data structures (e.g., balanced trees instead of mutable arrays), the resulting SAT formulas are highly competitive.
As shown in the experimental results, the verified encoder successfully handles a wide range of standard benchmarks. Notably, in domains like Rover, the SAT solver could solve the verified encoding while failing to terminate on the Madagascar encoding.
The "Madagascar" Bug and Encoding Insights
A significant finding of this work was the discovery of a bug in Madagascar, a state-of-the-art unverified planner. By using the verified encoder as a reference, the authors found that Madagascar occasionally adds incorrect "mutex" constraints, leading it to falsely claim problems are unsolvable.
Furthermore, the study challenged assumptions about encoding size. Madagascar uses auxiliary variables to maintain a "linear" encoding size, whereas the verified encoder uses a "quadratic" encoding without auxiliary variables. Surprisingly, modern SAT solvers like Kissat often solved the quadratic encodings faster, suggesting that auxiliary variables may sometimes hinder the solver's internal heuristics.
Conclusion and Future Work
This work demonstrates that formal verification is feasible for complex AI planning tasks beyond "toy" problems. The resulting system provides a mathematically guaranteed foundation for SAT-based planning. Future research will focus on addressing current limitations, such as memory consumption in the purely functional implementation, and extending the framework to support cost-optimal planning and more efficient low-level execution environments like LLVM.
Summary updated