Project "Any-Angle Path Planning"
(scroll down for publications)
In robotics or 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. We have
therefore developed versions of A* that propagate information only along grid
edges (to achieve small runtimes) but without constraining the paths to grid
edges (to find short paths).
Tutorial
Visualization
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: http://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
Representative Overview Publications
Representative Publications
- L. Palmieri, S. Koenig and K. Arras. RRT-Based Nonholonomic Motion Planning Using Any-Angle Path Biasing. In Proceedings of the 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 Proceedings of the 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 Proceedings of the 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 Proceedings of the 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 Proceedings of the 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 Proceedings of the 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