Any-angle path planning

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 pathfinding algorithms that search for a Euclidean shortest path between two points on a grid map while allowing the turns in the path to have any angle. The result is a path that cuts directly through open areas and has relatively few turns. ^[1] More traditional pathfinding algorithms such as A* either lack in performance or produce jagged, indirect paths.

Background

Real-world and many game maps have open areas that are most efficiently traversed in a direct way. Traditional algorithms are ill-equipped to solve these problems:

• A* with an 8-connected discrete grid graph (2D; 26 for the 3D triple cubic graph) is very fast, but only looks at paths in 45-degree increments. This behavior gives on average 8% extra path length in 2D and 13% in 3D. ^{[2] : 60, 69} A quick post-smoothing step can be used to straighten (thus shorten) the jagged output, but the result is not guaranteed to be optimal as it does not look at all the possible paths. (More specifically, they cannot change what side of a blocked cell is traversed.) The advantage is that all optimizations of grid A* like jump point search will apply.
• A visibility graph with all the grid points can be searched with A* for the optimal solution in 2D space. However, the performance is problematic since the number of edges in a graph with ${\displaystyle V}$ vertices is ${\displaystyle O(V^{2})}$. Such a graph does not always provide an optimal solution in 3D space. ^[2]

An any-angle path planning algorithm aims to produce optimal or near-optimal solutions while taking less time than the basic visibility graph approach. Fast any-angle algorithms take roughly the same time as a grid-based solution to compute.

Definitions

Taut path

A path where every heading change in the path “wraps” tightly around some obstacle. For a uniform grid, only taut paths can be optimal.

Single-source

A path-finding problem that seeks to find the shortest path to all parts from the graph, starting from one vertex.

Algorithms

A*-based

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

• Field D* ^{[4] [5]} (FD* ^[6] ) and 3D Field D* ^{[7] [8]} - 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 ^[9] and 3D Field D* the corresponding three-dimensional problem.
  • Multi-resolution Field D* ^[10] – Extension of Field D* for multi-resolution grids.
• Theta* ^{[6] [11]} - Uses the same main loop as A*, but for each expansion of a vertex ${\displaystyle s}$, there is a line-of-sight check between ${\displaystyle parent(s)}$ and the successor of ${\displaystyle s}$, ${\displaystyle s'}$. If there is line-of-sight, the path from ${\displaystyle parent(s)}$ to ${\displaystyle s'}$ is used since it will always be at least as short as the path from ${\displaystyle parent(s)}$ to ${\displaystyle s}$ and ${\displaystyle s}$ to ${\displaystyle s'}$. This algorithm works only on uniform-cost grids. ^[6] AP Theta* ^{[6] [11]} is an optimization of Theta* that uses angle-propagation to decrease the cost of performing line-of-sight calculations to O(1).
  • Lazy Theta* ^[12] 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. It is capable enough to run in 3D space.
  • Incremental Phi* ^[13] is an incremental, more efficient variant of Theta* designed for unknown 2D environments. ^[2]
  • Strict Theta* and Recursive Strict Theta* ^[14] improves Theta* by restricting the search space to Taut Paths introduced by ANYA. Like Theta*, This is an algorithm that returns near-optimal paths.
• Block A* ^[15] - 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 ^[16] - Finds optimal any-angle paths by restricting the search space to the Taut paths (a path where every heading change in the path “wraps” tightly around some obstacle); looking at an interval of points as a node rather than a single point. The fastest online optimal technique known. This algorithm is restricted to 2D grids.
• CWave ^{[17] [18]} - Uses geometric primitives (discrete circular arcs and lines) to represent the propagating wave front on the grid. For single-source path-planning on practical maps, it is demonstrated to be faster than graph search based methods. There are optimal and integer-arithmetic implementations.

There are also A*-based algorithm distinct from the above family:

• The performance of a visibility graph approach can be greatly improved by a sparse approach that only considers edges able to form taut paths. A multi-level version called ENLSVG is known to be faster than ANYA, but it can only be used with pre-processing. ^[19]
• PolyAnya generalizes ANYA to work on non-grid maps with polygonal obstacles. ^[20] It is fast, does not require preprocessing (unlike ENLSVG), and is optimal (unlike RRT).
• Similar to the RRT solution discussed below, it is often necessarily to also take into account steering constraints when piloting a real vehicle. Hybrid A* is an extension of A* that considers two additional dimension representing vehicle state, so that the paths are actually possible. It was created by Stanford Racing as part of the navigation system for Junior, their entry to the DARPA Urban Challenge. ^[21] A more detailed discussion is written by Peterit, et al. ^[22]

RRT-based

Main article: Rapidly-exploring random tree § Variants

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) ^[23] 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* ^{[24] [25]}
• Informed RRT* ^[26] improves the convergence speed of RRT* by introducing a heuristic, similar to the way in which A* improves upon Dijkstra's algorithm.

Other algorithms

• Probabilistic roadmap

Applications

Any-angle path planning are useful for robot navigation and real-time strategy games where more optimal paths are desirable. Hybrid A*, for example, was used as an entry to a DARPA challenge. ^[21] The steering-aware properties of some examples also translate to autonomous cars.

See also

• Motion planning

References

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. A. Nash. Any-Angle Path Planning. PhD thesis, Department of Computer Science, University of Southern California, Los Angeles (California), 2012.
3. 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.
4. D. Ferguson and A. Stentz. Field D*: An Interpolation-Based Path Planner and Replanner. Proceedings of the International Symposium on Robotics Research, 2005.
5. 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
6. 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.
7. 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.
8. 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. CiteSeerX   10.1.1.188.150 . doi:10.1109/IROS.2006.282516. ISBN   978-1-4244-0258-8. S2CID   1845942.
9. 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–73. doi:10.1145/102782.102784. hdl: 1813/8768 . S2CID   12673773.
10. Dave Ferguson and Anthony Stentz. Multi-resolution Field D*. Proceedings of the International Conference on Intelligent, 2006.
11. Daniel, K.; Nash, A.; Koenig, S.; Felner, A. (2010). "Theta*: Any-Angle Path Planning on Grids" (PDF). Journal of Artificial Intelligence Research. 39: 533–579. doi: 10.1613/jair.2994 .
12. Nash, A.; Koenig, S.; Tovey, C. (2010). "Lazy Theta*: Any-Angle Path Planning and Path Length Analysis in 3D" (PDF). Proceedings of the AAAI Conference on Artificial Intelligence. 24: 147–154. doi:10.1609/aaai.v24i1.7566. S2CID   3754577.
13. Nash, A.; Koenig, S.; Likhachev, M. (2009). "Incremental Phi*: Incremental Any-Angle Path Planning on Grids" (PDF). Proceedings of the International Joint Conference on Artificial Intelligence: 1824–1830.
14. Shunhao Oh, Hon Wai Leong, 2016. Strict Theta*: Shorter Motion Path Planning Using Taut Paths. In Proceedings of Twenty-Sixth International Conference on Automated Planning and Scheduling. https://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13049
15. 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.
16. Daniel Harabor and Alban Grastien. An Optimal Any-Angle Pathfinding Algorithm. Proceedings of the Twenty-Third International Conference on Automated Planning and Scheduling.
17. Sinyukov, Dmitry A.; Padir, Taskin (May–June 2017). "CWave: High-Performance Single-Source Any-Angle Path Planning on a Grid". Proceedings of the 2017 IEEE International Conference on Robotics and Automation (ICRA). 2017 IEEE International Conference on Robotics and Automation (ICRA). Singapore: IEEE. pp. 6190–6197. doi:10.1109/ICRA.2017.7989733.
18. Sinyukov, Dmitry A.; Padir, Taskin (2020). "CWave: Theory and Practice of a Fast Single-source Any-angle Path Planning Algorithm". Robotica. 38 (2). Cambridge University Press: 207–234. doi:10.1017/S0263574719000560. S2CID   182189674.
19. Oh, Shunhao; Leong, Hon Wai (5 June 2017). "Edge N-Level Sparse Visibility Graphs: Fast Optimal Any-Angle Pathfinding Using Hierarchical Taut Paths". Tenth Annual Symposium on Combinatorial Search. arXiv: 1702.01524 .
20. Cui, Michael; Harabor, Daniel D.; Grastien, Alban (2017). "Compromise-free Pathfinding on a Navigation Mesh". Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence: 496–502.
21. Junior: The Stanford Entry in the Urban Challenge
22. Petereit, Janko; Emter, Thomas; Frey, Christian W.; Kopfstedt, Thomas; Beutel, Andreas (May 2012). "Application of Hybrid A* to an Autonomous Mobile Robot for Path Planning in Unstructured Outdoor Environments". ROBOTIK 2012; 7th German Conference on Robotics: 1–6.
23. LaValle, Steven M. (October 1998). "Rapidly-exploring random trees: A new tool for path planning" (PDF). Technical Report (TR 98–11).
24. Karaman, Sertac; Frazzoli, Emilio (3 May 2010). "Incremental Sampling-based Algorithms for Optimal Motion Planning". arXiv: 1005.0416 [cs.RO].
25. Karaman, Sertac; Frazzoli, Emilio (5 May 2011). "Sampling-based Algorithms for Optimal Motion Planning". arXiv: 1105.1186 [cs.RO].
26. Gammell, Jonathan D.; Srinivasa, Siddhartha S.; Barfoot, Timothy D. (2014). "Informed RRT*: Optimal Sampling-based Path Planning Focused via Direct Sampling of an Admissible Ellipsoidal Heuristic". 2014 IEEE/RSJ International Conference on Intelligent Robots and Systems. pp. 2997–3004. arXiv: 1404.2334 . doi:10.1109/IROS.2014.6942976. ISBN   978-1-4799-6934-0.

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.
• Any Angle Pathfinding, Shunhao Oh's open source demonstration code