An Average Case Analysis of Planning

Abstract

I present an average case analysis of propositional STRIPS planning. The analysis assumes that each possible precondition (likewise postcondition) is equally likely too appear within an operator. Under this assumption, I derive bounds for when it is highly likely that a planning instanee can be efficiently solved, either by finding a plan or proving that no plan exists. Roughly, if planning instances have no conditions (ground atoms), g goals, and O(n9√δ) operators, then a simple, efficient algorithm can prove that no plan exists for at least 1 - 8 of the instances. If instances have Ω(n(ln g)(ln g/δ)) operators, then a simple, efficient algorithm can find a plan for at least 1-δ of the instances. A similar result holds for plan modification, i.e., solving a planning instance that is close too another planning instance with a known plan. Thus it would appear that propositional STRIPS planning, a PSPACE-complete problem, is hard only for narrow parameter ranges, which complements previous average-case analyses for NP-complete problems. Future work is needed to narrow the gap between the bounds and to Consider more realistic distributional assumptions and more sophisticated algorithms.