Practical Route Planning Under Delay Uncertainty: Stochastic Shortest Path Queries

Sejoon Lim, Christian Sommer, Evdokia Nikolova, Daniela Rus

2012 · 35 citations · 20 references

DOIFull text

Open access

Concepts

Abstract

We describe an algorithm for stochastic path 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 structures can be used to efficiently compute paths that maximize the probability of arriving at a destination before a given time deadline.

References

20