Friends or Foes? On Planning as Satisfiability and Abstract CNF Encodings.

Carmel Domshlak, Jörg Hoffmann, Ashish SabharwalJAIR 2009 · OpenReview

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:

  1. 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.
  2. 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

Abstract

Planning as satisfiability, as implemented in, for instance, the SATPLAN tool, is a highly competitive method for finding parallel step-optimal plans. A bottleneck in this approach is to *prove the absence* of plans of a certain length. Specifically, if the optimal plan has N steps, then it is typically very costly to prove that there is no plan of length N-1. We pursue the idea of leading this proof within solution length preserving abstractions (over-approximations) of the original planning task. This is promising because the abstraction may have a much smaller state space; related methods are highly successful in model checking. In particular, we design a novel abstraction technique based on which one can, in several widely used planning benchmarks, construct abstractions that have exponentially smaller state spaces while preserving the length of an optimal plan. Surprisingly, the idea turns out to appear quite hopeless in the context of planning as satisfiability. Evaluating our idea empirically, we run experiments on almost all benchmarks of the international planning competitions up to IPC 2004, and find that even hand-made abstractions do not tend to improve the performance of SATPLAN. Exploring these findings from a theoretical point of view, we identify an interesting phenomenon that may cause this behavior. We compare various planning-graph based CNF encodings F of the original planning task with the CNF encodings F_abs of the abstracted planning task. We prove that, in many cases, the shortest resolution refutation for F_abs can never be shorter than that for F. This suggests a fundamental weakness of the approach, and motivates further investigation of the interplay between declarative transition-systems, over-approximating abstractions, and SAT encodings.
BibTeX
@article{domshlak2009friends,
  author = {Carmel Domshlak and Jörg Hoffmann and Ashish Sabharwal},
  title = {{Friends or Foes? On Planning as Satisfiability and Abstract CNF Encodings.}},
  journal = {J. Artif. Intell. Res.},
  year = {2009},
  url = {https://openreview.net/forum?id=IgQZOBwTGV7u},
}

Loading related content...

Figure