An Average Case Analysis of Planning

Tom Bylander

I present an average case analysis of propositional STRIPS planning. The analysis assumes that each possible precondition (likewise postcondition) is equally likely to appear within an operator. Under this assumption, 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 have n conditions (ground atoms), g goals, and O(n g÷d) operators, then a simple, efficient algorithm can prove that no plan exists for at least 1 - d of the instances. If instances have W(n(ln g)(ln g/d)) operators, then a simple, efficient algorithm can find a plan for at least 1 - d of the instances. 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 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 assumptious and more sophisticated algorithms.


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.