2次元格子における大域最適な一対全経路計画のための厳密な波面伝播
Exact Wavefront Propagation for Globally Optimal One-to-All Path Planning on 2D Cartesian Grids
2次元格子上で可視性に基づく解析的距離関数を利用し、O(n)の計算量とメモリで大域最適な一対全経路を厳密に計算するアルゴリズムを提案した。
著者: Ibrahim Ibrahim, Joris Gillis, Wilm Decré, Jan Swevers
分類: cs.RO, cs.CG
原文アブストラクト
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.
