Any-angle path planning
Encyclopedia
Any-angle path planning algorithms search for paths on a cell decomposition of a continuous configuration space
(such as a two-dimensional terrain).
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.
So far, three main any-angle path planning algorithms have been developed, all are based on the heuristic search algorithm A* . Field D* uses interpolation during each vertex expansion. Theta* checks for shortcuts during each vertex expansion. Finally, Block A* uses a look-up table to quickly find piece-wise any-angle paths. While Theta* find paths that are no longer than A* paths, the found path may not be the ground truth
optimal path. Unlike Theta* and Field D*, Block A* is guaranteed to find the ground-truth optimal path given that Block A* uses a sufficiently large look-up table.
Configuration space
- Configuration space in physics :In classical mechanics, the configuration space is the space of possible positions that a physical system may attain, possibly subject to external constraints...
(such as a two-dimensional terrain).
Consider, for example, a uniform grid with blocked and unblocked cells. Searching the corresponding visibility graph
Visibility graph
In computational geometry and robot motion planning, a visibility graph is a graph of intervisible locations, typically for a set of points and obstacles in the Euclidean plane. Each node in the graph represents a point location, and each edge represents a visible connection between them...
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.
So far, three main any-angle path planning algorithms have been developed, all are based on the heuristic search algorithm A* . Field D* uses interpolation during each vertex expansion. Theta* checks for shortcuts during each vertex expansion. Finally, Block A* uses a look-up table to quickly find piece-wise any-angle paths. While Theta* find paths that are no longer than A* paths, the found path may not be the ground truth
Ground truth
Ground truth is a term used in cartography, meteorology, analysis of aerial photographs, satellite imagery and a range of other remote sensing techniques in which data are gathered at a distance. Ground truth refers to information that is collected "on location." In remote sensing, this is...
optimal path. Unlike Theta* and Field D*, Block A* is guaranteed to find the ground-truth optimal path given that Block A* uses a sufficiently large look-up table.