The BURIDAN Planner

Overview

Classical planning assumes complete and deterministic information about the world state and the effects of actions. These assumptions are inappropriate for many domains: turning the ignition key might usually start one's old car, but occasionally fail for unknown reasons. Even if a deterministic model is possible for a given domain, it might be too complex to be useful. For example, when deciding between an indoor and an outdoor site for a wedding, one is likely to use a probabilistic model to forecast the weather rather than project the cloud dynamics. The initial world state is also a source of uncertainty: will the freeways be crowded?

This paper presents a planning algorithm that doesn't depend on the assumptions of complete and deterministic information. We use a probability distribution over possible worlds to model imperfect information about the initial world state, and we model actions using a conditional probability distribution over changes to the world.

Adopting a probabilistic model complicates the definition of plan success. Instead of terminating when it builds a plan that provably achieves the goal, our planner terminates when it builds a plan that is sufficiently likely to succeed: our algorithm produces a plan such that the probability of the plan achieving the goal exceeds a user-supplied probability threshold, if such a plan exists.

Our work on BURIDAN makes several important contributions. First, we define a symbolic action representation and provide it probabilistic semantics. Second, we describe an implemented algorithm, named after Jean Buridan, for probabilistic planning. Third, we prove the planner both sound and complete. Fourth, we compare the efficiency of four different probabilistic assessment algorithms both analytically and with empirical experiments. Finally, we explore the interface between the process of generating plans and the process of evaluating them.

An implementation of BURIDAN is also available. This is a Lisp source code archive in compressed tar format, and this is a few suggestions if you're having trouble.

Publications

• Long (Artificial Intelligence, 76:239-86) and short (AAAI-94, pp 1073-8) papers describing BURIDAN are available.