Trisha Shetty (Editor)

Any angle path planning

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit
Any-angle path planning

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. Any-angle algorithms are able to find optimal or near-optimal paths by incorporating the any-angle search into the algorithm itself. Algorithms such as A* Post Smoothing that smooth a path found by a grid constrained algorithm are unable to reliably find optimal paths since they cannot change what side of a blocked cell is traversed.

Contents

Motivation

Any-angle path planning algorithms are necessary in order to quickly find an optimal path. For a world represented by a grid of blocked and unblocked cells, the brute-force way to find an any-angle path is to search the corresponding visibility graph. This is problematic since the number of edges in a graph with V vertices is O ( V 2 ) . Searching the discrete grid graph can be done quickly since the number of grows linearly with the number of vertices, but the paths are not optimal since since the angle of the turns are constrained to 45° or 90°, which will add turns and increase the overall length of the path. Smoothing a grid-constrained path after does not fix this problem since the algorithm that found that path did not look at all possible paths. Any-angle path planning algorithms find shorter paths than the grid-constrained algorithms while taking roughly same amount of time to compute.

A*-based

So far, four 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* (FD*) 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.
  • Theta* - Uses the same main loop as A*, but for each expansion of a vertex s , there is a line-of-sight check between p a r e n t ( s ) and the successor of s , s ′ . If there is line-of-sight, the path from p a r e n t ( s ) to s ′ is used since it will always be at least as short as the path from p a r e n t ( s ) to s and s to s ′ . This algorithm works on uniform-cost grids, but can be adapted to weighted grids. AP Theta* 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* 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.
  • 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 looking at an interval of points as a node rather than a single point.

    • RRT-based

    Besides, for search in high-dimensional search spaces, such as when the configuration space of the system involves many degrees of freedom that need to be considered (see Motion planning), and/or momentum needs to be considered (which could effectively double the number of dimensions of the search space; this larger space including momentum is known as the phase space), variants of the rapidly-exploring random tree (RRT) have been developed that (almost surely) converge to the optimal path by increasingly finding shorter and shorter paths:

  • Rapidly-exploring random graph (RRG) and RRT*
  • 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

    Hybrid A* was created by Stanford Racing as part of the navigation system for Junior, their entry to the DARPA Urban Challenge. Hybrid A* is continuous and tracks the vehicle's position and orientation. This ensures that the path generated can be followed by the vehicle, unlike the paths generated by A* for Field D*, which both produce sharp turns, and do not consider the geometry or movement constrains of the vehicle.

    References

    Any-angle path planning Wikipedia
    (Text) CC BY-SA