IDA Dept. of Computer and Information science, Linköping University

IDA Technical Reports: abstract

Generated: Sun, 21 Dec 2014 16:07:39

Bäckström, C. (1995). Expressive Equivalence of Planning Formalisms. Technical Report LiTH-IDA-R-95-03, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),

Abstract: A concept of expressive equivalence for planning formalisms based on polynomial transformations is defined. It is argued that this definition is reasonable and useful both from a theoretical and from a practical perspective; if two languages are equivalent, then theoretical results carry over and, more practically, we can model an application problem in one language and then easily use a planner for the other language. In order to cope with the problem of exponentially sized solutions for planning problems an even stronger concept of expressive equivalence is introduced, using the novel {\em ESP-reduction}. Four different formalisms for propositional planning are then analyzed, namely two variants of STRIPS, ground TWEAK and the SAS$^+$ formalism. Although these may seem to exhibit different degrees of expressive power, it is proven that they are, in fact, expressively equivalent under ESP-reduction. This means that neither negative goals, partial initial states nor multi-valued state variables increase the expressiveness of `standard' propositional STRIPS.


Goto (at Linköping University): CS Dept TR Overview
<webmaster@ida.liu.se>