Any-angle path planning algorithms are a subset of pathfinding algorithms that search for a path between two points in space and allow the turns in the path to have any angle. The result is a path that goes directly toward the goal and has relatively few turns. Other pathfinding algorithms such as A* constrain the paths to a grid, which produces jagged, indirect paths.
Background
Real-world and many game maps have open areas that are most efficiently traversed in a direct way. Traditional algorithms are ill-equipped to solve these problems:
A* with a 8-connected discrete grid graph is very fast, but only looks at paths in 45-degree increments. A quick post-smoothing step can be used to straighten the jagged output, but the result is not guaranteed to be optimal as it does not look at all the possible paths. The advantage is that all optimizations of grid A* like jump point search will apply.
A visibility graph with all the grid points can be search with A* for the optimal solution. However, the performance is problematic since the number of edges in a graph with vertices is.
An any-angle path planning algorithm aims to produce optimal or near-optimal solutions while taking less time than the basic visibility graph approach. Fast any-angle algorithms take roughly the same time as a grid-based solution to compute.
Definitions
; Taut path: A path where every heading change in the path “wraps” tightly around some obstacle. For a uniform grid, only taut paths can be optimal. ; Single-source: A path-finding problem that seeks to find the shortest path to all parts from the graph, starting from one vertex.
Algorithms
A*-based
So far, five main any-angle path planning algorithms that are based on the heuristic search algorithm A* have been developed, all of which propagate information along grid edges:
Field D* and 3D Field D* - Dynamic pathfinding algorithms based on D* that use interpolation during each vertex expansion and find near-optimal paths through regular, nonuniform cost grids. Field D* therefore tries to solve the weighted region problem and 3D Field D* the corresponding three-dimensional problem.
* Multi-resolution Field D* – Extension of Field D* for multi-resolution grids.
Theta* - Uses the same main loop as A*, but for each expansion of a vertex, there is a line-of-sight check between and the successor of,. If there is line-of-sight, the path from to is used since it will always be at least as short as the path from to and to. This algorithm works only on uniform-cost grids. AP Theta* is an optimization of Theta* that uses angle-propagation to decrease the cost of performing line-of-sight calculations to, and Lazy Theta* is another optimization of Theta* that uses lazy evaluation to reduce the number of line-of-sight calculations by delaying the line-of-sight calculations for each node from when it is explored to when it is expanded. Incremental Phi* is an incremental, more efficient variant of Theta* designed for unknown 2D environments.
* Strict Theta* and Recursive Strict Theta* improves Theta* by restricting the search space to Taut Paths introduced by ANYA. Like Theta*, This is an algorithm that returns near-optimal paths.
Block A* - Generates a local distance database containing all possible paths on a small section of the grid. It references this database to quickly find piece-wise any-angle paths.
ANYA - Finds optimal any-angle paths by restricting the search space to the Taut paths ; looking at an interval of points as a node rather than a single point. The fastest online optimal technique known.
CWave - Uses geometric primitives to represent the propagating wave front on the grid. For single-source path-planning on practical maps, it is demonstrated to be faster than graph search based methods. There are optimal and integer-arithmetic implementations.
There are also A*-based algorithm distinct from the above family:
The performance of a visibility graph approach can be greatly improved by a sparse approach that only considers edges able to form taut paths. A multi-level version called ENLSVG is known to be faster than ANYA, but it can only be used with pre-processing.
Similar to the RRT solution discussed below, it is often necessarily to also take into account steering constraints when piloting a real vechicle. Hybrid A* is an extension of A* that considers two additional dimension representing vehicle state, so that the paths are actually possible. It was created by Stanford Racing as part of the navigation system for Junior, their entry to the DARPA Urban Challenge. A more detailed discussion is written by Peterit, et al.
Informed RRT* improves the convergence speed of RRT* by introducing a heuristic, similar to the way in which A* improves upon Dijkstra's algorithm.
Applications
Any-angle path planning are useful for robot navigation and real-time strategy games where more optimal paths are desirable. Hybrid A*, for example, was used as an entry to a DARPA challenge. The steering-aware properties of some examples also translate to autonomous cars.
