Project "Fast Replanning (Incremental Heuristic
Search)"
(scroll down for publications)
Agents (such as robots or video game characters) often operate in domains that are only incompletely known or change dynamically. One way of dealing with incomplete information is to interleave search with action execution. In this case, the agents need to replan quickly. To make search fast, we have studied both heuristic search methods with limited lookahead (agent-centered search, such as real-time heuristic search) and heuristic search methods that reuse information from previous searches (incremental heuristic search). Incremental heuristic search methods, for example, are often faster than A* searches from scratch, yet differ from other replanning methods (such as planning by analogy) in that their solution quality is as good as the solution quality of A* searches from scratch. We have developed a variety of incremental heuristic search methods, including incremental heuristic search methods that work according to different principles than the few previously existing ones, analyzed their properties, and applied them in different settings to demonstrate their advantages. Existing settings include goal-directed navigation in initially unknown terrain. For example, we have been able to show that the worst-case travel distance of the navigation strategy behind Anthony Stentz' D* is close to optimal. Novel settings include STRIPS-type symbolic planning, mapping, reinforcement learning and any-angle search. For example, our Minimax LPA* seems to be the first incremental heuristic minimax search method and can speed up the parti-game algorithm substantially. Similarly, our PINCH system can speed up one-time planning with HSP (a popular heuristic search-based planner at the time) substantially, and our SHERPA system can speed up repeated optimal planning with HSP substantially. Finally, our Planning on Demand architecture demonstrated that incremental heuristic search allows the path planning module of mobile robot architectures to handle initially unknown obstacles rather than having to delegate this task to the reactive navigation module. Our D* Lite (which is different from D*) seems to have become a popular incremental heuristic search method with a variety of research groups. For example, David Wooden writes in his dissertation about our LPA* that it "has led to a series of algorithms, including D* lite, ... (The name "lite" is perhaps an unfortunate choice, as the algorithm is indeed not a diluted or handicapped version of D*.) ... In fact, Stentz's lab (where D* was introduced) uses D* Lite in many of its current implementations in place of D* ...", citing "Ferguson, D. personal communication, May 2006" (David Wooden, Graph-based Path Planning for Mobile Robots, Dissertation, School of Electrical and Computer Engineering, Georgia Institute of Technology, December 2006, page 11). Indeed, Dave Ferguson and Anthony Stentz used elements of D* Lite in a highly optimized version of their Field D* system, that researchers from NASA's Jet Propulsion Laboratory used to control the Mars rovers "Spirit" and "Opportunity" in test mode (without any involvement by us). Maxim Likhachev and Dave Ferguson used a combination of ARA* and D* Lite, called Anytime D*, to plan long motions involving complex maneuvers (such as traversal of parking lots and complex u-turns) for the winning DARPA Urban Challenge entry from CMU (again without any involvement by us). We have thus contributed to laying a strong foundation for the emerging class of incremental heuristic search methods (of which there existed only a small number of previous methods).
The "Artificial Intelligence Topics" webpages on "Search" of the Association for the Advancement of Artificial Intelligence link to this page. The game programming webpages on "Amit's Thoughts on Path-Finding and A*" link to this page as well.
Tutorial
Applet
Code
The following code should be correct but is somewhat out of date. In particular, Lifelong Planning A* and D* Lite can now use buckets as priority queue or, if they use a heap as priority queue, break ties towards larger g-values. These improvements are not yet reflected in the code.
Class Project
Representative Overview Publications
Representative Publications on Heuristic Search
Representative Publications on Symbolic Planning
Representative Publications on Robotics
Representative Publications on Reinforcement Learning
Some of this material is based upon work supported by the National Science Foundation under Grant No. 0350584. 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 National Science Foundation.
Many publishers do not want authors to make their papers available electronically after the papers have been published. Please use the electronic versions provided here only if hardcopies are not yet available. 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.