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

In this paper we introduce focused A* heuristic recomputation (FAHR), an enhancement to A* search that can detect and correct large discrepancies between the heuristic cost-to-go estimate and the true cost function. In situations where these large discrepancies exist, the search may expend significant effort escaping from the Â¿bowlÂ¿ of a local minimum. A* typically computes supporting data structures for the heuristic once, prior to initiating the search. FAHR directs the search out of the bowl by recomputing parts of the heuristic function opportunistically as the search space is explored. FAHR may be used when the heuristic function is in the form of a pattern database. We demonstrate the effectiveness of the algorithm through experiments on a ground vehicle path planning simulation.

Notes

Associated Center(s) / Consortia: Field Robotics Center

Associated Project(s): Autonomous Driving Motion Planning

Text Reference

Matthew McNaughton and Christopher Urmson, "FAHR: Focused A* Heuristic Recomputation," Intelligent Robots and Systems, 2009. IROS 2009. IEEE/RSJ International Conference on, March, 2011, pp. 4893 -4898.

BibTeX Reference

@inproceedings{McNaughton_2011_6817,
   author = "Matthew McNaughton and Christopher Urmson",
   title = "FAHR: Focused A* Heuristic Recomputation",
   booktitle = "Intelligent Robots and Systems, 2009. IROS 2009. IEEE/RSJ International Conference on",
   pages = "4893 -4898",
   publisher = "IEEE",
   month = "March",
   year = "2011",
}

The Robotics Institute

Menu