Gregory M. Provan
We describe a computational framework for decisiontheoretic planning, suitable for uncertain, dynamic domains in which temporal relationships between state variables can be described probabilistically. This system explicitly incorporates uncertainty and precise notions of temporal change within a relatively simple framework, extending previous work on the use of temporal probabilistic networks for planning. This framework compiles a symbolic rule-base augmented with probabilities and utilities into a temporal probabilistic network. The network is constructed incrementally, leading to more efficient and flexible networks. A variety of temporal reasoning assumptions can be specified parametrically using different parameterized time-series processes to govern the temporal evolution of the system. Plans can be assessed and refined in several ways. For example, the plan with highest expected utility can be computed, given a partial ordering on (i.e. utility values assigned to) outcomes, using standard decision-theoretic notions of utility maximization. Moreover, the probability of a single variable of interest to the problem-solver can be computed at an arbitrary future time point without generating the entire plan.