Any-angle path planning

Any-angle path planning algorithms search for paths on a cell decomposition of a continuous configuration space (such as a two-dimensional terrain).

Motivation

Consider, for example, a uniform grid with blocked and unblocked cells. Searching the corresponding visibility graph finds a shortest path from a given start vertex to a given goal vertex but is typically very slow since the number of edges can grow quadratically in the number of vertices. Searching the corresponding grid graph typically finds suboptimal paths (since, for example, the heading changes of the resulting path are constrained to multiples of 45 degrees on an eight-neighbor grid graph) but is fast since the number of edges grows no faster than linearly in the number of vertices. Optimizing the path after the search typically shortens the path but does not change the topology of the path. It does not find a shortest path, for example, if the path found by the search algorithm passes a blocked cell on the left but the shortest path passes the same blocked cell on the right. Thus, there is an advantage to interleaving the search and the optimization. Any-angle path planning algorithms propagate information along grid edges (to search fast) without constraining their paths to grid edges (to find short paths). Thus, the heading changes of their paths are not constrained to specific angles, which explains their name.

Algorithms

So far, three main any-angle path planning algorithms have been developed, all are based on the heuristic search algorithm A*:^[1]

• Field D*^[2][3] (or simply FD*^[4]) and 3D Field D*^[5][6] 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^[7] and 3D Field D* the corresponding three-dimensional problem.

• Theta*^[4][8] checks for shortcuts during each vertex expansion, and allows the parent of a vertex in the search tree to be a non-neighbor, and finds a near-optimal or optimal path (depending on the geometry of the problem) in uniform-cost grids. AP Theta*^[4][8] is an optimization of Theta* that uses angle-propagation to decrease the cost of performing line-of-sight calculations to O(1), and Lazy Theta*^[9] is an optimization that uses lazy evaluation to reduce the number of line-of-sight calculations. Incremental Phi*^[10] is an incremental, more efficient variant of Theta* designed for unknown 2D environments.^[11]

• Finally, Block A* ^[12] uses a look-up table to quickly find piece-wise any-angle paths.

See also

• Motion planning

Applications

• Robot navigation
• Real-time strategy games

References

External links

• Lazy Theta*: Faster Any-Angle Path Planning
• A. Nash and S. Koenig. Any-Angle Path Planning. Artificial Intelligence Magazine, 34, (4), 85-107, 2013.