Exact Wavefront Propagation for Globally Optimal One-to-All Path Planning on 2D Cartesian Grids

Autor:	Ibrahim, Ibrahim, Gillis, Joris, Decré, Wilm, Swevers, Jan
Rok vydání:	2024
Předmět:	Computer Science - Robotics Computer Science - Computational Geometry
Druh dokumentu:	Working Paper
Popis:	This paper introduces an efficient $\mathcal{O}(n)$ compute and memory complexity algorithm for globally optimal path planning on 2D Cartesian grids. Unlike existing marching methods that rely on approximate discretized solutions to the Eikonal equation, our approach achieves exact wavefront propagation by pivoting the analytic distance function based on visibility. The algorithm leverages a dynamic-programming subroutine to efficiently evaluate visibility queries. Through benchmarking against state-of-the-art any-angle path planners, we demonstrate that our method outperforms existing approaches in both speed and accuracy, particularly in cluttered environments. Notably, our method inherently provides globally optimal paths to all grid points, eliminating the need for additional gradient descent steps per path query. The same capability extends to multiple starting positions. We also provide a greedy version of our algorithm as well as open-source C++ implementation of our solver. Comment: 7 Pages, IEEE RA-L Accepted Version Preprint
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2409.11545 Zobrazit plný text záznamu View this record from Arxiv