基于可视性精确计算路径，实现二维网格全局最优规划。
Exact Wavefront Propagation for Globally Optimal One-to-All Path Planning on 2D Cartesian Grids
- 用可视性驱动的解析距离函数实现波前精确传播
- 时间与空间复杂度均为O(n)，在复杂环境中速度和精度更优
- 支持单起点或多起点，适合实时导航与机器人路径规划
本文提出一种在二维笛卡尔网格上实现全局最优路径规划的高效算法，计算与内存复杂度均为 $/mathcal{O}(n)$。不同于依赖欧几里得方程近似离散解的传统行进方法，本方法通过基于可视性的解析距离函数实现精确波前传播。算法利用动态规划子程序高效求解可视性查询。在与先进任意角度路径规划器的对比中，本方法在复杂环境下的速度与准确性均表现更优。其天然支持从单点或多个起点到所有网格点的全局最优路径，无需对每条路径查询额外进行梯度下降优化。此外，本文还提供该算法的贪心版本及开源C++实现。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。