Tractable Planning with State Variables by Exploiting Structural Restrictions

Abstract

So far, tractable planning problems reported in the literature have been defined by syntactical restrictions. To better exploit the inherent structure in problems, however, it is probably necessary to study also structural restrictions on the state-transition graph. Such restrictions are typically computationally hard to test, though, since this graph is of exponential size. We take an intermediate approach, using a statevariable model for planning and restricting the state-transition graph implicitly by restricting the transition graph for each state variable in isolation. We identify three such restrictions which are tractable to test and we present a planning algorithm which is correct and runs in polynomial time under these restrictions. This research was sponsored by the Swedish Research Council for the Engineering Sciences (TFR) under grants Dnr. 92-143 and Dnr. 93-00291. A short version of this report appears in the Proceedings of the Twelth National Conference of the America...