arXiv cs.AI· Yiyuan Zou, Clark Borst·· 3 天前AI 评分20
Zeta* 与 Zeta*-SIPP：静态与动态环境下的最优任意角度路径规划
Optimal any-angle path planning in static and dynamic environments
AI 导读
研究提出椭圆前向扩展和视野（field of view）两项通用技术，在保持最优性的前提下加速任意角度路径规划，并据此开发了静态环境的 Zeta* 与动态环境的 Zeta*-SIPP。Zeta* 结合前向扫描后性能与当前最优算法 Anya 相当，且更易扩展；Zeta*-SIPP 在基准测试中相比最优规划器 TO-AA-SIPP 实现超过一个数量级的加速。
正文 · 原文
Abstract: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. Many any-angle path-planning algorithms have been proposed, but only a few can guarantee optimal solutions. 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. For example, Zeta*-SIPP, which extends Zeta* by integrating Safe Interval Path Planning (SIPP), can find time-optimal any-angle paths in dynamic environments. Benchmarking results show that Zeta*-SIPP achieves more than an order-of-magnitude speedup over the state-of-the-art optimal planner TO-AA-SIPP when using either scanning method. Overall, this research identifies the key requirements for achieving optimal any-angle path planning and introduces a unified approach suitable for different environments.
| Comments: | 27 pages, 15 figures |
| Subjects: | Robotics (cs.RO); Artificial Intelligence (cs.AI) |
| Cite as: | arXiv:2607.00065 [cs.RO] |
| (or arXiv:2607.00065v2 [cs.RO] for this version) | |
| https://doi.org/10.48550/arXiv.2607.00065 arXiv-issued DOI via DataCite |
|
| Journal reference: | Artificial Intelligence 361 (2026): 104642 |
| Related DOI: | https://doi.org/10.1016/j.artint.2026.104642
DOI(s) linking to related resources |
Submission history
From: Yiyuan Zou [view email]
[v1]
Tue, 30 Jun 2026 12:40:23 UTC (1,265 KB)
[v2]
Tue, 13 Oct 2026 12:37:54 UTC (3,319 KB)
来源：arXiv cs.AI · arxiv.org