Efficient Optimal Search of Euclidean-Cost Grids and Lattices

James Kuffner
Proc. IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS'04), October, 2004.


Download
  • Adobe portable document format (pdf) (353KB)
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Abstract
We describe a simple technique to speed up optimal path planning on Euclidean-cost grids and lattices. Many robot navigation planning algorithms build approximate grid representations of the environment and use Djikstra? algorithm or A* to search the resulting embedded graph for an optimal path between given start and goal locations. However, the classical implementations of these search algorithms were designed to find optimal paths on arbitrary graphs with edges having arbitrary positive weight values. This paper explains how to exploit the structure of optimal paths on Euclidean-cost grids and lattices in order to reduce the number of neighboring nodes considered during a node expansion step. The result is a reduction in both the total nodes examined as well as the overall cost of the search. The algorithm presented increases the efficiency of robot navigation planning on 2D and 3D grids, and generalizes to any other search problem that involves searching Euclideancost grids and lattices in higher dimensions.

Keywords
path planning, graph search, grids and lattices

Notes
Associated Center(s) / Consortia: Center for the Foundations of Robotics

Text Reference
James Kuffner, "Efficient Optimal Search of Euclidean-Cost Grids and Lattices," Proc. IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS'04), October, 2004.

BibTeX Reference
@inproceedings{Kuffner_2004_4751,
   author = "James Kuffner",
   title = "Efficient Optimal Search of Euclidean-Cost Grids and Lattices",
   booktitle = "Proc. IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS'04)",
   publisher = "IEEE",
   month = "October",
   year = "2004",
}