Complexity results for state-variable planning under mixed syntactical and structural restrictions
Peter Jönsson, Christer Bäckström · 1995
Most tractable planning problems reported in the literature have been defined by syntactical restrictions. To better exploit the inherent structure of problems, however, it is probably necessary to study also structural restrictions on the state-transition graph. We present an almost exhaustive map of complexity results for state-variable planning under all combinations of our previously analysed syntactical (P, U, B, S) and structural (I, A, O) restrictions, considering both optimal and non-optimal plan generation. 1 Introduction Many planning problems in manufacturing and process industry are believed to be highly structured, thus allowing for efficient planning if exploiting this structure. However, a `blind' domain-independent planner will most likely go on tour in an exponential search space even for tractable problems. Although heuristics may help a lot, they are often not based on a sufficiently thorough understanding of the underlying problem structure to guarantee efficiency ...