@TECHREPORT{R-95-17,
PSURL = {/publications/cgi-bin/tr-fetch.pl?r-95-17+ps},
NUMBER = {R-95-17},
INSTITUTION = ida,
ADDRESS = idaaddr,
YEAR = {1995},
AUTHOR = {Jonsson, Peter and B{\"a}ckstr{\"o}m, Christer},
TITLE = {Complexity Results for State-Variable Planning under Mixed Syntactical and Structural Restrictions},
ABSTRACTURL = {/publications/cgi-bin/tr-fetch.pl?r-95-17+abstr},
ABSTRACT = {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 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 in combination with two new restrictions (A+, A-). The complexity map considers both optimal and non-optimal plan generation.}