Introduction
Conformant planning is the task of finding a single sequence of actions that guarantees goal achievement despite uncertainty about the initial state and the total absence of sensors during execution. Because the planner must account for every possible initial configuration, the problem is notoriously difficult, categorized as EXPSPACE-complete. This paper introduces iGC (improved Generate-and-Complete), a framework that significantly advances the state-of-the-art by replacing exhaustive state enumeration with efficient SAT-based logic and redundant action pruning.
The Challenge: State Explosion and Plan Bloat
Traditional conformant planners often struggle with two primary bottlenecks. First, the Generate-and-Complete (GC) approach typically verifies plan correctness by checking every possible initial state one by one. In domains with millions or billions of possible starting states, this brute-force verification leads to system timeouts. Second, the iterative process of repairing a plan to cover new states often introduces "plan bloat"—redundant actions that make the final solution unnecessarily long and difficult to validate.
The iGC Framework
The authors propose three core technical innovations to overcome these limitations:
- SAT-Based Verification: Instead of checking states individually, iGC encodes plan correctness into a Boolean satisfiability (SAT) problem. It asks a SAT solver to find any initial state where the current plan fails. If no such state exists, the plan is valid.
- Counterexample-Guided Completion: When the SAT solver identifies a failure, it provides a specific "counterexample" state. iGC then uses a classical planner (LAMA) to repair the plan specifically for that state, rather than attempting to solve for the entire belief state at once.
- Redundant Action Elimination: To combat plan bloat, iGC monitors belief states. If a sequence of actions leads back to a previously visited belief state or fails to change the belief state at all, that segment is pruned. This ensures the final plan remains lean.
Experimental Evaluation
The researchers evaluated iGC against a massive suite of 50 domains containing 1,179 instances, including standard benchmarks from International Planning Competitions (IPC-5, IPC-6) and high-uncertainty variants where initial states can reach astronomical levels (e.g., $10^{16}$ states).
As shown in the performance data above, iGC solved 989 instances, a substantial improvement over the previous best planner, DNF, which solved 784. Notably, iGC was the only planner capable of solving all instances in 24 different domains.
Key Results and Plan Quality
Beyond simply solving more problems, iGC demonstrated remarkable efficiency in handling massive uncertainty. In the coins-21 domain, which features $10^{16}$ initial states, iGC found a solution in just 23.82 seconds by identifying only 84 representative "witness" states.
Furthermore, the redundancy elimination mechanism significantly improved plan quality. By pruning unnecessary loops and stagnant actions, iGC produced plans that were often 50% to 90% shorter than those generated by the original GC approach.
Limitations and Future Work
While iGC sets a new benchmark, it faces specific bottlenecks. In certain domains, the time required to parse PDDL files exceeds the actual solving time, suggesting a need for more efficient front-end processing. Additionally, because iGC relies on an underlying classical planner, its performance is partially capped by the efficiency of that sub-solver. Future work may also focus on simplifying SAT "trace axioms" to prevent memory bottlenecks in extremely complex environments with very long plans.
Conclusion
By shifting from exhaustive enumeration to counterexample-guided SAT verification and implementing rigorous plan pruning, iGC effectively tames the state explosion inherent in conformant planning. Its ability to solve nearly 1,000 benchmark instances—many involving astronomical levels of uncertainty—marks a significant milestone in the field of automated planning.
Summary updated