TR2006-060
Optimal Route Planning under Uncertainty
-
- "Optimal Route Planning under Uncertainty", International Conference on Automated Planning and Scheduling (ICAPS), June 2006.BibTeX TR2006-060 PDF
- @inproceedings{Nikolova2006jun,
- author = {Nikolova, E. and Brand, M. and Karger, D.R.},
- title = {Optimal Route Planning under Uncertainty},
- booktitle = {International Conference on Automated Planning and Scheduling (ICAPS)},
- year = 2006,
- month = jun,
- url = {https://www.merl.com/publications/TR2006-060}
- }
,
- "Optimal Route Planning under Uncertainty", International Conference on Automated Planning and Scheduling (ICAPS), June 2006.
-
MERL Contact:
Abstract:
We present new complexity results and efficient algorithms for optimal route planning in the presence of uncertainty. We employ a decision theoretic framework for defining the optimal route: for a given source S and destination T in the graph, we seek an ST-path of lowest expected cost where the edge travel trimes are eandom variable and the cost is a nonlinear function of total travel time. Although this is a natural model for route-planning on real-world road networks, results are sparse due to the analytic difficulty of finding closed form expressions for the exptected cost (Fan, Kalaba and Moore), as well as the computational/combinatorial difficulty of efficiently finding an optimal path which minimizes the exptected cost. We identify a family of appropriate cost models and travel time distributions that are closed under convolution and physically valid. We obtain hardness results for routing problems with a given start time and cost functions with a global minimum, in a variety of deterministic and stochastic settings. In general the global cost is not separable into edge costs, precluding classic shortest-path approaches. However, using partial minimization techniques, we exhibit an efficient solution via dynamic programming with low polynomial complexity.
Related News & Events
-
NEWS ICAPS 2006: publication by Matthew Brand and others Date: June 6, 2006
Where: International Conference on Automated Planning and Scheduling (ICAPS)
MERL Contact: Matthew BrandBrief- The paper "Optimal Route Planning under Uncertainty" by Nikolova, E., Brand, M. and Karger, D.R. was presented at the International Conference on Automated Planning and Scheduling (ICAPS).