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 don't constrain their paths to grid edges, in order to be able to find shorter paths. Thus, the heading changes of their paths are not constrained to specific angles, which explains their name. Many of the algorithms also propagate information along grid edges in order to speed up the search.

Algorithms

A*-based

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

• 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 by, for every vertex $s'$ that is explored from a vertex $s$, assigning $s'$ the same parent as $s$ if there is free line-of-sight between ${\displaystyle parent(s)}$ and $s'$; otherwise $s$ is assigned as the parent, just like in A*. It 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 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*^[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.

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)^[13] 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*^[14][15]

• Informed RRT*^[16] improves the convergence speed of RRT* by introducing a heuristic, similar to the way in which A* improves upon Dijkstra's algorithm.

See also

• Motion planning

Applications

• Robot navigation
• Real-time strategy games

References

1. 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.
2. D. Ferguson and A. Stentz. Field D*: An Interpolation-Based Path Planner and Replanner. Proceedings of the International Symposium on Robotics Research, 2005.
3. 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
4. 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.
5. 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.
6. 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. doi:10.1109/IROS.2006.282516. ISBN 1-4244-0258-1.
7. 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.
8. 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.
9. 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.
10. 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.
11. A. Nash. Any-Angle Path Planning. PhD thesis, Department of Computer Science, University of Southern California, Los Angeles (California), 2012.
12. 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.
13. 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).
14. Karaman, Sertac; Frazzoli, Emilio (3 May 2010). "Incremental Sampling-based Algorithms for Optimal Motion Planning". arXiv:1005.0416 [cs.RO].
15. Karaman, Sertac; Frazzoli, Emilio (5 May 2011). "Sampling-based Algorithms for Optimal Motion Planning". arXiv:1105.1186 [cs.RO].
16. 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.2334 [cs.RO].

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.