Practical Route Planning Under Delay Uncertainty: Stochastic Shortest Path Queries

Sejoon Lim, Christian Sommer, Evdokia Nikolova, and Daniela Rus
RSS 2012 - Robotics: Science and Systems VIII (pp. 249-256)

We describe an algorithm for stochastic motion planning and applications to route planning in the presence of traffic delays. We improve on the prior state of the art by designing, analyzing, implementing, and evaluating data structures that answer approximate stochastic shortest path queries. For example, our data structure can be used to efficiently compute paths that maximize the probability of arriving at a destination before a given time deadline.

Our main theoretical result is an algorithm that, given a directed planar network with edge lengths characterized by expected travel time and variance, pre-computes a data structure in quasi-linear time such that stochastic approximate shortest-path queries can be answered in poly-logarithmic time (actual worst-case bounds depend on the probabilistic model).

Our main experimental results are two-fold: (i) we provide methods to extract travel-time distributions from a large set of heterogenous GPS traces and we build a stochastic model of an entire city, and (ii) we adapt our algorithms to work for real-world road networks, we provide an efficient implementation, and we evaluate the performance of our method for the model of the aforementioned city.

@inproceedings{LSNR12,
 author    = {Sejoon Lim 
              and Christian Sommer 
              and Evdokia Nikolova 
              and Daniela Rus},
 title     = {Practical Route Planning Under Delay Uncertainty: 
              Stochastic Shortest Path Queries},
 booktitle = {Robotics: Science and Systems VIII},
 year      = {2012},
 pages     = {249--256},
 url       = {http://dx.doi.org/10.15607/RSS.2012.VIII.032},
 doi       = {10.15607/RSS.2012.VIII.032},
}

Official version
Local version (1.0 MB)

Home → Publications → Practical Route Planning Under Delay Uncertainty: Stochastic Shortest Path Queries