ECAI 2004 Conference Paper

[full paper]

Evaluation Strategies for Planning as Satisfiability

Jussi Rintanen

In this paper we report new developments in satisfiability planning emerging from a shift of paradigm in evaluation strategies (where our contribution in this work lies) together with important qualitative and quantitative improvements in satisfiability algorithms that have been taking place in the recent years, leading to dramatically improved efficiency of satisfiability planning. We investigate different evaluation strategies for planning problems represented as a constraint satisfaction problem or as a satisfiability problem. The standard evaluation strategy -- evaluating the formulae sequentially increasing the length one step at a time -- guarantees that a plan corresponding to the first satisfiable formula is found first, but this strategy is often not the best possible in terms of runtime. We present evaluation strategies based on parallel or interleaved evaluation of several formulae, and show that on many problems this leads to substantially improved runtimes, sometimes several orders of magnitude. The cost of the improved runtimes is a possible decline in plan quality: some of the optimality guarantees of the standard evaluation strategy are lost, but this may be acceptable because of the improved runtimes.

Keywords: planning, satisfiability testing

Citation: Jussi Rintanen: Evaluation Strategies for Planning as Satisfiability. In R.López de Mántaras and L.Saitta (eds.): ECAI2004, Proceedings of the 16th European Conference on Artificial Intelligence, IOS Press, Amsterdam, 2004, pp.682-686.