提出高效最优的任意角度路径规划方法,支持动态障碍物环境。
Optimal any-angle path planning in static and dynamic environments

- 用椭圆邻域缩小搜索范围,结合视野机制加速可见性判断。
- 在静态环境比Anya更快,在动态环境比TO-AA-SIPP快20倍以上。
- 适用于空域、仓库等开放场景,适合需最优路径的机器人导航。
任意角度路径规划通过允许顶点间任意方向移动,突破传统图规划中预定义边的限制,可在连续空间中生成更直、更短的路径,特别适用于空域、仓库和海洋等开放区域的导航。尽管已有多种任意角度规划算法,但仅有少数能保证最优解,尤其在动态障碍物环境下。本文聚焦网格上的最优任意角度路径规划,提出两项通用加速技术:1)椭圆前向扩展,利用椭圆邻域限制搜索空间;2)视野机制,替代传统视线检测以提升效率。为融合二者,引入反向扫描(从开放节点建立视觉连接)与正向扫描(从封闭节点启动扫描)。基于此,分别开发了适用于静态环境的Zeta*和动态环境的Zeta*-SIPP。Zeta*结合正向扫描时性能接近前沿算法Anya,且易于扩展至动态场景(如Zeta*-SIPP)。Zeta*-SIPP无论采用哪种扫描方式,均比当前最优的TO-AA-SIPP快20倍以上。研究明确了实现最优任意角度路径规划的关键条件,并提出统一适用不同环境的方法。
原文摘要 · Abstract (English)
Any-angle path planning extends traditional graph-based path planning by allowing movement between any pair of vertices, rather than being restricted by predefined edges. It can find straighter and shorter paths in continuous space with graphs, making it particularly suitable for navigation in open areas such as airspaces, warehouses, and oceans. Many any-angle path-planning algorithms have been proposed, but only a few can guarantee optimal solutions, especially in the presence of dynamic obstacles. To address this challenge, this article focuses on optimal any-angle path planning on grids and introduces two general techniques that accelerate computation while preserving optimality in both static and dynamic environments: 1) elliptical forward expansion, which leverages ellipse-based neighborhoods to restrict the search space, and 2) field of view, which replaces traditional line-of-sight methods to speed up visibility checks. To integrate these two techniques, inverted and forward scanning are introduced. Inverted scanning establishes visual connections from open nodes, whereas forward scanning initiates scans from closed nodes. Building on the proposed techniques, Zeta* and Zeta*-SIPP are developed for static and dynamic environments respectively. Zeta*, when combined with forward scanning, is similar to the state-of-the-art algorithm Anya and attains comparable performance. Unlike Anya, Zeta* can be readily extended to other settings, such as dynamic environments (e.g., Zeta*-SIPP). Zeta*-SIPP, with either scanning method, is more than 20 times faster than the corresponding state-of-the-art optimal planner TO-AA-SIPP. Overall, this research identifies the key requirements for achieving optimal any-angle path planning and introduces a unified approach suitable for different environments.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。