Anytime Dynamic A*: An Anytime, Replanning Algorithm
Maxim Likhachev + , Dave Ferguson + , Geoff Gordon + , Anthony Stentz + , and Sebastian Thrun
+
School ofComputer Science

Computer Science Department
Carnegie Mellon University Stanford University
Pittsburgh, PA, USA Stanford, CA, USA
Abstract
We present a graph-based planning and replanning al-
gorithm able to produce bounded suboptimal solutions
in an anytime fashion. Our algorithm tunes the quality
of its solution based on available search time, at every
step reusing previous search efforts. When updated in-
formation regarding the underlying graph is received,
the algorithm incrementally repairs its previous solu-
tion. The result is an approach that combines the bene-
f i ts of anytime and incremental planners to provide ef-
f i cient solutions to complex, dynamic search problems.
We present theoretical analysis of the algorithm, exper-
imental results on a simulated robot kinematic arm, and
two current applications in dynamic path planning for
outdoor mobile robots.
Introduction
Planning for systems operating in the real world involves
dealing with a number ofchallenges not faced in many sim-
pler domains. Firstly, the real world is an inherently un-
certain and dynamic place; accurate models for planning are
diff i cult to obtain and quickly become out ofdate. Secondly,
when operating in the real world, time for deliberation is
usually very limited; agents need to make decisions and act
upon these decisions quickly.
Fortunately, a number of researchers have worked on
these challenges. To cope with imperfect information and
dynamic environments, eff i cient replanning algorithms have
been developed that correct previous solutions based on up-
dated information (Stentz 1994; 1995; Koenig & Likhachev
2002b; 2002a; Ramalingam & Reps 1996; Barto, Bradtke,
& Singh 1995). These algorithms maintain optimal solu-
tions for a fraction of the computation required to generate
such solutions from scratch.
However, when the planning problem is complex, it
may not be possible to obtain optimal solutions within the
deliberation time available to an agent. Anytime algo-
rithms (Zilberstein & Russell 1995; Dean & Boddy 1988;
Zhou & Hansen 2002; Likhachev, Gordon, & Thrun 2003)
have shown themselves to be particularly appropriate in such
settings, as they usually provide an initial, possibly highly-
suboptimal solution very quickly, then concentrate on im-
Copyright c  2005, American Association for Artif i cial Intelli-
gence (www.aaai.org). All rights reserved.
proving this solution until the time available for planning
runs out.
As of now, there has been relatively little interaction be-
tween these two areas of research. Replanning algorithms
have concentrated on f i nding a single solution with a f i xed
suboptimality bound, and anytime algorithms have con-
centrated on static environments. But the most interest-
ing problems, for us at least, are those that are both dy-
namic (requiring replanning) and complex (requiring any-
time approaches). For example, our current work focuses on
path planning in dynamic, relatively high-dimensional state
spaces, such as trajectory planning with velocity considera-
tions for mobile robots navigating partially-known outdoor
environments.
In this paper, we present a heuristic-based, anytime re-
planning algorithm that bridges the gap between these two
areas of research. Our algorithm, Anytime Dynamic A*
(AD*), continually improves its solution while deliberation
time allows, and corrects its solution when updated informa-
tion is received. A simple example ofits application to robot
navigation in an eight-connected grid is shown in Figure 1.
This paper is organised as follows. We begin by
discussing current incremental replanning algorithms, fo-
cussing in particular on D* and D* Lite (Stentz 1995;
Koenig & Likhachev 2002a). Next, we present existing any-
time algorithms, including the recent Anytime Repairing A*
algorithm (Likhachev, Gordon, & Thrun 2003). We then
introduce our novel algorithm, Anytime Dynamic A*, and
provide an example real-world application in dynamic path
planning for outdoor mobile robots. We demonstrate the
benef i ts of the approach through experimental results and
conclude with discussion and extensions.
Incremental Replanning
As mentioned above, often the information an agent has con-
cerning its environment (e.g. its map) is imperfect or incom-
plete. As a result, any solution generated using its initial
information may turn out to be invalid or suboptimal as it
receives updated information through, for example, an on-
board or offboard sensor. It is thus important that the agent is
able to replan optimal paths when new information arrives.
A number of algorithms exist for performing this re-
planning (Stentz 1995; Barbehenn & Hutchinson 1995;
Ramalingam & Reps 1996; Ersson & Hu 2001; Huim-