Navigation algorithms have shown to be important in many practical applications. In an unknown or constantly changing environment, D* Lite, a classic dynamic algorithm, replans a shortest path in an efficient manner. However, if there are multiple shortest paths, the D* Lite algorithm arbitrarily selects one. When it comes to a density-unbalanced terrain, the shortest paths with the same cost may have different meaning. The algorithm performance largely depends on how crowded are the areas through which the selected shortest path traverses. In this paper, we propose the densityaware D* Lite algorithm, DAD* Lite, which is capable to take into account crowded areas and avoid them to find a (best) shortest path even when this has more detours than other shortest paths. Experiments show DAD* Lite improves D* Lite by giving better results on successful runs and moving distance.
Navigation algorithms, largely used to develop autonomous
vehicles, intelligent agents, etc, are an important area of
study in artificial intelligence. Under a dynamic
environment, knowledge of the terrain – initially partially known, or
unknown – is updated as the agent (for example, an
exploring planet rover, and vehicle parking) moves. Replanning
in dynamic circumstances is a very practical problem and
it is a key part of a navigation algorithm. D* Lite
The D* Lite algorithm seeks to find a minimum cost path from the start point to the goal point in the dynamic environment. Terrain information is modeled as an undirected graph G(V; E) with a start vertex vs and a goal vertex vg. An edge cost function, denoted by c(v; u), is associated to each directed edge (v; u), and the cost of a path is the sum of all the edge costs along that path. Determining the global minimum cost path from vs to vg is by no means trivial since the known environment information held by the agent may change unpredictably.
Copyright held by the authors.
When the environment is static, the well known A*
algorithm
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. Only vertices that are within sensor-radius from the current vertex are exactly in sight and the agent has accurate information on these vertices. Therefore, the agent knows only part of the terrain precisely, beyond which it holds old information, which might be out of date.
As the D* algorithm
D* Lite also uses the “more informed” rhs function to make better vertex updates during expansion. The rhs function in D* Lite is defined by rhs(v) = minv02succ(v) g(v0) + c(v; v0) v 6= vg 0 otherwise.
Three states are defined for a vertex v: the vertes is locally consistent if rhs(v) = g(v), locally overconsistent if rhs(v) < g(v), and locally underconsistent if rhs(v) > g(v). To generate the shortest path, D* Lite maintains the vertices in a priority queue with in ascending order of key values defined as min(g(v); rhs(v)) + h(vs; v).
Every time an inconsistent vertex is updated by making g(v) = rhs(v), the algorithm needs to check whether its neighbor becomes inconsistent. If this happens, this neighbor is added to the queue. D* Lite propagates calculations until all vertices on the path, including vs, are locally consistent. When selecting the shortest path, the agent moves to its neighbor vertex with the minimum of g-value plus the edge cost, which is the maximum-g-decrease-value. If the agent detects any changes that have been made since the last round, this makes these changed vertices inconsistent, and D* Lite adds them to the priority queue for possible update. Because D* Lite only updates partially inconsistent vertices, making (g; rhs) consistent instead of all vertices, it can perform much more efficient than the other navigation algorithms.
D* Lite has been improved by avoiding unneccessary
calculations in the case where the previous planned shortest
path is still available and considering the new changes
detected there is no better solution to replace this path
There are many other variants from D* Lite, which deal
with different constraints or requirements. For example,
DD* Lite
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 Density-Unbalanced Terrain describes DAD* Lite and motivation behind it. The experimental setup, results, and analysis are presented in Section Experiments. Finally, Section Conclusion and Future Work concludes the current study and presents future work.
D* Lite and all its variants conduct experiments on random
terrains. For example, each node on the grid world is
selected as a block with the same probability and all the
unblocked edges have equal cost. However, the real world
environments are much more complex for which the
assumption of an even-distribution terrain does not hold. Moreover,
these algorithms do not consider the information caused by
the unbalance, when, in fact, such information can help
develop a more efficient navigation algorithm. Fig. 1 is a Mars
panorama taken by Mars Exploration Rover
Density-unbalanced terrain can be illustrated in a grid world as shown in Fig. 2, where vi;j denotes the ith row and jth column vertex. Fig. 2 shows three shortest paths from vs = v3;3 to vg = v0;0. When the agent starts to move 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 of human beings, going to v2;3 is better, because this area is spacious while the bottom left side of the grid is more crowded. P ath1 may be blocked more in the future, and it does not have a detour. However, D* Lite makes decisions on the next move only depending on c(vs; v) + g(v), v 2 succ(vs), thus the agent has the same probability to go to the crowded area or the spacious area.
With the above observations, designing an algorithm able to select a shortest path in the most spacious region, thus avoiding crowded areas is an important problem. To solve 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 candidate 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 the shortest paths, will potentially avoid more interruptions and finally get to vg with the minimum overall cost. It may help to overcome the shortcomings of the D* Lite family algorithms due to the unpredictable future changes (dynamic environment) and the inaccurate information (limitation of the sensor radius): D* Lite only computes the shortest path based on local and temporary information which turns out not to be a globally optimal solution almost certainly. However we treat this non-trivial problem as our future work and in this paper, the proposed DAD* Lite algorithm considers only all the shortest paths as the candidate pool.
As a descendant of D* Lite, DAD* Lite uses the same
procedure to calculate shortest paths. D* Lite finds all the
shortest paths after calling ComputerShortestPath() shown
in the pseudocode of
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:
The heuristic value of a path is an accumulation of each vertex’s evaluation on this path, and DAD* Lite calculates the evaluation value of each vertex along the shortest paths. The evaluation value reflects the information of both the number of blocked neighbors from this vertex to the goal and the number of detours to the other shortest paths. The detailed computation of the evaluation value is shown next.
Fig. 3 and Fig. 4 illustrate the DAD* Lite pseudocode.
Since DAD* Lite is built on D* Lite only the new and
changed subroutines are shown; the omitted D* Lite
subroutines can be found in
In Fig. 3, firstly GetDAPath() initializes eval(v) for vertices which are visited in the last round of GetDAPath() computation. Then it calls GetDAPath(v). GetDAPath(v) is a reProcedure Initialize(): 01. U = ;; 02. km = 0; 03. for all v 2 V rhs(v) = g(v) = 1; eval(v) = 0; 04. rhs(vg) = 0; 05. eval(vg) = 1; 06. U.Insert(vg, CalcKey(vg)); Procedure GetDAPath(u) 01. if(u 6= vg) 02. for all v 2 succ(u) 03. if (rhs(u) = g(v) + c(u; v) && eval(v) = 0) 04. eval(u)+ =GetDAPath(v); 05. next(u) = argmaxv2succ(u)&&rhs(u)=g(v)+c(u;v)eval(v); 06. cnt = # of blocked v j v 2 pred(u); 07. eval(u) = eval(u)=2cnt; 08. return (eval(u)); Procedure GetDAPath() 01. for all visited v in last round except vg 02. eval(v) = 0; 03. GetDAPath(vs); cursive function, which computes eval(v) for each vertex v on the shortest paths. Lines 02-07 show how the heuristics are calculated. Lines 02-04 sum the eval(v) of u’s successors only if its successor v is on the shortest paths. This calculation gives higher value for the vertices with more detours. Line 05 chooses the vertex v which has the highest evaluation value from all u’s successors and saves it to next(u). In line 06, cnt counts the number of the blocked v in u’s predecessors. The larger cnt, the higher probability that a block will move to u and block the path from u to vg. Line 07 gives the formula of eval(u), which is is directly proportional to the sum of u’s on-the-shortest-path successors’ evaluation value, and is inversely proportional to two to the power of the number of blocks around u.
( 312 + 312 )=21 = 312 .
In Fig. 5(b), arrows indicate the vertex pointed to by next(v). Then next(v) always goes to the successor with the maximum eval. That is, next(vs) points to v2;3, because it has a larger eval (equal to 1218 ) than v3;2. It can be seen in Fig. 5(b) that the eval value has the capability to reflect directly how crowded a shortest path is.
In this section, DAD* Lite is compared with D* Lite on random grid terrains. The grid world is a 4-direction square terrain with size size vertices. All the experiments are carried out on the terrain with size = 200. vg = v(20;20) and vs = v(180;180). The sensor-radius is the observable distance from the agent’s current vertex. In every experiment, each vertex in the spacious area is randomly selected as blocked with some probability spacious-percentage, which higher for vertices in crowded areas, described by crowdedpercentage. To simulate the crowded areas, a number of squares, with a random side length from 30 to 50, are injected in the terrains. The total crowded areas sum up to 30% of the whole terrain area; different crowded areas overlap. Before every navigation, the agent has an old map, in which every obstacle is considered wrongly to be at its neighbor position with probability 0:5. As the agent moves, in each step, all the obstacles in the terrain have probability 0:5 to move to their neighbors excluding vs and vg.
In Fig. 6, the performance of D* Lite and DAD* Lite is compared along two aspects – successful runs and moving distance – with different crowded-percentage. Experiments of D* Lite and DAD* Lite, respectively, run 1000 times. In each experiment, navigation stops when the algorithm cannot find a single path from vs to vg and thus vg can never be reached. successful runs represents the number of experiments in which the agent reaches vg in the end. Among all the successful runs, moving distance measures the average distance that the agent moves from vs to vg. Compared to the other D* Lite family algorithms experiments, where the emphasis is mostly on running time and heap operation, successful runs and moving distance reflect a more global point of view.
1000
In Fig. 6(a), DAD* Lite shows better results in successful runs than D* Lite. This benefit reaches the maximum at crowded-percentage = 0:3. When crowded-percentage is small, the terrain is actually rather spacious, with small crowded areas, so the advantage of DAD* Lite is not obvious. As crowded-percentage increases, the crowded areas have more obstacles. If a shortest path exists, D* Lite picks up one arbitrarily. If this shortest path goes through crowded areas, the probability that the agent is trapped in one of these increases. Therefore, DAD* Lite outperforms D* Lite in this situation. As crowded-percentage increases, fewer and fewer paths can pass through the crowded areas, so the shortest paths through the crowded areas account for a small proportion among all the shortest paths and therefore, it becomes easy for D* Lite to select a path avoiding crowded areas. This explains why DAD* Lite gains less in successful runs when crowded-percentage = 0:4.
In Fig. 6(b), DAD* Lite has shorter moving distance than D* Lite. Because the benchmark used is random and the terrain block density is still small, if the planned shortest path is interrupted, it is easier for the algorithm to find an alternative shortest path with the same distance as the old one, and hence, for both DAD* Lite and D* Lite, the moving distance is not big. However, it should be noticed that since
In Fig. 7, two algorithms are compared with different sensor-radius. Fig. 7(a) shows that the number of successful runs decreases with sensor-radius for both DAD* Lite and D*. However, compared to D* Lite, DAD* Lite is less affected by the change of sensor-radius. More importantly, it can be seen that DAD* Lite with sensor-radius = 2 shows the similar result to D* Lite with sensor-radius = 20. In other words, in the same environment, the result of using DAD* Lite is equal to that of using D* Lite with a 10 sensor-radius. Fig. 7(b) shows the improvement of DAD* Lite with respect to the moving distance. ) s ndo 500 c ise 400 lil m i(em 300
T 650 )s 600 d con 500 e lils 400 i m ( iem 300 T
D* Lite
200 DAD* Lite
0.1 0.15 0.2
spacious percentage
= crowded percentage
(c) sensor-radius = 10
vs = v(180;180) and vg = v(20;20), the cost of the possible
shortest path is 320. In Fig. 6(b) the values for moving
distance produced by DAD* Lite are all closed to 320, which
shows that the benefit of DAD* Lite with respcet to the
moving distance is relatively stable.
Similarly, ID* Lite
In Fig. 9(a), the difference between two algorithms reaches the minimum point at crowded-percentage = 0:3, because DAD* Lite saves more moving distance than D* Lite as shown in Fig. 6(b). In Fig. 9(c), the biggest difference between the two algorithms comes when block percentage = 0:1. That is, when the terrain becomes more spacious, there are more shortest paths, therefore GetDAPath() needs to expand more vertices and thus, it consumes more time.
This study proposed DAD* Lite, the Density-Aware D* Lite algorithm. Compared to D* Lite selecting a shortest path arbitrarily, DAD* Lite finds a shortest path which may have more detours than other shortest paths and avoid the crowded areas. From a global point of view, by using a heuristic to quantify how crowded an area is, DAD* Lite produces better results than D* Lite. This improvement is reflected experimentally in the values of successful runs and moving distance.
From the experimental results, DAD* Lite consumes more time than D* Lite, which is determined by the structure of the algorithm. Future work will set a threshold on running time of GetDAPath() or a threshold on the number of the shortest paths to search in GetDAPath() to prune the search tree. Furthermore, the option of embedding DAD* Lite heuristic with ID* Lite, in order to shorten computation time, will also be explored. However, for a system that does not have a strict time limit, and when crowded areas are an important issue (e.g., the agent may be damaged if traveling in such areas), DAD* Lite will always have a higher chance to reach vg successfully on the shorter path (i.e., moving less distance).
As already discussed, D* Lite has its inherent shortcomings because the local and temporary nature of the information it owns. Without global information, it is impossible to find a globally optimal solution. The DAD* Lite algorithm presented here is a good start in the direction of obtaining a globally optimal solution. Improving the candidate pool of the paths and development of better heuristics will likely lead solutions close to global optimality.