Encoding plans in propositional logic
Henry Kautz, David McAllester, Bart Selman · 1996
In recent work we showed that planning problems can be efficiently solved by general propositional satisfiability algorithms (Kautz and Selman 1996). A key issue in this approach is the development of practical reductions of planning to SAT. We introduce a series of different SAT encodings for STRIPS-style planning, which are sound and complete representations of the original STRIPS specification, and relate our encodings to the Graphplan system of Blum and Furst (1995). We analyze the size complexity of the various encodings, both in terms of number of variables and total length of the resulting formulas. This paper complements the empirical evaluation of several of the encodings reported in Kautz and Selman (1996). We also introduce a novel encoding based on the theory of causal planning, that exploits the notionof "lifting" from the theorem-proving community. This new encoding strictly dominates the others in terms of asymptotic complexity. Finally, we consider further reductions i...
Cited by 266 works.
Authors
References
- Strips: A new approach to the application of theorem proving to problem solving
- Some Philosophical Problems from the Standpoint of Artificial Intelligence
- A machine program for theorem-proving
- A new method for solving hard satisfiability problems
- Pushing the envelope: planning, propositional logic, and stochastic search
- Hard and easy distributions of SAT problems
- UCPOP: a sound, complete, partial order planner for ADL
- Systematic nonlinear planning
- Planning as satisfiability
- Fast Planning Through Planning Graph Analysis.