D* Lite
Sven Koenig
College of Computing
Georgia Institute of Technology
Atlanta, GA 30312-0280
skoenig@cc.gatech.edu
Maxim Likhachev
School of Computer Science
Carnegie Mellon University
Pittsburgh, PA 15213
maxim+@cs.cmu.edu
Abstract
Incremental heuristic search methods use heuristics to focus
their search and reuse information from previous searches to
find solutions to series of similar search tasks much faster
than is possible by solving each search task from scratch. In
this paper, we apply Lifelong Planning A* to robot navigation
in unknown terrain, including goal-directed navigation in un-
known terrain and mapping of unknown terrain. The resulting
D* Lite algorithm is easy to understand and analyze. It im-
plements the same behavior as Stentz’ Focussed Dynamic A*
but is algorithmically different. We prove properties about
D* Lite and demonstrate experimentally the advantages of
combining incremental and heuristic search for the applica-
tions studied. We believe that these results provide a strong
foundation for further research on fast replanning methods in
artificial intelligence and robotics.
Introduction
Incremental search methods, such as DynamicSWSF-FP
(Ramalingam & Reps 1996), are currently not much used in
artificial intelligence. They reuse information from previous
searches to find solutions to series of similar search tasks
much faster than is possible by solving each search task
from scratch. An overview is given in (Frigioni, Marchetti-
Spaccamela, & Nanni 2000). Heuristic search methods,
such as A* (Nilsson 1971), on the other hand, use heuristic
knowledge in form of approximations of the goal distances
to focus the search and solve search problems much faster
than uninformed search methods. An overview is given in
(Pearl 1985). We recently introduced LPA* (Lifelong Plan-
ning A*), that generalizes both DynamicSWSF-FP and A*
and thus uses two different techniques to reduce its planning
time (Koenig & Likhachev 2001). In this paper, we apply
LPA* to robot navigation in unknown terrain. The robot
could use conventional graph-search methods when replan-
ning its paths after discovering previously unknown obsta-
cles. However, the resulting planning times can be on the
order of minutes for the large terrains that are often used,
which adds up to substantial idle times (Stentz 1994). Fo-
cussed Dynamic A* (D*) (Stentz 1995) is a clever heuris-
tic search method that achieves a speedup of one to two or-
ders of magnitudes(!) over repeated A* searches by mod-
Copyright
c
2002, American Association for Artificial Intelli-
gence (www.aaai.org). All rights reserved.
ifying previous search results locally. D* has been exten-
sively used on real robots, including outdoor HMMWVs
(Stentz & Hebert 1995). It is currently also being inte-
grated into Mars Rover prototypes and tactical mobile robot
prototypes for urban reconnaissance (Matthies et al. 2000;
Thayer et al. 2000). However, it has not been extended by
other researchers. Building on LPA*, we therefore present
D* Lite, a novel replanning method that implements the
same navigation strategy as D* but is algorithmically dif-
ferent. D* Lite is substantially shorter than D*, uses only
one tie-breaking criterion when comparing priorities, which
simplifies the maintenance of the priorities, and does not
need nested if-statements with complex conditions that oc-
cupy up to three lines each, which simplifies the analysis of
the program flow. These properties also allow one to extend
it easily, for example, to use inadmissible heuristics and dif-
ferent tie-breaking criteria to gain efficiency. To gain insight
into its behavior, we present various theoretical properties of
LPA* that also apply to D* Lite. Our theoretical properties
show that LPA* is efficient and similar to A*, a well known
and well understood search algorithm. Our experimental
properties show that D* Lite is at least as efficient as D*.
We also present an experimental evaluation of the benefits of
combining incremental and heuristic search across different
navigation tasks in unknownterrain, including goal-directed
navigation and mapping. We believe that our theoretical and
empirical analysis of D* Lite will provide a strong founda-
tion for further research on fast replanning methods in arti-
ficial intelligence and robotics.
Motivation
Consider a goal-directed robot-navigation task in unknown
terrain, where the robot always observes which of its eight
adjacent cells are traversable and then moves with cost one
to one of them. The robot starts at the start cell and has to
move to the goal cell. It always computes a shortest path
from its current cell to the goal cell under the assumption
that cells with unknown blockage status are traversable. It
then follows this path until it reaches the goal cell, in which
case it stops successfully, or it observes an untraversable
cell, in which case it recomputesa shortest path from its cur-
rent cell to the goal cell. Figure 1 shows the goal distances
of all traversable cells and the shortest paths from its current
cell to the goal cell both before and after the robot has moved
评论0