Path Planning under Time-Dependent Uncertainty

Authors:

Michael P. Wellman, Kenneth Larson, Matthew Ford, and Peter R. Wurman
Univ Michigan AI Laboratory
1101 Beal Avenue
Ann Arbor, MI 48109-2110 USA
e-mail: wellman@umich.edu

Abstract:

Standard algorithms for finding the shortest path in a graph require that the cost of a path be additive in edge costs, and typically assume that costs are deterministic. We consider the problem of uncertain edge costs, with potential probabilistic dependencies among the costs. Although these dependencies violate the standard dynamic-programming decomposition, we identify a weaker stochastic consistency condition that justifies a generalized dynamic-programming approach based on stochastic dominance. We present a revised path-planning algorithm and prove that it produces optimal paths under time-dependent uncertain costs. We illustrate the algorithm by applying it to a model of stochastic bus networks, and present sample performance results comparing it to some alternatives. For the case where all or some of the uncertainty is resolved during path traversal, we extend the algorithm to produce optimal policies.

Keywords:

path planning, uncertainty, time dependence, stochastic dominance, A*

Availability:

This report is available in compressed postscript format. The manuscript is based on a paper presented at UAI-95:

• Path planning under time-dependent uncertainty (MP Wellman, M Ford, and K Larson). Eleventh Conference on Uncertainty in Artificial Intelligence, pages 532-539, August 1995. [abstract]