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. These paths, however, 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, they are slow since the number of edges of visibility graphs can be quadratic in the number of vertices. We have 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). We have thus contributed to laying the foundation for the emerging class of any-angle search methods (of which there existed only a small number of previous methods).
Class Project
Representative Overview Publications
Representative Publications
Part of this material is based upon work supported 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.