| On the utility of Plan-space (Causal) Encodings (1999) | |||||||||||||||||
Abstract | |||||||||||||||||
| Recently, casting planning as propositional satisfiability has been shown to be a very promising technique for plan synthesis. It has been claimed that SAT encodings for planning problems can be derived from each of the traditional refinement planning paradigms. Although encodings based both on state-space planning and on plan-space (causal) planning have been proposed, most implementations and tradeoff evaluations primarily use state-based encodings. This is surprising given both the prominence of plan-space planners in traditional planning, as well as the recent claim that lifted versions of causal encodings provide the smallest encodings. In this paper we attempt a systematic analytical and empiricial comparison of plan-space (causal) encodings and statespace encodings. We start by characterizing a large spectrum of plan-space encodings, and provide several encodings that are much smaller than those previously proposed. We then show that the smallest causal encodings cannot be small... | |||||||||||||||||
Publication details | |||||||||||||||||
| |||||||||||||||||