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. | |
| 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 Branch-and-Cut-and-Price for Multi-Agent Path Finding
Edward Lam, Pierre Le Bodic