Project "Any-Angle Path Planning"
(scroll down for publications)

In robotics (and video games), one often discretizes continuous terrain into grids with blocked and unblocked cells and then uses search methods to find shortest paths on the resulting grids, which is fast. However, these paths are not shortest paths in the continuous terrain. Search methods on visibility graphs find shortest paths in two-dimensional (but not three-dimensional) continuous terrain. However, this is slow since the number of edges of visibility graphs can be quadratic in the number of vertices.

My collaborators and I used the term "any-angle path" for paths that connect grid vertices that do not need to be adjacent in the grid. We analyzed the lengths of various variants of shortest any-angle paths and then developed heuristic search algorithms based on A* that find short any-angle paths by propagating information only along grid edges (to achieve small runtimes) but without constraining the paths to grid edges (to find short paths). For example, we developed Theta* and several variants of it and demonstrated their advantages for both grid-based path finding and motion planning with complex nonholonomic constraints, showing that Theta* is simple, fast and finds short and realistic looking paths. Theta* has been extended and compared against by others due to its simplicity. Theta* also inspired others to develop fast any-angle path-planning algorithms that find shortest any-angle paths. Our first paper on Theta* received a AAAI Classic Paper (= "Test of Time") Award, and our Lazy Theta* is now part of ROS 2 according to S. Macenski, T. Moore, D. Lu, A. Marzlyakov, and M. Ferguson, "From the Desks of ROS Maintainers: A Survey of Modern & Capable Mobile Robotics Algorithms in the Robot Operating System 2."

Tutorials

• Tutorial Slides
• Theta*: Any-Angle Path Planning for Smoother Trajectories in Continuous Environments (on aigamedev.com)
• Lazy Theta*: Faster Any-Angle Path Planning (on aigamedev.com)

Visualization

• Theta* Applet

Code

• Code of several any-angle path-planning algorithms (including Theta*), as discussed in T. Uras and S. Koenig. An Empirical Comparison of Any-Angle Path-Planning Algorithms. In Proceedings of the Annual Symposium on Combinatorial Search, 2015 (see below under "Representative Overview Publication" for the online version of the paper). If you use the code, please reference it as follows in your publications: "T. Uras and S. Koenig. An Empirical Comparison of Any-Angle Path-Planning Algorithms. In Proceedings of the Annual Symposium on Combinatorial Search, 2015. Code available at: https://idm-lab.org/anyangle". Our code includes an implementation of Daniel Harabor's ANYA. Daniel has published an improved version of ANYA since then and makes a JAVA implementationn of it, along with a C++ implementation of his Polyanya, available on bitbucket.

Class Project

• Class Project on Any-Angle Path Planning

Representative Overview Publications

• T. Uras and S. Koenig. An Empirical Comparison of Any-Angle Path-Planning Algorithms [Short Paper]. In Symposium on Combinatorial Search (SoCS), 206-210, 2015. [downloadable]
  

• A. Nash and S. Koenig. Any-Angle Path Planning. Artificial Intelligence Magazine, 34, (4), 85-107, 2013. [downloadable]
  

Representative Publications

• J. Bailey, A. Nash, C. Tovey and S. Koenig. Path-Length Analysis for Grid-Based Path Planning. Artificial Intelligence, 301, 103560, 2021. [downloadable]
  

• J. Han, T. Uras and S. Koenig. Toward a String-Pulling Approach to Path Smoothing on Grid Graphs. In Symposium on Combinatorial Search (SoCS), 106-110, 2020. [downloadable]
  

• L. Palmieri, S. Koenig and K. Arras. RRT-Based Nonholonomic Motion Planning Using Any-Angle Path Biasing. In IEEE International Conference on Robotics and Automation (ICRA), 2775-2781, 2016. [downloadable]
  

• J. Bailey, C. Tovey, T. Uras, S. Koenig and A. Nash. Path Planning on Grids: The Effect of Vertex Placement on Path Length. In Artificial Intelligence and Interactive Digital Entertainment Conference (AIIDE), 108-114, 2015. [downloadable]
  

• T. Uras and S. Koenig. Speeding-up Any-Angle Path-Planning on Grids [Short Paper]. In International Conference on Automated Planning and Scheduling (ICAPS), 234-238, 2015. [downloadable]
  

• 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. [downloadable]
  

• A. Nash, S. Koenig and C. Tovey. Lazy Theta*: Any-Angle Path Planning and Path Length Analysis in 3D. In AAAI Conference on Artificial Intelligence (AAAI), 2010. [downloadable]
  

• A. Nash, S. Koenig and M. Likhachev. Incremental Phi*: Incremental Any-Angle Path Planning on Grids. In International Joint Conference on Artificial Intelligence (IJCAI), 1824-1830, 2009. [downloadable]
  

• A. Nash, K. Daniel, S. Koenig and A. Felner. Theta*: Any-Angle Path Planning on Grids. In AAAI Conference on Artificial Intelligence (AAAI), 1177-1183, 2007. [downloadable]
  

Dissertation

• A. Nash. Any-Angle Path Planning. PhD thesis, Department of Computer Science, University of Southern California, Los Angeles (California), 2012. [downloadable]
  

Part of this material is based upon research supported by the National Science Foundation under grant number IIS-1319966 and by Northrop Grumman via a fellowship to Alex Nash. Any opinions, findings, and conclusions or recomendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the sponsoring organizations.

If you have comments on any of these papers, please send me an email! Also, please send me your papers if we have common interests.

This page was automatically created by a bibliography maintenance system that was developed as part of an undergraduate research project, advised by Sven Koenig.

Home Page of Sven Koenig