Optimal Route Planning under Uncertainty

    •  Nikolova, E., Brand, M., Karger, D.R., "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 = {}
      • }
  • MERL Contact:
TR Image
Minimum-cost envelopes for the same network under quadratic and quadratic+exponential cost functions superimposed in a neighborhood of their global optima.

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 E. Brand
      • 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).