TL;DR
This paper investigates whether using abstractions to simplify planning problems can speed up "planning as satisfiability" (PAS) solvers, particularly for proving the absence of shorter plans. Surprisingly, they find that abstractions, even those that preserve optimal plan length, often don't improve PAS performance and can even make it worse, due to how SAT encodings interact with resolution complexity.
What Problem Does This Paper Address?
The core challenge lies in efficiently finding optimal plans, especially parallel step-optimal plans. A key bottleneck for state-of-the-art solvers like SATPLAN (which uses Planning as Satisfiability, or PAS) is proving that no plan of a certain length exists. This is crucial for optimality: if the optimal plan has N steps, proving there's no plan of length N-1 is often the hardest part.
The authors draw inspiration from model checking, where "abstraction" (creating a simplified, over-approximated version of a system) is highly effective for proving properties like the absence of errors. They hypothesize that using "solution length preserving" abstractions in planning could similarly simplify the task of proving the absence of shorter plans, thereby speeding up optimality proofs. The question is: can these powerful abstraction techniques, so successful in model checking, be "friends" to PAS, or will they prove to be "foes"?
Methods
The paper explores two main avenues:
- Variable Domain Abstraction: This is the novel abstraction technique proposed. It works by identifying multiple-valued variables in a planning task (e.g., the location of a package) and "gluing" together irrelevant values. For instance, if a package can be in city A, B, or C, and only A and B are relevant to its destination, values related to C might be abstracted away by mapping them to a single representative value. This is designed to preserve optimal plan length.
- Theoretical Analysis of Resolution Complexity: The authors delve into the theoretical underpinnings of why their empirical results might be counterintuitive. They analyze how abstractions affect the "resolution complexity" of the CNF encodings used by SAT solvers. Resolution complexity is essentially the size of the smallest proof of unsatisfiability. They investigate how different types of abstractions and different CNF encoding strategies (based on planning graphs) interact, proving theorems about whether resolution complexity can decrease, stay the same, or even increase after abstraction.
Datasets
The experiments were conducted on a wide range of benchmarks from the International Planning Competitions (IPC) up to IPC 2004. These include domains such as:
- Airport
- Blocksworld
- Depots
- Dining Philosophers
- Driverlog
- Freecell
- Grid
- Logistics
- Mprime
- Mystery
- Optical Telegraph
- Pipesworld (NoTankage and Tankage)
- PSR
- Rovers
- Satellite
- Zenotravel
The authors also designed domain-specific abstractions for some of these domains and used constructed benchmarks (based on the pigeonhole problem) for theoretical analysis.
Key Insights and Ideas
- Abstraction's Counterintuitive Effect on PAS: The most surprising finding is that, contrary to intuition from model checking, abstractions that preserve optimal plan length often do not improve the performance of SATPLAN. Even when abstractions drastically reduce the state space, the time to prove the absence of shorter plans can remain the same or even increase.
- The Devil is in the CNF Encoding: The paper highlights that the interaction between abstractions and the specific CNF encoding used by SAT solvers is critical. Planning graph-based encodings, which capture mutex relationships between actions and facts, are particularly sensitive.
- Resolution Complexity is Key: The theoretical analysis reveals that abstractions can sometimes make it harder to find short resolution refutations. This is because abstractions might obscure crucial mutex relationships that the SAT solver could otherwise exploit, or they might require the solver to re-derive these mutexes, adding computational overhead.
- "Friends" for Some, "Foes" for Others: While SATPLAN (PAS) doesn't benefit much, other planning algorithms like Mips.BDD (which uses a state-space search approach) do show significant performance improvements with the same abstractions. This suggests that the benefits of abstraction are highly dependent on the underlying planning algorithm's mechanism.
- Variable Domain Abstraction is Promising (but not for PAS): The proposed variable domain abstraction is shown to be effective at creating solution-length-preserving abstractions with exponentially smaller state spaces, but this advantage doesn't translate to PAS.
Key Results
- Empirical Results:
- For SATPLAN'04, abstractions generally provided little to no improvement, and in some cases, performance degraded. For example, in Logistics, abstraction yielded only a humble speed-up factor of 2.8, while in other domains, performance was worse.
- Mips.BDD showed significant improvements with abstractions across many domains, sometimes becoming competitive with SATPLAN'04.
- IPP also saw some improvements, though less consistently than Mips.BDD.
- Satellite was a notable exception where abstractions consistently provided huge advantages for all three planners.
- Theoretical Results:
- Theorems 4.1-4.3 demonstrate that for many common abstractions and SAT encodings, resolution complexity cannot decrease by applying the abstraction. In some cases, it can even exponentially increase.
- Theorem 4.3 shows that for encoding (C) (which uses reduced planning graphs), the resolution complexity can be bounded by the complexity of recovering mutexes lost in the abstraction.
- Theorem 4.15 proves that abstractions can lead to exponentially worse resolution complexity, particularly when dealing with problems that can be decomposed into "easy" and "hard" sub-problems.
Limitations and Future Work
- Open Questions on Encodings (B) and (D): The paper leaves open whether variable domain abstraction can improve resolution complexity when using encodings (B) and (D) (which include fact variables). The interaction between fact variables and abstractions remains an area for further research.
- Generalizing Results: The authors question whether their findings hold for other SAT encodings of planning or for other fields like model checking.
- Practical Implications of Theoretical Bounds: While theoretical results show potential for exponential increases in resolution complexity, the authors acknowledge that the practical impact on SAT solver performance is not fully understood. They conjecture that simplifications might bound the improvement polynomially.
- More Effective Abstractions: The paper suggests that more effective abstraction methods might exist, particularly for unsolvable instances, which could be relevant for over-subscription planning.
- Alternative Abstraction Techniques: Exploring predicate abstraction for planning is suggested as a future research direction.
- Modified PAS Systems: Investigating whether modified PAS systems, like those that use branching restrictions within a single SAT call, might benefit from abstractions is also proposed.
Summary updated