Any-angle path planning

From Wikipedia, the free encyclopedia
Jump to: navigation, search
The path found by A* on an octile grid vs. the shortest path between the start and goal nodes.

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.[1] 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.

Motivation[edit]

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 vertices is . Searching the discrete grid graph can be done quickly since the number of edges grows linearly with the number of vertices, but the paths are not optimal 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.[citation needed]

Algorithms[edit]

A*-based[edit]

So far, four main any-angle path planning algorithms that are based on the heuristic search algorithm A*[2] have been developed, all of which propagate information along grid edges:

  • Field D*[3][4] (FD*[5]) and 3D Field D*[6][7] - 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[8] and 3D Field D* the corresponding three-dimensional problem.
  • Theta*[5][9] - 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 on uniform-cost grids, but can be adapted to weighted grids.[5] AP Theta*[5][9] 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*[10] 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*[11] is an incremental, more efficient variant of Theta* designed for unknown 2D environments.[12]
  • Block A* [13] - 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[14] - Finds optimal any-angle paths by looking at an interval of points as a node rather than a single point.

RRT-based[edit]

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)[15] 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*[16][17]
  • Informed RRT*[18] improves the convergence speed of RRT* by introducing a heuristic, similar to the way in which A* improves upon Dijkstra's algorithm.

Applications[edit]

Hybrid A* was created by Stanford Racing as part of the navigation system for Junior, their entry to the DARPA Urban Challenge.[19] 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 constraints of the vehicle.

See also[edit]

Applications[edit]

References[edit]

  1. ^ Tansel Uras and Sven Koenig. An Empirical Comparison of Any-Angle Path-Planning Algorithms. Proceedings of the Eighth International Symposium on Combinatorial Search.
  2. ^ P. Hart, N. Nilsson and B. Raphael, A Formal Basis for the Heuristic Determination of Minimum Cost Paths, IEEE Trans. Syst. Science and Cybernetics, SSC-4(2), 100-107, 1968.
  3. ^ D. Ferguson and A. Stentz. Field D*: An Interpolation-Based Path Planner and Replanner. Proceedings of the International Symposium on Robotics Research, 2005.
  4. ^ David Ferguson and Anthony (Tony) Stentz, "The Field D* Algorithm for Improved Path Planning and Replanning in Uniform and Non-Uniform Cost Environments," tech. report CMU-RI-TR-05-19, Robotics Institute, Carnegie Mellon University, June, 2005
  5. ^ a b c d A. Nash, K. Daniel, S. Koenig and A. Felner. Theta*: Any-Angle Path Planning on Grids. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 1177–1183, 2007.
  6. ^ Carsten, Joseph; Ferguson, Dave; Stentz, Anthony (October 9–15, 2006). "3D Field D*: Improved Path Planning and Replanning in Three Dimensions" (PDF). Intelligent Robots and Systems, 2006 IEEE/RSJ International Conference on. Proceedings of the 2006 IEEE/RSJ International Conference on Intelligent Robots and Systems. Beijing, China: IEEE. pp. 3381–3386. doi:10.1109/IROS.2006.282516. Retrieved 2014-11-07. 
  7. ^ Carsten, J.; Ferguson, D.; Stentz, A. (2006). "3D Field D: Improved Path Planning and Replanning in Three Dimensions". 2006 IEEE/RSJ International Conference on Intelligent Robots and Systems. p. 3381. ISBN 1-4244-0258-1. doi:10.1109/IROS.2006.282516. 
  8. ^ Mitchell, J. S. B.; Papadimitriou, C. H. (1991). "The weighted region problem: Finding shortest paths through a weighted planar subdivision". Journal of the ACM. 38: 18. doi:10.1145/102782.102784. 
  9. ^ a b K. Daniel, A. Nash, S. Koenig and A. Felner. Theta*: Any-Angle Path Planning on Grids. Journal of Artificial Intelligence Research, 39, 533-579, 2010.
  10. ^ A. Nash, S. Koenig and C. Tovey. Lazy Theta*: Any-Angle Path Planning and Path Length Analysis in 3D. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), 2010.
  11. ^ A. Nash, S. Koenig and M. Likhachev. Incremental Phi*: Incremental Any-Angle Path Planning on Grids. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 1824-1830, 2009.
  12. ^ A. Nash. Any-Angle Path Planning. PhD thesis, Department of Computer Science, University of Southern California, Los Angeles (California), 2012.
  13. ^ P. Yap, N. Burch, R. Holte, and J. Schaeffer, Block A*: Database-Driven Search with Applications in Any-angle Path-Planning. Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence, 2011.
  14. ^ Daniel Harabor and Alban Grastien. An Optimal Any-Angle Pathfinding Algorithm. Proceedings of the Twenty-Third International Conference on Automated Planning and Scheduling.
  15. ^ LaValle, Steven M. (October 1998). "Rapidly-exploring random trees: A new tool for path planning" (PDF). Technical Report. Computer Science Department, Iowa State University (TR 98-11). 
  16. ^ Karaman, Sertac; Frazzoli, Emilio (3 May 2010). "Incremental Sampling-based Algorithms for Optimal Motion Planning". arXiv:1005.0416Freely accessible [cs.RO]. 
  17. ^ Karaman, Sertac; Frazzoli, Emilio (5 May 2011). "Sampling-based Algorithms for Optimal Motion Planning". arXiv:1105.1186Freely accessible [cs.RO]. 
  18. ^ Gammell, Jonathan D.; Srinivasa, Siddhartha S.; Barfoot, Timothy D. (8 Apr 2014). "Informed RRT*: Optimal Sampling-based Path Planning Focused via Direct Sampling of an Admissible Ellipsoidal Heuristic". arXiv:1404.2334Freely accessible [cs.RO]. 
  19. ^ Junior: The Stanford Entry in the Urban Challenge

External links[edit]