In this chapter, we explore various approaches for using probabilistic models to handle the uncertainty and nondeterminism in planning and acting problems. These approaches are mostly based on dynamic programming optimization methods for Markov decision processes.We explain the basic principles and develop heuristic search algorithms for stochastic shortest-path problems. We also propose several sampling algorithms for online probabilistic planning and discuss how to augment with probabilistic models refinement methods for acting. The chapter also discusses the critical issue of specifying a domain with probabilistic models.

Our motivations for using probabilistic models, and our main assumptions, are briefly introduced next. Section 6.2 defines stochastic shortest-path problems and basic approaches for solving them. Different heuristic search algorithms for these problems are presented and analyzed in Section 6.3.Online probabilistic planning approaches are covered in Section 6.4.Refinement methods for actingwith probabilisticmodels are presented in Section 6.5. Sections 6.6 and 6.7 are devoted to factored representations and domain modeling issues with probabilistic models, respectively. The main references are given in the discussion and historical remarks Section 6.8. The chapter ends with exercises.

INTRODUCTION

Some of the motivations for deliberation with probabilistic models are similar to those introduced in Chapter 5 for addressing nondeterminism: the future is never entirely predictable, models are necessarily incomplete, and, even in predictable environments, complete deterministic models are often too complex and costly to develop. In addition, probabilistic planning considers that the possible outcomes of an action are not equally likely. Sometimes, one is able to estimate the likelihood of each outcome, relying for example on statistics of past observations. Probabilistic planning addresses those cases in which it is desirable to seek plans optimized with respect to the estimated likelihood of the effects of their actions.

The usual formal model of probabilistic planning is that of Markov decision processes (MDPs). An MDP is a nondeterministic state-transition system together with a probability distribution and a cost distribution.The probability distribution defines how likely it is to get to a state s' when an action a is performed in a state s.

A probabilistic state-transition system is said to be Markovian if the probability distribution of the next state depends only on the current state and not on the sequence of states that preceded it.