💻 computer science

Optimal any-angle path planning in static and dynamic environments

This paper introduces Zeta* and Zeta*-SIPP, novel algorithms for optimal any-angle path planning in static and dynamic environments that leverage elliptical forward expansion and field-of-view techniques to achieve significant speed improvements while preserving solution optimality.

Original authors: Yiyuan Zou, Clark Borst

Published 2026-07-02

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yiyuan Zou, Clark Borst

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to guide a drone from a starting point to a finish line in a large, open warehouse filled with pillars (obstacles). Your goal is to get there as quickly as possible.

The Old Way (The "Grid" Problem)
Traditional navigation software, like the classic A* algorithm, treats the world like a giant chessboard. It can only move the drone from the center of one square to the center of an adjacent square. This forces the drone to take a "stair-step" path, constantly turning 45 degrees. It's like trying to drive a car down a street but only being allowed to turn at every single intersection, even if you could drive straight across a field. The result? The path is safe, but it's longer and bumpier than it needs to be.

The "Any-Angle" Dream
Scientists wanted a way to let the drone fly in straight lines, cutting corners like a bird. This is called Any-Angle Path Planning.

Theta* was an early attempt. It was like a human looking around and saying, "Hey, I can see the next pillar from here, so I'll just fly straight to it." It made paths straighter, but it wasn't guaranteed to find the absolute shortest route.
Anya was the next big leap. It was incredibly smart and fast at finding the true shortest path, but it was like a specialized race car: it worked perfectly on flat, static tracks (static environments) but was very hard to modify for bumpy, changing tracks (dynamic environments where obstacles move).

The New Solution: Zeta* and Zeta*-SIPP
This paper introduces a new family of algorithms called Zeta* (for static worlds) and Zeta*-SIPP (for dynamic worlds with moving obstacles). The authors created two "superpowers" to make these algorithms both fast and perfect.

Superpower 1: The "Elliptical Search" (The Oval Race Track)

Imagine you are looking for a lost key in a huge field. A traditional search might check every single blade of grass in a circle around you.
The authors realized that if you know where you started and where you want to go, you don't need to check the grass far away to the left or right. You only need to check the area inside an oval (ellipse) drawn between the start and the finish.

How it works: The algorithm draws an invisible oval. Any point outside this oval is mathematically guaranteed to be a longer, worse path. So, the algorithm ignores everything outside the oval.
The Benefit: It drastically cuts down the number of places the computer needs to look, saving huge amounts of time while still guaranteeing the shortest path.

Superpower 2: The "Flashlight" (Field of View)

When a drone flies, it needs to know if the path ahead is blocked.

The Old Way (Line of Sight): Imagine checking a path by shining a laser pointer at every single square one by one. If you have to check 100 squares, you fire 100 lasers. It's slow.
The New Way (Shadowcasting): Imagine turning on a powerful flashlight. Instead of checking one square at a time, the light floods the whole area at once. If a pillar blocks the light, it casts a "shadow" behind it. The algorithm instantly knows that everything in that shadow is blocked without checking each square individually.
The Benefit: This "flashlight" method checks visibility much faster than the old "laser pointer" method.

Putting It Together: Two Scanners

To make these superpowers work together, the authors invented two ways to scan the map:

Inverted Scanning: You stand on a new spot you just found and shine your flashlight outward to see what you can reach.
Forward Scanning: You stand on a spot you've already visited and shine your flashlight forward to see what new spots you can now reach.

The Results: Zeta* vs. Zeta*-SIPP

Zeta* (Static Worlds): This is the version for maps where nothing moves (like a warehouse with fixed pillars). It uses the "Flashlight" and "Oval" tricks to find the perfect path. It is almost as fast as the current champion (Anya) but is built like a "Lego set" rather than a "custom race car," meaning it's much easier to modify for other uses.
Zeta*-SIPP (Dynamic Worlds): This is the version for maps where obstacles move (like drones flying around each other). This is the hardest problem because the path might get blocked while you are flying.
- The paper claims that Zeta*-SIPP is more than 20 times faster than the previous best method (TO-AA-SIPP) for finding the perfect path in these moving environments.
- It achieves this by combining the "Oval" search (to ignore bad paths) with the "Flashlight" (to check for moving blocks quickly) and a "lazy" checking method (it only double-checks a path if it looks like it might be the winner).

The Bottom Line

The authors didn't just make a slightly faster calculator; they built a new engine for navigation. They proved that by using an oval-shaped search area and a flashlight-style visibility check, you can find the absolute shortest, straightest path for a robot, whether the world is still or full of moving obstacles, and do it incredibly fast.

For Static Worlds: It's a reliable, fast, and flexible tool.
For Dynamic Worlds: It solves a problem that was previously very slow, making optimal navigation for moving robots (like fleets of drones) suddenly practical.

Technical Summary: Optimal Any-Angle Path Planning in Static and Dynamic Environments

1. Problem Definition

The paper addresses the challenge of optimal any-angle path planning on grids, a problem where an agent must find the shortest (or time-optimal) path between two points in a continuous space while avoiding static and dynamic obstacles. Unlike traditional graph-based planners like A*, which restrict movement to predefined edges (e.g., 45-degree increments on a grid), any-angle planning allows movement between any pair of vertices, enabling straighter and shorter paths.

The core difficulty lies in balancing optimality with computational efficiency, particularly in dynamic environments where obstacles move according to known trajectories. While algorithms like Theta* offer efficiency, they do not guarantee true shortest paths. Conversely, optimal algorithms like Anya (for static environments) and TO-AA-SIPP (for dynamic environments) guarantee optimality but often suffer from scalability issues or high computational costs due to complex search node structures or exhaustive visibility checks.

2. Methodology

The authors propose two general techniques to accelerate computation while preserving optimality, which are integrated into new algorithms: Zeta* (for static environments) and Zeta-SIPP* (for dynamic environments).

A. Core Techniques

Elliptical Forward Expansion:
- Replaces traditional local neighborhood expansions (e.g., 2k-neighborhoods) with a global search strategy based on the geometric properties of ellipses.
- The start and target points serve as the foci of an ellipse. The major axis length $L$ is defined by the minimum $f$ -value in the open list ( $L \ge \min_{n \in open} f(n)$ ).
- This creates an upper bound for node expansion: nodes outside the ellipse have costs higher than the current best path and can be temporarily excluded, ensuring that only nodes potentially contributing to the optimal path are expanded.
- This approach guarantees that the search remains optimal by maintaining the monotonicity required for A*-like algorithms.
Field of View (FoV) via Shadowcasting:
- Replaces traditional line-of-sight (LoS) checks with a symmetric shadowcasting algorithm (specifically octant-based or quadrant-based).
- Instead of checking visibility from a single point to neighbors repeatedly, the algorithm treats a node as a "light source" and casts shadows from obstacles to determine visibility for a whole region in a single pass.
- This significantly reduces redundant visibility checks, especially in large neighborhoods or open areas.

B. Integration Strategies: Inverted vs. Forward Scanning

To integrate FoV with elliptical expansion, the paper introduces two scanning modes:

Inverted Scanning: Treats newly added open nodes as light sources. It performs shadowcasting to find visible nodes within the elliptical boundary. This requires a buffer to handle grid aliasing near the ellipse boundary.
Forward Scanning: Treats closed nodes as light sources. As the elliptical search range expands, the field of view from closed nodes is incrementally updated to include new open nodes. This allows for more aggressive pruning of the scan range using known path information (e.g., parent headings) and avoids repeated scanning of already connected nodes.

C. Algorithmic Implementations

Zeta (Static Environments):*
- Optimized for static grids by restricting the search space to taut paths (paths that only turn at obstacle corners), similar to Anya.
- Uses point-based search nodes (unlike Anya's triangular regions), making it more extensible.
- Zeta-i:* Uses inverted scanning.
- Zeta-f:* Uses forward scanning with cost-bounded pruning.
Zeta-SIPP (Dynamic Environments):*
- Extends Zeta* to handle dynamic obstacles using Safe Interval Path Planning (SIPP).
- Search nodes are defined by location and safe time intervals.
- Integrates Inverted Expansion (from TO-AA-SIPP) to delay expensive Safe-Interval-based Conflict Detection and Resolution (SI-CDR) until necessary.
- Zeta-SIPP-i* and Zeta-SIPP-f* apply the respective scanning methods to the SIPP framework.

3. Key Contributions

General Techniques: The introduction of elliptical forward expansion and field-of-view scanning as general mechanisms for optimal any-angle planning, decoupling visibility checking from node expansion.
New Algorithms: The development of Zeta* and Zeta-SIPP*, which provide a unified approach for optimal path planning in both static and dynamic environments.
Scalability and Extensibility: Unlike Anya, which relies on complex triangular search nodes that hinder extension to 3D or dynamic settings, Zeta* retains standard point-based nodes, facilitating easier adaptation to weighted terrains and dynamic obstacles.
Performance Improvements: The demonstration that forward scanning combined with elliptical expansion can achieve performance comparable to state-of-the-art static planners (Anya) while significantly outperforming dynamic planners (TO-AA-SIPP).

4. Experimental Results

The authors evaluated the algorithms on standard benchmarks (Moving AI Lab) including game maps, city maps, and dynamic scenarios.

Static Environments:
- Zeta-f* achieves performance comparable to Anya (the state-of-the-art optimal static planner) and is approximately 10 times faster than Theta* on average.
- Zeta-i* is slower than Zeta*-f due to less effective scan range pruning, scanning substantially more vertices.
- Zeta* variants maintain optimality while using fewer sorted elements and scanned vertices compared to suboptimal planners like A* with large neighborhoods.
Dynamic Environments:
- Zeta-SIPP-f* is more than 20 times faster (specifically ~24x) than the previous state-of-the-art optimal planner, TO-AA-SIPP.
- Zeta-SIPP-i* is also significantly faster (~21x) than TO-AA-SIPP.
- While TO-AA-FoV-SIPP (a variant of TO-AA-SIPP using FoV) performs well in narrow maps (Room, Maze), Zeta*-SIPP-f generally outperforms it in open and complex maps due to the efficiency of elliptical expansion in reducing the search space.
- Suboptimal planners (e.g., AA-SIPP) remain faster than optimal ones but produce slightly longer paths; however, Zeta*-SIPP offers a viable option when optimality is strictly required.

5. Significance and Claims

The paper claims to identify the key requirements for achieving optimal any-angle path planning and introduces a unified approach suitable for different environments.

Optimality vs. Efficiency: The research demonstrates that it is possible to achieve true shortest paths in dynamic environments without the prohibitive computational cost associated with previous optimal planners.
Unified Framework: By separating visibility checking (via FoV) from node expansion (via elliptical bounds), the proposed framework offers a flexible foundation that can be extended to non-uniform costmaps and 3D scenarios, unlike previous methods that were tightly coupled to specific grid structures or static assumptions.
Practical Impact: The authors position Zeta*-SIPP as a recommended option for applications where even small improvements in path quality yield substantial energy savings, and as a potential low-level planner for optimal any-angle Multi-Agent Path Finding (MAPF).

The authors remain modest regarding their claims, noting that while Zeta* is slightly slower than Anya in static environments, its primary value lies in its extensibility to dynamic and complex settings where Anya struggles. The paper does not claim to solve all path planning problems but rather provides a significant step forward in making optimal any-angle planning computationally feasible for dynamic scenarios.