The Robotics Institute

Carnegie Mellon Robotics Institute

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

This paper presents a solution to the problem of finding an effective yet admissible heuristic function for A* by precomputing a look-up table of solutions. This is necessary because traditional heuristic functions such as Euclidean distance often produce poor performance for certain problems. Here, the technique is applied to the state lattice, which is used for full state space motion planning. However, the approach is applicable to many applications of heuristic search algorithms. The look-up table is demonstrated to be feasible to generate and store. A principled technique is presented for selecting which queries belong in the table. Finally, the results are validated through testing on a variety of path planning problems.

Notes

Associated Center(s) / Consortia: National Robotics Engineering Center

Number of pages: 6

Text Reference

Ross Alan Knepper and Alonzo Kelly, "High Performance State Lattice Planning Using Heuristic Look-Up Tables," 2006 IEEE/RSJ International Conference on Intelligent Robots and Systems, October, 2006, pp. 3375 - 3380.

BibTeX Reference

@inproceedings{Knepper_2006_5620,
   author = "Ross Alan Knepper and Alonzo Kelly",
   title = "High Performance State Lattice Planning Using Heuristic Look-Up Tables",
   booktitle = "2006 IEEE/RSJ International Conference on Intelligent Robots and Systems",
   pages = "3375 - 3380",
   month = "October",
   year = "2006",
}

The Robotics Institute

Menu