Tractable Planning with State Variables by Exploiting Structural Restrictions

Peter Jonsson, Peter Jonsson

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. Hence, we take an intermediate approach, using a state-variable 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 page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.