A probabilistic analysis of prepositional STRIPS planning

摘要

I present a probabilistic analysis of prepositional STRIPS planning. The analysis considers two assumptions. One is that each possible precondition (likewise postcondition) of an operator is selected independently of other pre- and postconditions. The other is that each operator has a fixed number of preconditions (likewise postconditions). Under both assumptions, I derive bounds for when it is highly likely that a planning instance can be efficiently solved, either by finding a plan or proving that no plan exists. Roughly, if planning instances under either assumption have n propositions (ground atoms) and g goals, and the number of operators is less than an O(n In g) bound, then a simple, efficient algorithm can prove that no plan exists for most instances. If the number of operators is greater than an Ω(n In g) bound, then a simple, efficient algorithm can find a plan for most instances. The two bounds differ by a factor that is exponential in the number of pre- and postconditions. A similar result holds for plan modification, i.e., solving a planning instance that is close to another planning instance with a known plan. Thus it appears that prepositional STRIPS planning, a PSPACE-complete problem, exhibits a easy-hard-easy pattern as the number of available operators increases with a narrow range of hard problems. An empirical study demonstrates this pattern for particular parameter values. Because prepositional STRIPS planning is PSPACE-complete, this extends previous phase transition analyses, which have focused on NP-complete problems. Also, the analysis shows that surprisingly simple algorithms can solve a large subset of the planning problem.