Pushing the Envelope: Planning, Propositional Logic and Stochastic Search

Henry A. Kautz, Bart SelmanAAAI 1996 · OpenReview

TL;DR

This paper demonstrates that by reformulating classical AI planning problems as propositional satisfiability (SAT) problems and using a stochastic local search algorithm (Walksat), they can solve previously intractable planning instances orders of magnitude faster than state-of-the-art specialized planners. This challenges the long-held belief that planning requires specialized algorithms and highlights the power of general-purpose SAT solvers with clever encodings.

What Problem Does This Paper Address?

The field of AI planning has long grappled with the challenge of scalability. Traditional planning algorithms, often based on first-order logic or specialized search techniques, struggle to handle complex real-world problems. This difficulty stems from the inherent combinatorial explosion of possible action sequences and state transitions. While stochastic local search methods have shown success in related areas like scheduling, their application to challenging classical planning problems was not well-established. The authors aim to bridge this gap by showing that a general, stochastic SAT solver, when applied to well-crafted propositional encodings of planning problems, can achieve unprecedented performance.

Methods

The core innovation lies in the reformulation of planning problems as propositional satisfiability (SAT) problems. Instead of using domain-specific planning algorithms, the authors encode the initial state, goal state, and domain axioms into a propositional logic formula. This allows them to leverage powerful SAT solvers.

They explore two main types of encodings:

  • Graphplan-based encodings: These are derived from the planning graphs generated by the Graphplan system, which represent facts and actions at different time steps.
  • Direct encodings: These include:
  • Linear encodings: Based on Kautz and Selman's work, these represent plans as sequences of actions at discrete time steps.
  • State-based encodings: A novel approach that focuses on the properties of states and fluents, abstracting away explicit action representations. This is shown to be particularly compact.

For solving these SAT problems, they compare two approaches:

  • Systematic SAT solvers: Specifically, "tableau," a state-of-the-art Davis-Putnam-based solver.
  • Stochastic local search SAT solvers: Primarily "Walksat," a randomized greedy local search algorithm known for its effectiveness on hard SAT instances.

Datasets

The authors evaluate their approach on several challenging planning domains that are known to be difficult for traditional planners:

  • Rocket domain: A standard benchmark problem.
  • Logistics domain: A more complex extension of the rocket domain, involving moving packages between locations using vehicles.
  • Blocks World: A classic AI problem, with particularly large instances ("bw_large.a", "bw_large.b", "bw_large.c", "bw_large.d") used to test scalability.

They note that these domains were typically described using STRIPS operators, and their encodings were derived from these descriptions.

Key Insights and Ideas

  • Planning as SAT is powerful: The long-held belief that planning requires specialized algorithms is challenged. General-purpose SAT solvers, when fed appropriate encodings, can be highly effective.
  • Encoding matters immensely: The choice of propositional encoding significantly impacts the performance of SAT solvers. State-based encodings, in particular, proved to be very compact and efficient.
  • Stochastic search shines on hard problems: Walksat, a stochastic local search algorithm, consistently outperformed systematic solvers on the hardest instances, often by orders of magnitude. This suggests that for certain complex combinatorial problems, the ability of stochastic methods to escape local optima is crucial.
  • Systematic and stochastic methods are complementary: While Walksat excels at finding solutions quickly, systematic solvers like tableau are essential for proving optimality by demonstrating the infeasibility of shorter plans.
  • State-based encodings offer a new perspective: These encodings, which focus on state properties rather than explicit action descriptions, are more compact, handle parallelism naturally, and provide a cleaner way to represent frame conditions.

Key Results

The paper reports dramatic speedups:

  • For the hardest instances (e.g., "logistics.c" and "bw_large.d"), Walksat with direct SAT encodings solved problems two or more orders of magnitude faster than Graphplan.
  • Walksat found optimal plans for all tested instances.
  • For "bw_large.d" (19 blocks, multiple stacks), Walksat found an optimal 36-step plan, a feat not achieved by other systems without domain-specific heuristics.
  • The state-based encodings resulted in a significant reduction in the number of propositional variables compared to Graphplan-based encodings.

Limitations and Future Work

  • Incompleteness of stochastic search: Walksat cannot prove unsatisfiability, meaning it cannot definitively show that no solution exists. This is where systematic solvers are crucial for proving optimality.
  • Domain dependence of performance: The authors acknowledge that in some specific domains (like D1S¹), Graphplan might scale better than their SAT approach, suggesting that specialized systems can still have advantages.
  • Manual encoding: The state-based encodings used in the experiments were created manually. Automating the process of generating these efficient encodings is a key area for future research.
  • Exploring other domains: The authors plan to apply their methods to other domains, such as the softbot planning domain, to further validate their findings.
  • Further investigation of systematic vs. stochastic: Understanding the relative strengths and weaknesses of systematic and stochastic methods across a wider range of domains and encodings remains an important research direction.

Summary updated

Abstract

Planning is a notoriously hard combinatorial search problem. In many interesting domains, current planning algorithms fail to scale up gracefully. By combining a general, stochastic search algorithm and appropriate problem encodings based on propositional logic, we are able to solve hard planning problems many times faster than the best current planning systems. Although stochastic methods have been shown to be very effective on a wide range of scheduling problems, this is the first demonstration of its power on truly challenging classical planning instances. This work also provides a new perspective on representational issues in planning.
BibTeX
@inproceedings{kautz1996pushing,
  author = {Henry A. Kautz and Bart Selman},
  title = {{Pushing the Envelope: Planning, Propositional Logic and Stochastic Search}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1996},
  url = {https://openreview.net/forum?id=HJVm36g_-H},
}
Figure