Computing Close to Optimal Weighted Shortest Paths in Practice

Nguyet Tran, Michael J. Dinneen, Simone Linz

PosterID: 75 PDF Slides Poster BibTeX

This paper proposes a new practical algorithm for the weighted region problem (WRP). The objective of WRP is to find a minimum cost path between two vertices in an environment of different regions where each region incurs a traversal cost per unit distance. Currently, there is no practical algorithm that solves this problem exactly. Among the approximation methods that solve instances of WPR, there is a limited number of algorithms that compute paths whose lengths are close to optimal, which we call very-close optimum paths. However, they are considered as theoretical methods. On the other hand, algorithms for solving WRP that can be applied to practical data sets (using decomposition ideas or heuristics) are not guaranteed to find a very-close optimum path within an acceptable amount of time. In this paper, we consider an alternative method for solving WRP that exploits Snell's law of physical refraction. We compare the performance of our new algorithm with that of two existing algorithms, using at least 500 test cases for each such comparison. The experimental results show that our algorithm runs remarkably fast in practice and returns a very-close optimum weighted shortest path.

Session Aus4: Path Planning
Canb 10/29/2020, 11:00 – 12:00
10/30/2020, 20:00 – 21:00
Paris 10/29/2020, 01:00 – 02:00
10/30/2020, 10:00 – 11:00
NYC 10/28/2020, 20:00 – 21:00
10/30/2020, 05:00 – 06:00
LA 10/28/2020, 17:00 – 18:00
10/30/2020, 02:00 – 03:00