The expected shortest path problem: algorithms and experiments
Deniz Sarıöz, Victor Dan · Journal of computing sciences in colleges · 2001
In this project, we designed, implemented, and tested algorithms for the Expected Shortest Path problem. The problem can be stated as follows: given a weighted, directed graph whose edges can only be traversed with given probabilities, find the path with the shortest expected length from a given start node to a given goal node. This problem is at the center of our vision-guided mobile robot project, where the robot has to navigate the probabilistic graph defined by visibilities between landmarks. Applications of the expected shortest path problem include route planning given known traffic conditions, as well as similar decision problems in the presence of uncertainty.