A Stochastic Model of Actions and Plans for Anytime Planning under Uncertainty.

Building planning systems that operate in real domains requires coping with both uncertainty and time pressure. This article describes a model of reaction plans, which are generated using a formalization of actions and of state descriptions in probabilistic logic, as a basis for anytime planning under uncertainty. The model has the following main features. At the action level, we handle incomplete and ambiguous domain information, and reason about alternative action effects whose probabilities are given. On this basis, we generate reaction plans that specify different courses of action, reflecting the domain uncertainty and alternative action effects; if generation time was insufficient, these plans may be left unfinished, but they can be reused, incrementally improved, and finished later. At the planning level, we develop a framework for measuring the quality of plans that takes domain uncertainty and probabilistic information into account using Markov chain theory; based on this framework, one can design anytime algorithms focusing on those parts of an unfinished plan first, whose completion promises the most "gain". Finally, the plan quality can be updated during execution, according to additional information acquired, and can therefore be used for on-line planning. [ABSTRACT FROM AUTHOR]