On the limits of planning over belief states under strict uncertainty

A recent trend in planning with incomplete information is to model the actions of a planning problem as nondeterministic transitions over the belief states of a planner, and to search for a plan that terminates in a desired goal state no matter how these transitions turn out. We show that this view of planning is fundamentally limited. Any plan that is successful by this criteria has an upper bound on the number of actions it can execute. Specifically, the account will not work when iterative plans are needed. We also show that by modifying the definition slightly, we obtain another account of planning that does work properly even for iterative plans. Although the argument is presented in an abstract form, we illustrate the issues using a simple concrete example. Copyright © 2006, American Association for Artificial Intelligence.