# Optimal any-angle path planning in static and dynamic environments

arXiv: https://arxiv.org/abs/2607.00065 · HTML: https://mlsanity.com/paper/2607.00065/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 39 references that are in the map.
- First posted on arXiv 30 Jun 2026.

## Builds on (most cited first, 8 of 8)

- [Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks](https://mlsanity.com/paper/1906.08291/) (2019)
- [Informed RRT*: Optimal Sampling-based Path Planning Focused via Direct Sampling of an Admissible Ellipsoidal Heuristic](https://mlsanity.com/paper/1404.2334/) (2014)
- [Batch Informed Trees (BIT*): Sampling-based Optimal Planning via the Heuristically Guided Search of Implicit Random Geometric Graphs](https://mlsanity.com/paper/1405.5848/) (2014)
- [Theta*: Any-Angle Path Planning on Grids](https://mlsanity.com/paper/1401.3843/) (2014)
- [Batch Informed Trees (BIT*): Informed Asymptotically Optimal Anytime Search](https://mlsanity.com/paper/1707.01888/) (2017)
- [Any-Angle Pathfinding for Multiple Agents Based on SIPP Algorithm](https://mlsanity.com/paper/1703.04159/) (2017)
- [Towards Time-Optimal Any-Angle Path Planning With Dynamic Obstacles](https://mlsanity.com/paper/2104.06681/) (2021)
- [Optimal and Bounded Suboptimal Any-Angle Multi-agent Pathfinding](https://mlsanity.com/paper/2404.16379/) (2024)

## Abstract (arXiv)

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.