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 veryclose 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 veryclose 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 veryclose optimum weighted shortest path. 
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 
Online Computation of Euclidean Shortest Paths in Two Dimensions
Ryan Hechenberger, Peter J Stuckey, Daniel Harabor, Pierre Le Bodic, Muhammad Aamir Cheema
Bounded Suboptimal Path Planning with Compressed Path Databases
Shizhe Zhao, Mattia Chiari, Adi Botea, Alfonso E. Gerevini, Daniel Harabor, Alessandro Saetti, Peter J. Stuckey
Computing Close to Optimal Weighted Shortest Paths in Practice
Nguyet Tran, Michael J. Dinneen, Simone Linz
New Valid Inequalities in BranchandCutandPrice for MultiAgent Path Finding
Edward Lam, Pierre Le Bodic