TL;DR
This paper introduces a novel approach to planning-as-satisfiability (SAT) by exploiting the deterministic nature of fluent updates. By modifying a standard SAT solver to prioritize branching on action variables, they achieve dramatic speedups (up to 4 orders of magnitude) in solving planning problems, significantly reducing the search space.
What Problem Does This Paper Address?
Traditional AI planning problems are often reduced to SAT problems, where a SAT solver searches for a satisfying assignment of truth values to variables representing actions and their effects over time. However, existing SAT solvers treat all variables (actions and fluents) equally during the search. This paper highlights that in STRIPS-style planning, the values of "fluents" (states of the world) at a given time point are deterministically determined by the initial state and the sequence of actions performed up to that point. The only source of true nondeterminism lies in the choice of actions. The challenge is that current SAT-based planners don't leverage this inherent determinism, leading to an unnecessarily large search space and slower problem-solving times.
Methods
The core contribution is the development of a modified Davis-Putnam (DP) procedure, dubbed DP, for solving SAT-encoded planning problems. The standard DP procedure involves branching on any literal (action or fluent). DP modifies this by forcing the solver to only branch on action literals. This means that when the solver needs to make a non-deterministic choice, it will always pick an action variable. Fluent variables, whose values are deterministically determined by actions, are handled by the UNIT-PROPAGATE step within the DP procedure. This effectively restricts the search to the space of action assignments, relying on the problem's structure to automatically derive the resulting fluent states.
The authors also discuss various SAT encoding strategies for planning problems, categorizing them by:
- Frame axioms: Classical (McCarthy & Hayes) vs. Explanatory (Haas).
- Action representation: Regular, Simple-split, and Bitwise.
- Planning strategy: Sequential and Parallel.
They then compare the performance of a standard SAT solver (TABLEAU) against their modified solver (TABLEAU*) on these different encodings.
Datasets
The paper evaluates its approach using a suite of planning problems generated by the MEDIC system. These problems are largely the same as those analyzed in Ernst, Millstein, & Weld (1997). Specific domains mentioned include:
- BIG-BW1
- MED-BW1
- SMALL-BW1
- FIXA-2, FIXA-1
- FERRY3
- FIX2-STRIPS, FIX1-STRIPS
- MONKEY-TEST2, MONKEY-TEST1
- HANOI-STRIPS3, HANOI-STRIPS2
- PRODIGY-SUSSMAN-3, PRODIGY-SUSSMAN-2, PRODIGY-SUSSMAN-1
- ATT-LOGISTICS3, ATT-LOGISTICS2, ATT-LOGISTICS1, ATT-LOGISTICSO
No new benchmarks were introduced; the focus was on evaluating the proposed method on existing, well-studied planning problem instances.
Key Insights and Ideas
- Determinism is Key: The most crucial insight is that fluent updates in STRIPS planning are deterministic. This simple observation has profound implications for SAT-based planning.
- Action-Centric Search: By forcing the SAT solver to only branch on action variables, we can drastically prune the search space. The solver doesn't waste time exploring assignments of fluent variables that are already determined by the chosen actions.
- Significant Speedups: Exploiting this determinism leads to substantial performance improvements, as demonstrated by the experimental results.
- Encoding Matters: While the core idea is general, the performance gains can vary depending on the specific SAT encoding used for the planning problem. Explanatory frame axioms and regular/simple-split action representations generally perform better with the proposed method.
Key Results
The experiments show that TABLEAU* (the modified solver) consistently outperforms the standard TABLEAU solver on planning problems.
- Speedup: TABLEAU achieved speedups of up to 4 orders of magnitude* in CPU time compared to TABLEAU.
- Search Space Reduction: The number of nodes in the search tree traversed by TABLEAU was also significantly smaller, reflecting the reduced search space. For example, on the crse encoding for SMALL-BW1, TABLEAU traversed 100,1689 nodes, while TABLEAU traversed only 17.
- Performance Trends:
- Explanatory encodings generally performed better than classical ones.
- Regular and simple-split action representations were often faster than bitwise representations, despite bitwise encodings reducing the number of action variables. This is attributed to the fact that bitwise encodings can lead to SAT problems with fewer binary clauses, making standard splitting heuristics less effective.
Limitations and Future Work
Limitations: * The authors acknowledge that the results are dependent on the specific problems, STRIPS formulations, SAT encoding methods, and the chosen SAT solver. Changing these factors might lead to different outcomes. * The paper focuses on a specific modification of the Davis-Putnam procedure. Other SAT solving paradigms might not benefit in the same way.
Future Work: * The paper suggests that this work opens up research into building SAT deciders specifically tailored for STRIPS planning problems. * Exploring other SAT solving techniques and encodings to further optimize planning-as-SAT is a natural next step. * Investigating how to generalize this approach to other planning formalisms beyond STRIPS.
Summary updated