Abstract

Abstract: In this report, we describe a simple probabilistic and decision-theoretic planning problem. We show how algorithms developed in the field of Markovian decision theory, a subfield a stochastic dynamic programming (operations research), can be used to construct optimal plans for this planning problem, and we present some of the complexity results known. Although their computational complexity allows only small problems to be solved optimally, the methods presented here are helpful as a theoretical framework. They allow one to make statements about the structure of an optimal plan, to guide the development of heuristic planning methods, and to evaluate their performance. We show the connection between this normative theory and universal planning, reinforcement learning, and anytime algorithms. One can easily construct a one-step planner by using a Markovian decision algorithm and a random assignment of actions to states as the initial plan. In many planning domains, it is easy for human problem solvers to construct a working plan, although it is difficult for them to find the optimal (or a close-to-optimal) plan. Therefore, we propose a two-step planning method: During the first planning phase, a working (i.e. ergodic), but not necessarily optimal plan is constructed. Sometimes, a domain specific planning method might be available for this task. We show that such a planning method can be obtained even in probabilistic domains by taking advantage of deterministic or quasi-deterministic actions. Thus, traditional (deterministic) planners can be useful in probabilistic domains. We also state a general greedy algorithm that accomplishes this task if no domain specific method is available. During the second planning phase, a Markovian decision algorithm is used to incrementally refine the initial plan and derive increasingly better plans, until the optimal plan is finally found. Since this algorithm is an anytime algorithm, we can trade off planning time and the execution reward of the plan. Finally, we briefly present a software package that implements our ideas. The probabilistic domain can be modeled using an augmented STRIPS notation. It is automatically translated into a Markovian decision problem, that is then solved.

Download the paper in pdf.

Many publishers do not want authors to make their papers available electronically after the papers have been published. Please use the electronic versions provided here only if hardcopies are not yet available. If you have comments on any of these papers, please send me an email! Also, please send me your papers if we have common interests.

This page was automatically created by a bibliography maintenance system that was developed as part of an undergraduate research project, advised by Sven Koenig.