Guiding the Search for the Euclidean Shortest Path Problem

Abstract

We consider the problem of reducing the search space of algorithms which solve the Euclidean Shortest Path Problem by traversing a precomputed navigation mesh. Heuristics can be used to guide this traversal. We show how upper and lower bounds to the optimal path length can be combined into an independent heuristic which considerably reduces the search space of such an algorithm. In our experiments we use our heuristic in an existing routing algorithm and find that our approach yields a substantial speedup for complicated paths.