.png){kind=icon}
.png){kind=icon}
Return
State-variable planning under structural restrictions: algorithms and complexity
.png){kind=icon}
OA
AI
DOI：10.1016/S0004-3702(98)00003-4.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Computationally tractable planning problems reported in the literature so far have almost exclusively been defined by syntactical restrictions. To better exploit the inherent structure in problems, it is probably necessary to study also structural restrictions on the underlying state-transition graph. The exponential size of this graph, though, makes such restrictions costly to test. Hence, we propose an intermediate approach, using a state-variable model fcr planning and defining restrictions on the separate state-transition graphs for each state variable. We identify such restrictions which can tractably be tested and we present a planning algorithm which is correct and runs in polynomial time under these restrictions. The algorithm has been implemented and it outperforms Graphplan on a number of test instances. In addition, we present an exhaustive map of the complexity results for planning under all combinations of four previously studied syntactical restrictions and our five new structural restrictions. This complexity map considers both the optimal and non-optimal plan generation problem. (C) 1998 Elsevier Science B.V.
Keywords:
planning
algorithms
complexity
tractability
structure
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
13.9
Papers:
6.1K
Citations:
1.9W
Organization
No organization information available