Ryan Hechenberger, Peter J Stuckey, Daniel Harabor, Pierre Le Bodic, Muhammad Aamir Cheema |
PosterID:
73
PDF
Slides
Poster
BibTeX
|
| We consider the online version of Euclidean Shortest Path (ESP): a problem that asks for distance minimal trajectories between traversable pairs of points in the plane. The problem is made challenging because each trajectory must avoid a set of non-traversable obstacles represented as polygons. To solve ESP practitioners will often preprocess the environment and construct specialised data structures, such as visibility graphs and navigation meshes. Pathfinding queries on these data structures are fast but the preprocessed data becomes invalidated when obstacles move or change. In this work we propose RayScan, a new algorithmic approach for ESP which is entirely online. The central idea is simple: each time we expand a node we also cast a ray toward the target. If an obstacle intersects the ray we scan its perimeter for a turning point; i.e. a vertex from which a new ray can continue unimpeded towards the target. RayScan is fast, optimal and entirely online. Experiments show that it can significantly improve upon current state-of-the-art methods for ESP in cases where the set of obstacles is dynamic. | |
| 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