When we map a continuous physical environment into a discrete grid for pathfinding, we make a fundamental trade-off: we exchange infinite geometric complexity for a structured graph that classical search algorithms like A can quickly solve. However, this discretization introduces an artificial constraint. By forcing an agent to move exclusively along graph edges—such as 4-way cardinal or 8-way cardinal/ordinal directions—we introduce a systematic error known as path inflation or metrication error*.
Even in a completely wide-open space, an 8-connected grid forces an agent to zig-zag if its destination does not lie precisely on a 45-degree increment. As Alex Nash et al. point out, this structural constraint artificially inflates path lengths by roughly 8% in 2D environments and up to 13% in 3D voxel grids (as analyzed by Alex Nash et al.). For physical systems like autonomous ships (Yong Ma et al.) or quadrotors (Wenchao Ding), these jagged, staircase-like trajectories are more than just mathematically suboptimal; they introduce severe motion jitters, violate vehicle dynamics, and waste significant energy.
The Illusion of Post-Processing
A common intuition is that path inflation can be easily fixed by a two-step pipeline: first, find a path using standard grid-based A*, and second, apply a smoothing filter (such as a Bézier curve or a "string-pulling" routine) to clean up the jagged edges.
However, this approach suffers from a fundamental flaw. As Alex Nash et al. demonstrated, the initial grid-constrained search can easily commit to the wrong topological neighborhood (or homotopy class). Because standard A* evaluates costs strictly along grid edges, it may perceive a route around the left side of an obstacle as shorter than a route around the right side, even though the true continuous straight-line shortcut lies to the right.
Grid-Constrained Search (Suboptimal Homotopy Class)
[Start] ----> [Grid Path] ----> (Obstacle) ----> [Goal]
|
v (Post-smoothing can only tweak this flawed route)
True Any-Angle Path (Optimal Homotopy Class)
[Start] =======================================> [Goal]
Once the initial search selects a suboptimal topological corridor, local post-processing smoothing algorithms cannot escape it; they can only optimize the path within that flawed corridor. As noted by the authors of Global Tensor Motion Planning, even advanced spline-based smoothing remains fundamentally bottlenecked by the topology of the underlying discrete graph structure.
The Core Mechanism: Line-of-Sight Propagation
Any-angle path planning algorithms solve this problem by breaking the grid-edge constraint during the search process, rather than after it. The foundational algorithm for this approach is Theta*, developed by Alex Nash et al..
To understand why Theta works, consider how standard A updates path information. When expanding a node $s$, A* examines a neighboring node $s'$ and considers a path from the start node to $s$, and then along the grid edge from $s$ to $s'$. The parent of $s'$ is strictly set to $s$.
Theta introduces a simple yet powerful modification. When evaluating a neighbor $s'$, it does not just look at the edge $(s, s')$. Instead, it checks if there is a clear line-of-sight between the parent* of $s$ (denoted as $p(s)$) and $s'$.
- If there is a line-of-sight: $s'$ bypasses $s$ entirely. It sets its parent directly to $p(s)$, and its path cost becomes the true Euclidean distance from the start to $p(s)$ plus the straight-line distance from $p(s)$ to $s'$.
- If the line-of-sight is blocked: The algorithm falls back to the standard A* rule, setting the parent of $s'$ to $s$.
Standard A* Propagation:
[Parent p(s)] ----> [Current Node s] ----> [Neighbor s']
Path: Jagged grid edges
Theta* Propagation (Clear Line-of-Sight):
[Parent p(s)] ===========================> [Neighbor s']
(Bypasses Node s)
Path: True Euclidean straight line
By propagating parent pointers across arbitrary distances rather than restricting them to immediate neighbors, Theta dynamically constructs a visibility graph on the fly. This allows the search to discover global shortcuts across open spaces while maintaining a runtime comparable to standard grid search. To scale this to 3D environments where line-of-sight checks are computationally expensive, Lazy Theta** (Alex Nash et al.) defers these visibility checks using lazy evaluation, performing them only when a node is about to be expanded.
Alternative Geometries and Continuous Optimization
While any-angle grid planners modify parentage on a standard grid, other paradigms eliminate grid-based path inflation by altering the underlying representation or optimization space entirely.
Mesh-Based and Edge-Based Search
Instead of regular square grids, environments can be discretized using geometric features. Douglas Demyen et al. introduced the TRA algorithm, which utilizes Constrained Delaunay Triangulations. By abstracting space into triangles, the planner focuses purely on core decision points (e.g., which side of an obstacle to pass), allowing agents to traverse open space along continuous, near-optimal vectors. Similarly, Zhuo Yao et al. developed RimJump*, which focuses search attention exclusively on obstacle edges and inflection points rather than point-by-point grid cells, calculating mathematically exact shortest paths based on obstacle complexity rather than map scale.
Continuous Space Optimization
Other approaches bypass graph structures altogether. Xing Liu leverages Particle Swarm Optimization (PSO) within a continuous search space to generate smooth, dynamically feasible trajectories for Unmanned Underwater Vehicles (UUVs). For information-gathering tasks, Gaurav S. Sukhatme et al. designed sampling-based algorithms that operate directly in continuous space, ensuring that robots maximize data collection without being artificially constrained by grid boundaries or ignoring vehicle dynamics.
Scaling to Multi-Agent Systems
The suboptimality of discrete grids compounds dramatically when coordinating multiple robots. In Multi-Agent Pathfinding (MAPF), restricting agents to cardinal grid movements forces them into unnatural bottlenecks, creating artificial congestion and increasing collision risks (Stepan Dergachev et al.).
To resolve this, researchers extended any-angle principles to multi-agent coordination. Algorithms like AA-SIPP(m), proposed by Konstantin S. Yakovlev et al., combine prioritized planning with any-angle path generation, reducing overall trajectory costs by up to 20% in dense environments. To achieve absolute mathematical optimality, Konstantin S. Yakovlev et al. introduced AA-CCBS, the first multi-agent planner capable of finding provably optimal, collision-free trajectories in continuous space. By breaking free from rigid grid lines, these frameworks allow agents to utilize the full physical capacity of an environment, enabling parallel movements and smooth, direct navigation.
Key Foundational Work
Efficient Triangulation-Based Pathfinding (2006) — contributed 1 concept elements to this direction.
Worldwide Aeronautical Route Planner (1999) — contributed 1 concept elements to this direction.