Project "Fast Replanning (Incremental Heuristic Search)"
(scroll down for publications)

Agents 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, I 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 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. My collaborators and I developed many incremental heuristic search methods, including ones that work according to different principles than the few previously existing ones, analyzed their properties and applied them in a variety of settings to demonstrate their advantages, including for goal-directed navigation in initially unknown terrain and novel settings such as STRIPS-type symbolic planning, mapping, reinforcement learning, moving-target search and any-angle search. For example, we analyzed goal-directed navigation with the freespace assumption (the common-sense navigation strategy behind Stentz' D* and other systems) and showed that its worst-case travel distance is close to optimal. We later applied the analysis also to other navigation strategies, such as Greedy Mapping. We showed that there are four classes of incremental heuristic search algorithms, characterized their advantages and disadvantages, developed a variety of algorithms for them and explored their applications. For example, Minimax LPA* seems to be the first incremental heuristic minimax search method and is able to speed up the parti-game algorithm substantially. Similarly, the PINCH system is able to speed up one-time planning with HSP substantially, the SHERPA system is able to speed up repeated optimal planning with HSP substantially, RTAA* is able to update the heuristics much faster than the standard real-time heuristic search algorithm LRTA* (resulting in smaller search times), LPA* is able to speed up multi-agent path-finding solvers substantially, and variants/ideas of LPA* and its goal-directed navigation variant D* Lite have been widely used by others (including the developers of D*) in robotics, for example, on the winning DARPA Urban Challenge entry and a Mars rover as well as for sampling-based motion planning (BIT* and RRT#). 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*) received a AAAI Classic Paper (= "Test of Time") Honorable Mention. It and our other incremental heuristic search methods seem to have become popular incremental heuristic search methods with a variety of research groups (without any involvement by us). Here are some examples:

Most of our publications include a version of the following disclaimer: "It is important to realize that experimental results, such as the runtimes of the search algorithms, depend on a variety of factors, including implementation details (such as the data structures, tie-breaking strategies, and coding tricks used) and experimental setups (such as whether the gridworlds are four-neighbor or eight-neighbor gridworlds). We do not know of any better method for evaluating search algorithms than to implement them as best as possible, publish their runtimes, and let other researchers experiment with their own and thus potentially different implementations and experimental setups." The reason for this disclaimer is that it would be important to have good computational models that can predict the performance of incremental heuristic search methods as a function of the search problems, implementation details and experimental setups. For example, D* Lite runs much faster than A* in some situations but also much slower in other situations. Its runtime advantage depends on the connectivity of the grid (for example, whether it is a four-neighbor or eight-neighbor grid) and its implementation of the priority queue (for example, whether the priority queue is implemented with a binary heap or buckets). In general, runtime proxies, such as the number of expansions, cannot be used to evaluate incremental heuristic search methods since they all need different amounts of time per expansion. Furthermore, they typically operate on search problems that fit into memory. Big O-analyses do not make sense for small search problems and implementation details really do matter and can have a large effect on the runtime. We definitely need to understand better which heuristic search method to use in which situation.

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 Moving Target 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 recommendations 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.

Home Page of Sven Koenig