Deconstructing Planning as Satisfiability

Henry A. KautzAAAI 2006

Abstract

In the field of automated planning, the late 1990s were marked by a competition between heuristic state-space search and "Planning as Satisfiability" (SATPlan). By 2000, heuristic methods seemed to have achieved a decisive victory. However, the 2004 International Planning Competition (IPC) witnessed a surprising reversal: a SAT-based system, Satplan04, dominated the field. This paper deconstructs the factors behind this resurgence, concluding that the primary drivers were the exponential increase in SAT solver efficiency and a shift in benchmark complexity toward "intrinsically hard" problems.

The Resurgence of SATPlan

The core idea of SATPlan is to encode STRIPS-style planning problems—defined by actions with preconditions and effects—into propositional logic formulas. A solution to the planning problem then corresponds to a satisfying assignment for the formula. While early versions showed promise, they were soon outpaced by planners using sophisticated forward-chaining heuristics.

By 2004, the narrative changed. Satplan04 proved to be the fastest and most robust planner in five domains at the IPC. Interestingly, this success was achieved not by adding complexity to the planning encodings, but often by simplifying them. For instance, Satplan04 removed certain pre-processing steps like mutex propagation, relying instead on the raw power of modern SAT solvers.

The Impact of Solver Engineering

The most significant factor in SATPlan's comeback was the "free lunch" provided by the SAT community. Between 1997 and 2004, SAT solvers underwent a revolution. The transition from early solvers like Sato and Satz to "industrial strength" engines like zChaff, MiniSat, and Siege introduced conflict-driven clause learning (CDCL) and highly efficient data structures.

Table 1: Performance of various SAT solvers (1997–2004) on Airport domain benchmarks from IPC-4.

As shown in the table above, the performance delta is staggering. For the largest problem in the set (p28), solvers from 1997 failed to find a solution within 24 hours. In contrast, the 2004 solver Siege solved the same problem in just 12.74 seconds. Modern solvers demonstrated the ability to handle formulas containing over 13 million clauses and 250,000 variables with remarkable speed.

The paper argues that the nature of the competition benchmarks played a crucial role. Earlier competitions often featured "easy" problems where simple heuristics could easily guide a search to the goal. The 2004 benchmarks, particularly the "Airport" domain, were "intrinsically hard." These problems lacked clear heuristic gradients, creating a combinatorial "needle in a haystack" scenario. SAT solvers, which excel at exploring complex, structured search spaces without relying on simple distance-to-goal heuristics, were perfectly suited for these challenges.

Limitations and Future Directions

Despite its success, SATPlan faces a significant "memory wall." The process of "grounding" (instantiating the entire propositional formula before solving) can lead to memory exhaustion in domains with many objects.

Future research is directed toward overcoming these scaling issues. Key areas include:

  • Symmetry Breaking: Automatically detecting and exploiting the regular structure of planning problems to prune the search space.
  • Metric and Temporal Constraints: Integrating Boolean arithmetic or SMT (Satisfiability Modulo Theories) to handle resources and time.
  • Lifted Solving: Developing solvers that operate directly on first-order logic to avoid the memory explosion of grounding.

Conclusion

The success of Satplan04 was a testament to the power of cross-disciplinary progress. By leveraging the rapid evolution of SAT solver technology, planning researchers were able to tackle problems that were previously considered intractable. The deconstruction of this success highlights that for structured combinatorial problems, the efficiency of the underlying search engine can be just as critical as the domain-specific heuristics.

Summary updated

BibTeX
@inproceedings{kautz2006deconstructing,
  author = {Henry A. Kautz},
  title = {{Deconstructing Planning as Satisfiability}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2006},
}
Figure