=Paper=
{{Paper
|id=Vol-1348/maics2013_paper_5
|storemode=property
|title=Navigation on Density-Unbalanced Terrain
|pdfUrl=https://ceur-ws.org/Vol-1348/maics2013_paper_5a.pdf
|volume=Vol-1348
|dblpUrl=https://dblp.org/rec/conf/maics/HanY13
}}
==Navigation on Density-Unbalanced Terrain==
https://ceur-ws.org/Vol-1348/maics2013_paper_5a.pdf
Navigation on Density-Unbalanced Terrain
Qiang Han, Weiya Yue
University of Cincinnati
School of Electronic & Computing System
Cincinnati, OH 45220, USA
hanqg@ucmail.uc.edu, weiyayue@hotmail.com
Abstract When the environment is static, the well known A* algo-
rithm (Hart, Nilsson, & Raphael 1968) uses a vertex evalu-
Navigation algorithms have shown to be important in ation function f (v) to determine the order in which the al-
many practical applications. In an unknown or con- gorithm chooses vertices in the search tree to build the path
stantly changing environment, D* Lite, a classic dy-
from vs to vg . The evaluation function, f (v) has two addi-
namic algorithm, replans a shortest path in an efficient
manner. However, if there are multiple shortest paths, tive components, that is, f (v) = g(v) + h(v), where g(v) is
the D* Lite algorithm arbitrarily selects one. When the actual cost from vs to the current vertex v, and h(v) is
it comes to a density-unbalanced terrain, the shortest a cost estimating heuristic from v to vg . Another algorithm,
paths with the same cost may have different meaning. Lifelong Planning A* (LPA*) (Koenig, Likhachev, & Furcy
The algorithm performance largely depends on how 2004) (Koenig & Likhachev 2001), introduces an additional
crowded are the areas through which the selected short- component, rhs(v), which is calculated using the updated
est path traverses. In this paper, we propose the density- g-value of v’s predecessors and thus potentially better in-
aware D* Lite algorithm, DAD* Lite, which is capa- formed and more updated than v’s own g-value. However,
ble to take into account crowded areas and avoid them LPA* only recalculates the lowest cost path when the agent
to find a (best) shortest path even when this has more
is at vs and it does not replan as the agent moves and finds
detours than other shortest paths. Experiments show
DAD* Lite improves D* Lite by giving better results changes.
on successful runs and moving distance. D* Lite can be treated as a dynamic version of LPA*.
However, unlike LPA*, which detects environment changes
globally, D* Lite employs a parameter called sensor-radius.
Introduction Only vertices that are within sensor-radius from the current
vertex are exactly in sight and the agent has accurate infor-
Navigation algorithms, largely used to develop autonomous mation on these vertices. Therefore, the agent knows only
vehicles, intelligent agents, etc, are an important area of part of the terrain precisely, beyond which it holds old infor-
study in artificial intelligence. Under a dynamic environ- mation, which might be out of date.
ment, knowledge of the terrain – initially partially known, or As the D* algorithm (Stentz 1995) (Stentz 1997), D* Lite
unknown – is updated as the agent (for example, an explor- performs a backward search from vg to vs . For D* and all its
ing planet rover, and vehicle parking) moves. Replanning descendant algorithms, the backward search is the key point
in dynamic circumstances is a very practical problem and to their success, because the g-value of every node v in G
it is a key part of a navigation algorithm. D* Lite (Koenig is exactly the path cost from vg to v and can be reused after
& Likhachev 2002) (Koenig & Likhachev 2005) has been the agent moves. When edge cost changes are detected, and
proven and largely used as an efficient dynamic navigation the g-values of the vertices affected by these changes need
algorithm. to be updated, D* Lite propagates the computation from the
The D* Lite algorithm seeks to find a minimum cost path affected vertices to vs . In most cases, the backward propa-
from the start point to the goal point in the dynamic envi- gation expands much less vertices than a forward search.
ronment. Terrain information is modeled as an undirected D* Lite also uses the “more informed” rhs function to
graph G(V, E) with a start vertex vs and a goal vertex vg . make better vertex updates during expansion. The rhs func-
An edge cost function, denoted by c(v, u), is associated to tion in D* Lite is defined by
each directed edge (v, u), and the cost of a path is the sum
minv0 ∈succ(v) g(v 0 ) + c(v, v 0 ) v 6= vg
of all the edge costs along that path. Determining the global
minimum cost path from vs to vg is by no means trivial since rhs(v) =
0 otherwise.
the known environment information held by the agent may
change unpredictably. Three states are defined for a vertex v: the vertes is lo-
cally consistent if rhs(v) = g(v), locally overconsistent if
rhs(v) < g(v), and locally underconsistent if rhs(v) >
Copyright held by the authors. g(v). To generate the shortest path, D* Lite maintains
the vertices in a priority queue with in ascending order of Planning on Density-Unbalanced Terrain
key − values defined as min(g(v), rhs(v)) + h(vs , v).
Motivation for DAD* Lite
Every time an inconsistent vertex is updated by making D* Lite and all its variants conduct experiments on random
g(v) = rhs(v), the algorithm needs to check whether its terrains. For example, each node on the grid world is se-
neighbor becomes inconsistent. If this happens, this neigh- lected as a block with the same probability and all the un-
bor is added to the queue. D* Lite propagates calculations blocked edges have equal cost. However, the real world en-
until all vertices on the path, including vs , are locally con- vironments are much more complex for which the assump-
sistent. When selecting the shortest path, the agent moves tion of an even-distribution terrain does not hold. Moreover,
to its neighbor vertex with the minimum of g-value plus the these algorithms do not consider the information caused by
edge cost, which is the maximum-g-decrease-value. If the the unbalance, when, in fact, such information can help de-
agent detects any changes that have been made since the velop a more efficient navigation algorithm. Fig. 1 is a Mars
last round, this makes these changed vertices inconsistent, panorama taken by Mars Exploration Rover (Nasa 2012).
and D* Lite adds them to the priority queue for possible up- In the middle of the picture, there is an area crowded with
date. Because D* Lite only updates partially inconsistent rocks, while in other regions the terrain is clear of rocks and
vertices, making (g, rhs) consistent instead of all vertices, spacious.
it can perform much more efficient than the other navigation
algorithms.
D* Lite has been improved by avoiding unneccessary cal-
culations in the case where the previous planned shortest
path is still available and considering the new changes de-
tected there is no better solution to replace this path (Yue &
Franco 2009) (Yue & Franco 2010). Additionally, a variant
of D*, ID* Lite, seeks to reduce calculation by first expand-
ing the vertices which are more likely to contribute a short- Figure 1: Mars Panorama taken by Mars Exploration Rover
est path (Yue et al. 2011). A threshold is used in ID* Lite
to control updates. Only the vertices with key-value smaller Density-unbalanced terrain can be illustrated in a grid
than the threshold can be updated. The threshold value is world as shown in Fig. 2, where vi,j denotes the ith row
increased gradually, until the shortest path is found. Due to
the way of performing undates, ID* Lite avoids unnecessary and j th column vertex. Fig. 2 shows three shortest paths
update significantly and it shows much better results than D* from vs = v3,3 to vg = v0,0 . When the agent starts to move
Lite. from vs , D* Lite picks up one of vs ’s on-the-shortest-path
successors, v3,2 or v2,3 arbitrarily. Based on the perception
There are many other variants from D* Lite, which deal of human beings, going to v2,3 is better, because this area
with different constraints or requirements. For example, is spacious while the bottom left side of the grid is more
DD* Lite (Mills-Tettey, Stentz, & Dias 2006) combines D* crowded. P ath1 may be blocked more in the future, and
Lite with a technique of detecting dominance relationships it does not have a detour. However, D* Lite makes deci-
to solve navigation problems with global constraints. By sions on the next move only depending on c(vs , v) + g(v),
using the dominance relationship it prunes the search tree v ∈ succ(vs ), thus the agent has the same probability to go
obtaining a fast planning. The anytime algorithm family, to the crowded area or the spacious area.
such as AWA* (Hansen & Zhou 2007), ARA* (Likhachev,
Gordon, & Thrun 2003), AD* (Likhachev et al. 2005),
and IAD* (Yue et al. 2012), share the so called inflated
heuristics strategy, according to which the evaluation func-
tion f (v) is replaced by f 0 (v) = g(v) + · h(v), where
>= 1 denotes the inflation factor. Its effect is to increase
the weight of h-value in f (v), which causes fewer vertices to
be updated, and a sub-optimal path is returned. Thus, any-
time algorithms work best in time-limited and suboptimal
solution acceptable environments.
Figure 2: A 4 × 4 4-directional grid example
A new algorithm, Density-Aware D* Lite (DAD* Lite),
which replans a minimum cost path in a density-unbalanced
environment is introduced in this study. Section Planning on
Heuristics in DAD* Lite
Density-Unbalanced Terrain describes DAD* Lite and moti-
vation behind it. The experimental setup, results, and analy- With the above observations, designing an algorithm able
sis are presented in Section Experiments. Finally, Section to select a shortest path in the most spacious region, thus
Conclusion and Future Work concludes the current study avoiding crowded areas is an important problem. To solve
and presents future work. this problem, two issues must be considered.
The first issue concerns the pool of candidate paths, in
particular, how to obtain them. In DAD* Lite, the candi-
date pool contains all the shortest paths from vs to vg . One
could argue that a slightly-longer-than-shortest path that
goes through a much more spacious and easier route each of Procedure Initialize():
the shortest paths, will potentially avoid more interruptions 01. U = ∅;
and finally get to vg with the minimum overall cost. It may 02. km = 0;
help to overcome the shortcomings of the D* Lite family al- 03. for all v ∈ V rhs(v) = g(v) = ∞; eval(v) = 0;
gorithms due to the unpredictable future changes (dynamic 04. rhs(vg ) = 0;
environment) and the inaccurate information (limitation of 05. eval(vg ) = 1;
the sensor radius): D* Lite only computes the shortest path 06. U.Insert(vg , CalcKey(vg ));
based on local and temporary information which turns out Procedure GetDAPath(u)
not to be a globally optimal solution almost certainly. How- 01. if(u 6= vg )
ever we treat this non-trivial problem as our future work and 02. for all v ∈ succ(u)
in this paper, the proposed DAD* Lite algorithm considers 03. if (rhs(u) = g(v) + c(u, v) && eval(v) = 0)
only all the shortest paths as the candidate pool. 04. eval(u)+ =GetDAPath(v);
As a descendant of D* Lite, DAD* Lite uses the same 05. next(u) = argmaxv∈succ(u)&&rhs(u)=g(v)+c(u,v) eval(v);
06. cnt = # of blocked v | v ∈ pred(u);
procedure to calculate shortest paths. D* Lite finds all the
07. eval(u) = eval(u)/2cnt ;
shortest paths after calling ComputerShortestPath() shown 08. return (eval(u));
in the pseudocode of (Koenig & Likhachev 2005). The rea-
son is that when one child of a vertex has been updated to be Procedure GetDAPath()
consistent, then all its other children will be updated to be 01. for all visited v in last round except vg
consistent. So if one shortest path has been found, suppos- 02. eval(v) = 0;
03. GetDAPath(vs );
ing an other arbitrary path p from vs to vg is also shortest,
then the child of vc on p must be updated and consistent too.
Iteratively, all the vertices on p are updated and consistent, Figure 3: Subroutines of DAD* Lite
and thus all alternative shortest paths can be found, as shown
in (Yue & Franco 2009) and (Yue & Franco 2010). The cor-
rectness of DAD* Lite follows from that of D* Lite, and thus
DAD* Lite is guaranteed to find all the shortest paths.
The second issue concerns the design of heuristics to
select a path along with less crowded areas. DAD* Lite
chooses two factors to represent the how crowded a path is:
• Number of blocked path neighbors:
• Number of detours to other shortest paths:
Procedure Main():
The heuristic value of a path is an accumulation of each ver-
01. vlast = vs ;
tex’s evaluation on this path, and DAD* Lite calculates the 02. Initialize();
evaluation value of each vertex along the shortest paths. The 03. ComputeShortestPath();
evaluation value reflects the information of both the number 04. GetDAPath();
of blocked neighbors from this vertex to the goal and the 05. while (vs 6= vg )
number of detours to the other shortest paths. The detailed 06. /* if (g(vg ) = inf) then there is no known path */
computation of the evaluation value is shown next. 07. vs = next(vs );
08. Agent moves to vs ;
DAD* Lite Implementation 09. Scan graph for changed edge costs;
10. if any edge cost changes were observed
Fig. 3 and Fig. 4 illustrate the DAD* Lite pseudocode. 11. km = km + h(vlast , vs );
Since DAD* Lite is built on D* Lite only the new and 12. vlast = vs ;
changed subroutines are shown; the omitted D* Lite sub- 13. for all directed edges (u, v) with changed edge costs
routines can be found in (Koenig & Likhachev 2005). In 14. Update the edge cost c(u, v);
the main function in Fig. 4, when ComputerShortestPath() 15. UpdateVertex(u);
in Line 03 and Line 16 finishes, all the shortest paths are 16. ComputeShortestPath();
found. Then DAD* Lite calls GetDAPath() which aims to 17. GetDAPath();
find the shortest path avoiding crowded areas. Another dif-
ference from D* Lite in the main function, is that when the Figure 4: Main function of DAD* Lite
agent moves, it just moves to next(vs ). next(v) is the next
vertex from v based on the density-aware path.
In Fig. 3, firstly GetDAPath() initializes eval(v) for ver-
tices which are visited in the last round of GetDAPath() com-
putation. Then it calls GetDAPath(v). GetDAPath(v) is a re-
cursive function, which computes eval(v) for each vertex v of the whole terrain area; different crowded areas overlap.
on the shortest paths. Lines 02-07 show how the heuristics Before every navigation, the agent has an old map, in which
are calculated. Lines 02-04 sum the eval(v) of u’s succes- every obstacle is considered wrongly to be at its neighbor
sors only if its successor v is on the shortest paths. This position with probability 0.5. As the agent moves, in each
calculation gives higher value for the vertices with more de- step, all the obstacles in the terrain have probability 0.5 to
tours. Line 05 chooses the vertex v which has the high- move to their neighbors excluding vs and vg .
est evaluation value from all u’s successors and saves it to
next(u). In line 06, cnt counts the number of the blocked Results and Analysis
v in u’s predecessors. The larger cnt, the higher probability In Fig. 6, the performance of D* Lite and DAD* Lite is
that a block will move to u and block the path from u to vg . compared along two aspects – successful runs and moving
Line 07 gives the formula of eval(u), which is is directly distance – with different crowded-percentage. Experiments
proportional to the sum of u’s on-the-shortest-path succes- of D* Lite and DAD* Lite, respectively, run 1000 times. In
sors’ evaluation value, and is inversely proportional to two each experiment, navigation stops when the algorithm can-
to the power of the number of blocks around u. not find a single path from vs to vg and thus vg can never
be reached. successful runs represents the number of exper-
An Example iments in which the agent reaches vg in the end. Among all
Fig. 5 shows how DAD* Lite works in a grid world exam- the successful runs, moving distance measures the average
ple. In Fig. 5(a), (g, rhs) values are calculated in Comput- distance that the agent moves from vs to vg . Compared to
erShortestPath(). GetDAPath() calculates eval(v) in depth- the other D* Lite family algorithms experiments, where the
first-search fashion from the root vs . For example, in Fig. emphasis is mostly on running time and heap operation, suc-
5(b) to calculate eval(v1,3 ), its two successors v1,2 and cessful runs and moving distance reflect a more global point
v0,3 evaluation values are 321
and 321
respectively, and v1,3 of view.
has one blocked neighbor. So eval(v1,3 ) is calculated as 1000 450
D* Lite
1 1 1
( 32 + 32 )/21 = 32 . DAD* Lite
Moving distance
Successful runs 750 400
500 350
250 300
D* Lite
DAD* Lite
0 250
0.15 0.2 0.25 0.3 0.35 0.4 0.15 0.2 0.25 0.3 0.35 0.4
crowded-percentage crowded-percentage
(a) (b)
(a) (g, rhs) value (b) eval(v) value Figure 6: size = 200, sensor − radius = 10, spacious −
percentage = 0.1
Figure 5: A 4-direction grid world example on eval(v) cal-
In Fig. 6(a), DAD* Lite shows better results in success-
culation
ful runs than D* Lite. This benefit reaches the maximum
In Fig. 5(b), arrows indicate the vertex pointed to by at crowded-percentage = 0.3. When crowded-percentage
next(v). Then next(v) always goes to the successor with is small, the terrain is actually rather spacious, with small
the maximum eval. That is, next(vs ) points to v2,3 , be- crowded areas, so the advantage of DAD* Lite is not ob-
1
cause it has a larger eval (equal to 128 ) than v3,2 . It can be vious. As crowded-percentage increases, the crowded ar-
seen in Fig. 5(b) that the eval value has the capability to eas have more obstacles. If a shortest path exists, D* Lite
reflect directly how crowded a shortest path is. picks up one arbitrarily. If this shortest path goes through
crowded areas, the probability that the agent is trapped in
Experiments one of these increases. Therefore, DAD* Lite outperforms
D* Lite in this situation. As crowded-percentage increases,
Experimental Setup fewer and fewer paths can pass through the crowded areas,
In this section, DAD* Lite is compared with D* Lite on ran- so the shortest paths through the crowded areas account for
dom grid terrains. The grid world is a 4-direction square a small proportion among all the shortest paths and there-
terrain with size × size vertices. All the experiments are fore, it becomes easy for D* Lite to select a path avoiding
carried out on the terrain with size = 200. vg = v(20,20) crowded areas. This explains why DAD* Lite gains less in
and vs = v(180,180) . The sensor-radius is the observable dis- successful runs when crowded-percentage = 0.4.
tance from the agent’s current vertex. In every experiment, In Fig. 6(b), DAD* Lite has shorter moving distance than
each vertex in the spacious area is randomly selected as D* Lite. Because the benchmark used is random and the ter-
blocked with some probability spacious-percentage, which rain block density is still small, if the planned shortest path
higher for vertices in crowded areas, described by crowded- is interrupted, it is easier for the algorithm to find an alter-
percentage. To simulate the crowded areas, a number of native shortest path with the same distance as the old one,
squares, with a random side length from 30 to 50, are in- and hence, for both DAD* Lite and D* Lite, the moving dis-
jected in the terrains. The total crowded areas sum up to 30% tance is not big. However, it should be noticed that since
600 600
vs = v(180,180) and vg = v(20,20) , the cost of the possible
Time(milliseconds)
Time(milliseconds)
shortest path is 320. In Fig. 6(b) the values for moving dis- 500 500
tance produced by DAD* Lite are all closed to 320, which 400 400
shows that the benefit of DAD* Lite with respcet to the mov-
300 300
ing distance is relatively stable. D* Lite
DAD* Lite
D* Lite
DAD* Lite
200 200
0.15 0.2 0.25 0.3 0.35 0.4 2 5 10 15 20
1000 450
D* Lite crowded-percentage sensor-radius
DAD* Lite
Moving distance
Successful runs
400
750 (a) sensor-radius = 10, (b) spacious-percentage = 0.1,
500 350 spacious-percentage = 0.1 crowded-percentage = 0.3
300 650
250
D* Lite 600
Time(milliseconds)
DAD* Lite
0 250 500
2 5 10 15 20 2 5 10 15 20
sensor-radius sensor-radius 400
(a) (b) 300 D* Lite
DAD* Lite
200
Figure 7: size = 200, spacious-percentage = 0.1, crowded- 0.1 0.15 0.2 0.25
spacious percentage
percentage = 0.3 = crowded percentage
(c) sensor-radius = 10
In Fig. 7, two algorithms are compared with different
sensor-radius. Fig. 7(a) shows that the number of successful Figure 9: Running time comparisons
runs decreases with sensor-radius for both DAD* Lite and
D*. However, compared to D* Lite, DAD* Lite is less af-
fected by the change of sensor-radius. More importantly, it Similarly, ID* Lite (Yue et al. 2011) also calls a subroutine,
can be seen that DAD* Lite with sensor-radius = 2 shows get-alternative(), to generate the shortest path. Because ID*
the similar result to D* Lite with sensor-radius = 20. In Lite reduces the number of vertices to expand, it consumes
other words, in the same environment, the result of using much less time than D* Lite in total. Another big difference
DAD* Lite is equal to that of using D* Lite with a 10× is that the subroutine get-alternative() in ID* Lite only ex-
sensor-radius. Fig. 7(b) shows the improvement of DAD* pands one shortest path, and thus does not have to traverse
Lite with respect to the moving distance. all the vertices on all the shortest paths as DAD* Lite does.
450 In Fig. 9(a), the difference between two algorithms
1000 D* Lite
DAD* Lite reaches the minimum point at crowded-percentage = 0.3,
Moving distance
Successful runs
750 400
because DAD* Lite saves more moving distance than D*
500 350 Lite as shown in Fig. 6(b). In Fig. 9(c), the biggest differ-
250
D* Lite
300 ence between the two algorithms comes when block percent-
0
DAD* Lite
250
age = 0.1. That is, when the terrain becomes more spacious,
0.1 0.15 0.2 0.25 0.1 0.15 0.2 0.25 there are more shortest paths, therefore GetDAPath() needs
spacious percentage spacious percentage
= crowded percentage = crowded percentage to expand more vertices and thus, it consumes more time.
(a) (b)
Conclusion and Future Work
Figure 8: size = 200, sensor-radius = 10 This study proposed DAD* Lite, the Density-Aware D*
Lite algorithm. Compared to D* Lite selecting a shortest
Fig. 8 depicts the results of two algorithms in the terrains path arbitrarily, DAD* Lite finds a shortest path which may
when spacious percentage = crowded percentage. In this have more detours than other shortest paths and avoid the
case, all blocks are randomly chosen and evenly distributed crowded areas. From a global point of view, by using a
among the terrain. DAD* Lite performs better than D* Lite heuristic to quantify how crowded an area is, DAD* Lite
with respect to both successful runs and moving distance. produces better results than D* Lite. This improvement is
The advantage is small but stable. This result shows that reflected experimentally in the values of successful runs and
even for a block-evenly-distributed terrain, there may exist moving distance.
some random crowded areas, of which DAD* Lite can take From the experimental results, DAD* Lite consumes
advantage to a certain extent. more time than D* Lite, which is determined by the struc-
Fig. 9 shows the running time comparisons of the above ture of the algorithm. Future work will set a threshold on
three experiment configurations, responding to Fig. 6, Fig. running time of GetDAPath() or a threshold on the number
7 and Fig. 8 respectively. Running time is the average time of the shortest paths to search in GetDAPath() to prune the
of all the successful runs in each experiment configuration. search tree. Furthermore, the option of embedding DAD*
Because DAD* Lite inserts the procedure GetDAPath() and Lite heuristic with ID* Lite, in order to shorten computation
it basically has the same structure as D* Lite, potentially its time, will also be explored. However, for a system that does
running time is longer. GetDAPath() has to traverse all the not have a strict time limit, and when crowded areas are an
vertices on the shortest paths to calculate evaluation values. important issue (e.g., the agent may be damaged if traveling
in such areas), DAD* Lite will always have a higher chance ference on Automated Planning and Scheduling (ICAPS),
to reach vg successfully on the shorter path (i.e., moving less 262–271.
distance). Likhachev, M.; Gordon, G.; and Thrun, S. 2003. Ara*:
As already discussed, D* Lite has its inherent shortcom- anytime a* with provable bounds on sub-optimality. Ad-
ings because the local and temporary nature of the informa- vances in Neural Information Processing Systems.
tion it owns. Without global information, it is impossible to Mills-Tettey, G.; Stentz, A.; and Dias, M. 2006. Ddˆ*
find a globally optimal solution. The DAD* Lite algorithm lite: Efficient incremental search with state dominance. In
presented here is a good start in the direction of obtaining Proceedings of the National Conference on Artificial Intel-
a globally optimal solution. Improving the candidate pool ligence, volume 21(2), 1032. Menlo Park, CA; Cambridge,
of the paths and development of better heuristics will likely MA; London; AAAI Press; MIT Press; 1999.
lead solutions close to global optimality.
Nasa. 2012. Spirit mars rover in ’mcmurdo’
panorama. http://marsrovers.jpl.nasa.gov/
References gallery/press/spirit/20121109a.html.
Hansen, E., and Zhou, R. 2007. Anytime heuristic search. Stentz, A. 1995. The focussed d* algorithm for real-time
Journal of Artificial Intelligence Research 28(1):267–297. replanning. In Proceedings of the International Joint Con-
Hart, P.; Nilsson, N.; and Raphael, B. 1968. A formal ba- ference on Artificial Intelligence, 1652–1659.
sis for the heuristic determination of minimum cost paths. Stentz, A. 1997. Optimal and efficient path planning for
Systems Science and Cybernetics, IEEE Transactions on partially-known environments. The Kluwer International
4(2):100–107. Series in Engineering and Computer Science 388:203–220.
Koenig, S., and Likhachev, M. 2001. Incremental a*. Ad- Yue, W., and Franco, J. 2009. Avoiding unnecessary cal-
vances in neural information processing systems 14:1539– culations in robot navigation. In Proceedings of World
1546. Congress on Engineering and Computer Science, 718–723.
Koenig, S., and Likhachev, M. 2002. D*lite. In Eighteenth Yue, W., and Franco, J. 2010. A new way to reduce com-
national conference on Artificial intelligence 2002, 476– puting in navigation algorithm. Journal of Engineering
483. Letters 18(4):EL 18 4 03.
Koenig, S., and Likhachev, M. 2005. Fast replanning for Yue, W.; Franco, J.; Cao, W.; and Yue, H. 2011. Id*
navigation in unknown terrain. Robotics, IEEE Transac- lite: improved d* lite algorithm. In Proceedings of the
tions on 21(3):354–363. 2011 ACM Symposium on Applied Computing, 1364–1369.
ACM.
Koenig, S.; Likhachev, M.; and Furcy, D. 2004. Lifelong
planning a*. Artificial Intelligence 155(1):93–146. Yue, W.; Franco, J.; Cao, W.; and Han, Q. 2012. A new
anytime dynamic navigation algorithm. In Proceedings of
Likhachev, M.; Ferguson, D.; Gordon, G.; Stentz, A.; and the World Congress on Engineering and Computer Science
Thrun, S. 2005. Anytime dynamic a*: An anytime, replan- 2012, WCECS 2012, volume 1, 17–22.
ning algorithm. In Proceedings of the International Con-