Any-Angle Pathfinding for Smooth Trajectories in Continuous Space

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 238 papers63 conceptsfrozen 2026-10-04

Traditional pathfinding algorithms like A* are often tethered to the geometry of a grid. While grids provide a convenient way to discretize a map, they force agents into "jagged" trajectories—unnatural zig-zags restricted to 45 or 90-degree turns. In the real world, robots, drones, and ships move in continuous space. Forcing them to follow grid edges results in longer paths, increased energy consumption, and unnecessary mechanical wear.

The core shift in this research direction is the move toward any-angle pathfinding, which allows agents to move in straight lines between any two points in an environment, provided there is a clear line of sight.

The Intuition of the Shortcut

The fundamental insight behind any-angle pathfinding is a simple application of the triangle inequality: the straight line between two points is always shorter than a path that passes through an intermediate vertex.

In a standard grid search, when an algorithm expands a node, it only looks at its immediate neighbors. Michael Wybrow, Kim Marriott, and Peter J. Stuckey demonstrate in Orthogonal Connector Routing (GD 2009) that even when restricted to orthogonal paths, "nudging" and visibility checks can significantly simplify visual complexity.

Any-angle algorithms like Theta take this further. During the search process, instead of only considering a node's parent, the algorithm checks if there is a clear line-of-sight to its grandparent*. If a clear path exists, the algorithm "short-circuits" the intermediate node, effectively allowing the path to take any angle across the grid cells. As Alex Nash, Sven Koenig, and Craig A. Tovey explain in Lazy Theta*: Any-Angle Path Planning and Path Length Analysis in 3D, this representational strategy identifies shortcuts that eliminate discretization artifacts entirely.

From Grids to Continuous Geometry

While Theta improves grid-based search, other researchers argue for abandoning the grid entirely. Xing Liu suggests in Path Plan of Unmanned Underwater Vehicle Using Particle Swarm Optimization that moving to a continuous search space allows for the discovery of optimal coordinates that lie between* grid nodes, avoiding the optimality gap inherent in fixed resolutions.

This "grid-less" philosophy is echoed by Yuchen Wu and colleagues in Multi-robot Task Allocation and Path Planning with Maximum Range Constraints. Their RangeTAP framework treats obstacles as continuous geometric polygons rather than collections of cells. By recursively identifying obstacle vertices as guidance points, they bypass the "curse of dimensionality" that plagues high-resolution grids, allowing pathfinding to scale to massive environments without a loss in precision.

Solving the Multi-Agent Coordination Problem

The benefits of any-angle movement are most pronounced when multiple agents must share the same space. In traditional Multi-Agent Path Finding (MAPF), agents often collide because the grid forces them into the same narrow "corridors."

Konstantin S. Yakovlev and Anton Andreychuk show in Any-Angle Pathfinding for Multiple Agents Based on SIPP Algorithm that allowing any-angle movement reduces total trajectory costs by up to 21%. By eliminating jagged movements, agents create fewer "artificial" conflicts. This is further supported by Stepan Dergachev and Konstantin Yakovlev in Decentralized Unlabeled Multi-agent Navigation in Continuous Space, where they demonstrate that continuous-space planning allows for diagonal and curved trajectories that are physically impossible in discrete models, leading to significantly shorter flowtimes.

Balancing Smoothness and Physical Constraints

A path isn't just a line; for a physical robot, it must be executable. Standard any-angle paths can still have sharp corners where line-of-sight is broken by an obstacle.

To address this, Konstantin Yakovlev and Egor Baskin introduced LIAN in Grid-based angle-constrained path planning. LIAN expands the search frontier by identifying successors at a fixed radial distance, ensuring that every turn stays within a specific angular threshold. This makes the resulting paths ideal for UAVs or ships with limited turning radii.

Similarly, Jiaoyang Li and Chuchu Fan emphasize in Scalable and Safe Multi-Agent Motion Planning with Nonlinear Dynamics and Bounded Disturbances that planning with continuous-space safety buffers yields solutions that are not only shorter but safer, as they account for the fact that robots cannot "turn on a dime."

Computational Efficiency through Laziness

The primary challenge of any-angle planning is the computational cost of frequent line-of-sight (LoS) checks. Checking visibility between many pairs of nodes is much slower than simply checking if a neighboring cell is empty.

The research community has solved this through "lazy" evaluation. Lazy Theta* delays expensive LoS checks until they are absolutely necessary for the search to progress. More recently, Keisuke Okumura proposed LaCAS* in Pathfinding with Lazy Successor Generation, which uses k-d trees to incrementally generate successors only as needed. This allows the algorithm to find initial solutions rapidly and refine them into optimal, smooth paths over time, effectively bridging the gap between the speed of grid search and the quality of continuous-space planning.

Papers in this version

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 22 papers
  2. Version 1 · 2026-10-04 · 38 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_any_angle_pathfinding_2d3531fd,
  title = {any-angle pathfinding},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/any-angle-pathfinding/rdr_2d3531fd4bc148ff97c298b3ae373031},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_any_angle_pathfinding_for_smooth_traject_2d3531fd_v1,
  title = {Any-Angle Pathfinding for Smooth Trajectories in Continuous Space},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/any-angle-pathfinding-for-smooth-trajectories-in-continuous-space/rdr_2d3531fd4bc148ff97c298b3ae373031/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}