💻 computer science

Optimal any-angle path planning in static and dynamic environments

本文介绍了 Zeta* 和 Zeta*-SIPP，这两种是用于静态和动态环境下最优任意角度路径规划的新型算法，它们利用椭圆前向扩展和视野技术，在保持解的最优性的同时实现了显著的速度提升。

原作者： Yiyuan Zou, Clark Borst

发布于 2026-07-02

📖 1 分钟阅读☕ 轻松阅读

原作者： Yiyuan Zou, Clark Borst

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正在试图引导一架无人机从起点穿过一个充满柱子（障碍物）的大型开放仓库到达终点。你的目标是尽可能快地到达那里。

旧的方法（“网格”问题）
传统的导航软件，比如经典的 A* 算法，将世界视为一个巨大的棋盘。它只能让无人机从一个方格的中心移动到相邻方格的中心。这迫使无人机走成“阶梯状”的路径，不断进行 45 度的转向。这就像你试图开车穿过一条街道，但却被允许只能在每个路口转弯，即使你可以直接横穿一片空地。结果是，路径虽然安全，但比实际需要的更长、更颠簸。

“任意角度”的梦想
科学家们想要一种能让无人机沿直线飞行、像鸟儿一样切角飞行的方法。这被称为任意角度路径规划（Any-Angle Path Planning）。

Theta* 是早期的尝试。它就像是一个人类在观察周围并说：“嘿，我能看到下一个柱子，所以我可以直接飞向它。”它让路径变得更直，但并不保证一定能找到绝对最短的路线。
Anya 是下一次巨大的飞跃。它极其聪明且快速，能够找到真正的最短路径，但它就像一辆专门的赛车：它在平坦、静态的赛道（静态环境）上表现完美，但很难针对颠簸、变化的赛道（障碍物会移动的动态环境）进行修改。

新的解决方案：Zeta* 和 Zeta*-SIPP
本文介绍了一个名为 Zeta*（针对静态世界）和 Zeta*-SIPP（针对带有移动障碍物的动态世界）的新算法家族。作者创造了两种“超能力”，使这些算法既快速又完美。

超能力 1：“椭圆搜索”（椭圆赛道）

想象一下你正在一个巨大的草坪里寻找丢失的钥匙。传统的搜索可能会检查你周围圆圈内的每一根草。
作者意识到，如果你知道起点和终点在哪里，你不需要检查左侧或右侧远离你的草。你只需要检查在起点和终点之间画出的一个**椭圆（ellipse）**区域内的区域。

工作原理： 算法画出一个隐形的椭圆。任何位于这个椭圆之外的点在数学上都被证明是更长、更差的路径。因此，算法会忽略椭圆之外的所有内容。
益处： 它极大地减少了计算机需要查找的位置，在保证最短路径的同时节省了大量时间。

超能力 2：“手电筒”（视野）

当无人机飞行时，它需要知道前方是否被阻挡。

旧的方法（视线法/Line of Sight）： 想象一下通过向每一个方格逐一发射激光笔来检查路径。如果你必须检查 100 个方格，你就得发射 100 次激光。这很慢。
新的方法（阴影投射/Shadowcasting）： 想象打开一个强力手电筒。与其一个方格一个方格地检查，不如让光线瞬间充满整个区域。如果一根柱子挡住了光线，它会在后面投下一个“影子”。算法会立即知道，由于没有检查每个方格，那个影子里的所有东西都是被阻挡的。
益处： 这种“手电筒”方法比旧的“激光笔”方法检查可见性的速度要快得多。

整合在一起：两种扫描方式

为了让这些超能力协同工作，作者发明了两种扫描地图的方式：

反向扫描（Inverted Scanning）： 你站在刚刚发现的一个新位置上，向外照射手电筒，看看你能到达哪里。
正向扫描（Forward Scanning）： 你站在一个已经访问过的位置上，向前照射手电筒，看看现在可以到达哪些新位置。

结果：Zeta* 对比 Zeta*-SIPP

Zeta*（静态世界）： 这是针对地图中没有任何移动物体的版本（例如带有固定柱子的仓库）。它利用“手电筒”和“椭圆”技巧来寻找完美路径。它几乎和当前的冠军（Anya）一样快，但它更像是构建在“乐高积木”之上而非“定制赛车”之上，这意味着它更容易被修改用于其他用途。
Zeta*-SIPP（动态世界）： 这是针对地图中存在移动障碍物的版本（例如无人机之间互相飞行）。这是最难的问题，因为在飞行过程中路径可能会被阻挡。
- 该论文声称，在寻找这些移动环境中的完美路径时，Zeta*-SIPP 比之前的最佳方法（TO-AA-SIPP）快了 20 倍以上。
- 它通过结合“椭圆”搜索（以忽略糟糕路径）、“手电筒”式可见性检查（快速检查移动阻挡）以及“懒惰（lazy）”检查方法（只有当路径看起来像是获胜者时，才会进行二次检查）来实现这一点。

核心结论

作者不仅仅是做了一个稍微快一点的计算器；他们构建了一个全新的导航引擎。他们证明了通过使用椭圆形状的搜索区域和手电筒式的可见性检查，你可以为机器人找到绝对最短、最直的路径，无论世界是静止的还是充满移动障碍物的，并且能做得非常快。

对于静态世界： 它是一个可靠、快速且灵活的工具。
对于动态世界： 它解决了一个此前进展缓慢的问题，使得移动机器人（如无人机集群）的最优导航突然变得切实可行。

技术摘要：静态与动态环境下的最优任意角度路径规划

1. 问题定义

本文探讨了网格中最优任意角度路径规划（Optimal Any-Angle Path Planning）的挑战，即智能体需要在连续空间中寻找两点之间的最短（或时间最优）路径，同时避开静态和动态障碍物。与传统的基于图的规划器（如 A*）不同，后者将移动限制在预定义的边上（例如网格中的 45 度增量），而任意角度规划允许在任意两点对之间进行移动，从而实现更直、更短的路径。

核心难点在于平衡最优性（Optimality）与计算效率（Computational Efficiency），特别是在障碍物根据已知轨迹运动的动态环境中。虽然像 Theta* 这样的算法提供了高效性，但它们无法保证真正的最短路径。相反，像 Anya（针对静态环境）和 TO-AA-SIPP（针对动态环境）这样的最优算法虽然能保证最优性，但由于复杂的搜索节点结构或详尽的可见性检查，往往面临扩展性问题或高昂的计算成本。

2. 方法论

作者提出了两种旨在保持最优性的同时加速计算的通用技术，并将其集成到新的算法中：Zeta（用于静态环境）和 Zeta-SIPP（用于动态环境）。

A. 核心技术

椭圆前向扩张（Elliptical Forward Expansion）：
- 用基于椭圆几何属性的全局搜索策略取代传统的局部邻域扩张（例如 2k-邻域）。
- 起点和终点作为椭圆的两个焦点。长轴长度 $L$ 由 open list 中的最小 $f$ 值定义（ $L \ge \min_{n \in open} f(n)$ ）。
- 这创建了一个节点扩张的上界：位于椭圆之外的节点其代价高于当前最优路径，因此可以被暂时排除，从而确保仅扩展那些可能对最优路径有贡献的节点。
- 这种方法通过维持 A*-类算法所需的单调性，保证了搜索的最优性。
通过阴影投射实现的视野（Field of View, FoV via Shadowcasting）：
- 用对称的阴影投射算法（具体为基于八分量或四分量的算法）取代传统的视线（Line-of-Sight, LoS）检查。
- 该算法不再重复检查单个点到邻居的可见性，而是将一个节点视为“光源”，通过从障碍物投射阴影来一次性确定整个区域的可见性。
- 这显著减少了冗余的可见性检查，尤其是在大型邻域或开阔区域中。

B. 集成策略：反向扫描与前向扫描

为了将 FoV 与椭圆扩张集成，论文引入了两种扫描模式：

反向扫描（Inverted Scanning）： 将新加入的 open 节点视为光源。通过执行阴影投射来寻找椭圆边界内的可见节点。这需要一个缓冲区来处理椭圆边界附近的网格失真（Aliasing）问题。
前向扫描（Forward Scanning）： 将 closed 节点视为光源。随着椭圆搜索范围的扩大，从 closed 节点出发的视野会增量更新，以包含新的 open 节点。这允许利用已知路径信息（如父节点朝向）对扫描范围进行更积极的剪枝，并避免重复扫描已经连接的节点。

C. 算法实现

Zeta（静态环境）：*
- 针对静态网格进行了优化，将搜索空间限制在紧致路径（Taut Paths，即仅在障碍物拐角处转弯的路径）上，类似于 Anya。
- 使用基于点的搜索节点（不同于 Anya 的三角形区域），使其更具可扩展性。
- Zeta-i*：使用反向扫描。
- Zeta-f*：使用带有代价边界剪枝的前向扫描。
Zeta-SIPP（动态环境）：*
- 通过**安全间隔路径规划（Safe Interval Path Planning, SIPP）*将 Zeta 扩展到处理动态障碍物。
- 搜索节点由位置和安全时间间隔定义。
- 集成了反向扩张（源自 TO-AA-SIPP），以延迟昂贵的基于安全间隔的冲突检测与解决（SI-CDR），直到必要时才进行。
- Zeta-SIPP-i* 和 Zeta-SIPP-f* 分别应用了上述两种扫描方法到 SIPP 框架中。

3. 主要贡献

通用技术： 引入了椭圆前向扩张和视野扫描作为最优任意角度路径规划的通用机制，实现了可见性检查与节点扩张的解耦。
新算法： 开发了 Zeta* 和 Zeta-SIPP*，为静态和动态环境下的最优路径规划提供了一个统一的方法。
可扩展性与可扩展性： 不同于依赖复杂三角形搜索节点（这阻碍了向 3D 或动态环境扩展）的 Anya，Zeta* 保留了标准的基于点的节点，便于扩展到加权地形和动态障碍物。
性能提升： 证明了前向扫描结合椭圆扩张可以达到与最先进静态规划器（Anya）相当的性能，同时在动态环境下显著优于 TO-AA-SIPP。

4. 实验结果

作者在包括游戏地图、城市地图和动态场景在内的标准基准测试（Moving AI Lab）上评估了这些算法。

静态环境：
- Zeta-f* 的性能与 Anya（最先进的最优静态规划器）相当，且平均比 Theta* 快约 10 倍。
- Zeta-i* 比 Zeta*-f 慢，因为其扫描范围剪枝效果较差，扫描了更多的顶点。
- 与使用大邻域的非最优 A* 相比，Zeta* 变体在保持最优性的同时，使用了更少的排序元素和扫描顶点。
动态环境：
- Zeta-SIPP-f* 比之前的最优规划器 TO-AA-SIPP 快了 20 倍以上（具体约为 24 倍）。
- Zeta-SIPP-i* 也明显快于 TO-AA-SIPP（约 21 倍）。
- 虽然使用 FoV 的 TO-AA-SIPP 变体（TO-AA-FoV-SIPP）在狭窄地图（如 Room, Maze）中表现良好，但在开阔且复杂的地图中，Zeta*-SIPP-f 通常优于它，这归功于椭圆扩张在缩小搜索空间方面的效率。
- 非最优规划器（如 AA-SIPP）仍然比最优规划器快，但生成的路径稍长；然而，当严格要求最优性时，Zeta*-SIPP 提供了一个可行的选择。

5. 重要性与主张

论文声称确定了实现最优任意角度路径规划的关键要求，并引入了一个适用于不同环境的统一方法。

最优性 vs. 效率： 研究表明，可以在不产生以往最优规划器那般高昂计算成本的情况下，在动态环境中实现真正的最短路径。
统一框架： 通过将可见性检查（通过 FoV）与节点扩张（通过椭圆边界）分离，所提出的框架提供了一个灵活的基础，可以扩展到非均匀代价地图和 3D 场景，而不像以往的方法那样与特定的网格结构或静态假设紧密耦合。
实际影响： 作者将 Zeta*-SIPP 定位为那些即使是微小的路径质量提升也能带来显著能量节省的应用场景中的推荐选项，并作为最优任意角度多智能体路径规划（MAPF）的潜在底层规划器。

作者对自己的主张保持谦逊，指出虽然 Zeta* 在静态环境中略慢于 Anya，但其主要价值在于其可扩展性，能够应对 Anya 难以处理的动态和复杂环境。本文并不声称解决了所有的路径规划问题，而是为使最优任意角度规划在动态场景下变得计算可行迈出了重要一步。