|
Optimal Route Planning under
Uncertainty
Evdokia Nikolova, Matthew Brand & David Karger
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 times are random variables 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 expected cost, as well as the
computational/combinatorial difficulty of efficiently finding an optimal
path which minimizes the expected 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.
References:
[1] Evdokia Nikolova,
Matthew Brand and David
Karger. ``Optimal
Route Planning Under Uncertainty." In Proceedings of 2006 International
Conference on Automated Planning & Scheduling (ICAPS 2006).
|
|
