On the Limits of Planning over Belief States under Strict Uncertainty

Sebastian Sardina, Giuseppe De Giacomo, Yves Lesperance, Hector Levesque

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.

Subjects: 1.11 Planning; 9. Foundational Issues

Submitted: Mar 6, 2006

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.