When an autonomous agent navigates a grid-based map, traditional pathfinding algorithms like A* restrict its movement to the edges of the grid graph. Even with an 8-neighborhood expansion (allowing cardinal and diagonal moves), the resulting trajectories are inherently constrained to headings that are multiples of 45 degrees. This constraint forces agents into unnatural, jagged "zig-zag" patterns that accumulate unnecessary distance overhead and require frequent, abrupt heading changes.
To find shorter, smoother paths, we could construct a full visibility graph of the environment, but doing so is computationally expensive. Any-angle pathfinding bridges this gap. It maintains the simple, efficient data structures of grid-based search while dynamically breaking the grid-edge constraint to find paths that approach or match the true shortest path in continuous space.
The Core Mechanism: Line-of-Sight Propagation
The foundational insight of any-angle pathfinding, introduced by Alex Nash et al. in their seminal work on Theta*, modifies how a node's parent is assigned during vertex expansion.
In standard A*, when expanding a node $s$ to its neighbor $s'$, the algorithm assumes the path must travel along the edge from $s$ to $s'$. The parent of $s'$ becomes $s$.
Theta introduces a simple line-of-sight (LOS) check. When evaluating a neighbor $s'$, the algorithm checks whether an unobstructed straight line exists between the parent* of $s$ (the grandparent of $s'$) and $s'$. If a clear line of sight exists, $s'$ bypasses $s$ entirely and links directly to $\text{parent}(s)$.
Standard A* Expansion:
[Parent of s] --------> [s] --------> [s']
(Path is forced through s)
Theta* Expansion (with Line of Sight):
[Parent of s] ----------------------> [s']
\ /
\---------> [s] ------------/
(Node s is bypassed)
As Alex Nash et al. demonstrate, this simple modification allows trajectories to traverse grid cells at arbitrary angles. By leveraging the triangle inequality dynamically during the search, the algorithm identifies direct shortcuts that eliminate discretization artifacts. Alex Nash notes that this approach typically yields paths within 1% of the absolute shortest continuous distance while remaining nearly as fast as standard grid-based search.
Why Vertex Placement Matters
The quality of an any-angle path is deeply tied to how the underlying grid graph is constructed. In a comparative study, James Bailey et al. analyzed the effect of vertex placement on path length.
Traditionally, grid nodes are placed at the centers of grid cells. However, James Bailey et al. proved that placing vertices at cell corners rather than cell centers yields a profound mathematical advantage: when combined with any-angle line-of-sight checks, corner-based vertex placement produces paths that are mathematically identical in length to the truly shortest path in continuous space. This occurs because the shortest continuous paths in polygonal environments naturally turn at obstacle corners, making cell corners the optimal topological choice for graph vertices.
Optimizing the Search: Lazy Evaluation and Replanning
While any-angle pathfinding produces superior paths, performing a line-of-sight check for every expanded neighbor introduces a computational bottleneck. Ray-tracing through a grid is significantly more expensive than calculating a simple Euclidean distance between adjacent cells.
To mitigate this, Alex Nash et al. developed Lazy Theta*. The intuition behind Lazy Theta is to defer the expensive line-of-sight check until it is absolutely certain to be useful. Instead of verifying line-of-sight during* neighbor expansion, the algorithm optimistically assumes a line-of-sight exists and sets the parent accordingly. The actual line-of-sight check is delayed until a node is popped from the priority queue (the open list) for expansion. If the check fails, the algorithm falls back to the standard grid-edge parent. This lazy evaluation strategy reduces the number of visibility checks by up to an order of magnitude without sacrificing path quality.
For real-world robotic systems, environments are rarely static. Alex Nash extended this paradigm to dynamic environments with Incremental Phi*. By combining the smooth, arbitrary-angle trajectories of Theta with the rapid re-planning principles of incremental search algorithms (like Lifelong Planning A), Incremental Phi* allows an agent to efficiently update its near-optimal path as new obstacles are sensed, bypassing the need to recompute the entire path from scratch.
Scaling to Multiple Agents and Continuous Space
The benefits of any-angle pathfinding become even more pronounced when scaling from single-agent navigation to multi-agent coordination and continuous trajectory optimization.
Multi-Agent Coordination
In multi-agent pathfinding (MAPF), grid constraints compound the difficulty of avoiding collisions. When agents are forced to move only cardinally or diagonally, they must execute complex, coordinated "dances" to avoid each other in tight spaces.
By integrating any-angle movement into multi-agent frameworks, researchers unlocked massive efficiency gains. Konstantin S. Yakovlev et al. introduced AA-SIPP(m), which combines prioritized planning with Safe Interval Path Planning (SIPP) and any-angle movement. This integration reduces total trajectory costs by 13% to 21% compared to traditional grid-constrained multi-agent movement.
More recently, Konstantin Yakovlev et al. developed AA-CCBS, providing the first mathematically optimal and bounded suboptimal any-angle multi-agent pathfinding algorithm. As the authors note in their IROS 2024 paper, the efficiency gains of any-angle movement are highly dependent on the environment's topology. In open spaces, the ability to move at arbitrary angles allows agents to resolve temporal conflicts along direct, straight-line trajectories, whereas tightly constrained layouts like warehouses show less dramatic improvements.
The Bridge to Continuous Space
Ultimately, any-angle pathfinding serves as a stepping stone toward fully continuous space navigation. Planners that operate entirely within continuous solution spaces—such as the decentralized navigation protocol proposed by Stepan Dergachev et al., the spatio-temporal semantic corridors designed by Wenchao Ding et al., or the projected diffusion models introduced by Jinhao Liang et al.—demonstrate that avoiding fixed-resolution grids entirely yields the shortest, most energy-efficient paths for physical systems.
However, by embedding continuous line-of-sight checks directly into discrete graph searches, any-angle pathfinding algorithms provide a powerful, computationally lightweight alternative that captures the best of both worlds: the speed and predictability of grid searches, and the smooth, natural efficiency of continuous trajectories.
Key Foundational Work
Theta*: Any-Angle Path Planning on Grids (2007) — contributed 2 concept elements to this direction.
Mobile robotic surveying performance for planetary surface site characterization (2008) — contributed 1 concept elements to this direction.