D*, D* Lite & LPA*
D-Star (š·*), short for dynamic A* is a sensor based algorithm that deals with dynamic obstacles by real time changing its edgeās weights. It always computes a shortest path from its current cell to the start cell under the assumption that cells with unknown blockage status are traversable. D* maintains a list of nodes which is used to propagate information about changes of the cost function.
Algorithm
The algorithm works by iteratively selecting a node from the OPEN list and evaluating it. D* begins by searching backwards from the goal node towards the start node. Each expanded node has a back pointer which refers to the next node leading to the target, and each node knows the exact cost to the target.
Obstacle Handling
When an obstruction is detected along the intended path, all the points that are affected are again placed on the OPEN list, this time marked RAISE. Before a RAISED node increases in cost, however, the algorithm checks its neighbors and examines whether it can reduce the nodeās cost. If not, the RAISE state is propagated to all of the nodesā descendants, that is, nodes which have back pointers to it. These nodes are then evaluated, and the RAISE state is passed on, forming a wave. When a RAISED node can be reduced, its back pointer is updated, and passes the LOWER state to its neighbors. These waves of RAISE and LOWER states are the heart of D*.
Lifelong Planning A*
Lifelong planning A* popularly known as LPA*, is an incremental version of A*, which can adapt to changes in the graph without recalculating the entire graph, by updating the g-values (distance from start) from the previous search during the current search to correct them when necessary. It reuse the information from previous runs to drastically reduce the number of nodes which need to be examined, compared to A* by updating only the g-values that are relevant for computing a shortest path.
LPA* Trick
LPA* uses a clever trick to adapt costs. The current node asks its neighbors: You know me best, do you think Iām being realistic about myself? Specifically, it asks this about its g value, which is the known cost of getting from the initial node to itself i.e. the current node. Neighbors look at their own g, look at where the current node is in relation to them, and then offer an estimate of what they think its cost should be. The minimum of these offers is set as the current nodeās rhs-value which is then used to update its g value
Start Distance Estimates
LPA* maintains two estimates of the start distance g*(n) for each node:
- g(n), the previously calculated g-value (start distance) as in A*
- rhs(n), a look-ahead value based on the g-values of the nodeās predecessors (the minimum of all g(nā ) + d(nā , n), where nā is a predecessor of n and d(x, y) is the cost of the edge connecting x and y)
For the start node, the following always holds true: r h s ( s t a r t ) = g ( s t a r t ) = 0 {\displaystyle rhs(start)=g(start)=0}
If rhs(n) equals g(n), then n is called locally consistent. However, when edge costs change, local consistency needs to be re-established only for those nodes which are relevant for the route.
Priority Queue
When a node becomes locally inconsistent (because the cost of its predecessor or the edge linking it to a predecessor has changed), it is placed in a priority queue for re-evaluation. The priority of a vertex in the priority queue is always the same as its key, which is a vector with two components k(s) = [k1(s), k2(s)], where k1(s) = min{g(s), rhs(s)} + h(s,sgoal) and k2(s) = min{g(s), rhs(s). Entries are ordered by k1 (which corresponds directly to the f-values used in A*), then by k2.
The first component of keys used by A* correspond directly to f-value because both the g-values and rhs values of LPA* correspond to the g-values of A* and the h-values of LPA* correspond to the h-values of A*. The second component of the keys correspond to the g-value of A*.
Node Expansion
The top node in the queue is expanded as follows:
- If the rhs-value of a node equals its g-value, the node is locally consistent and is removed from the queue.
- If the rhs-value of a node is less than its g-value (known as a locally overconsistent node), the g-value is changed to match the rhs-value, making the node locally consistent. The node is then removed from the queue.
- If the rhs-value of a node is greater than its g-value (known as a locally underconsistent node), the g-value is set to infinity (which makes the node either locally overconsistent or locally consistent). If the node is then locally consistent, it is removed from the queue, else its key is updated.
Expansion of nodes continues with the next node at the top of the queue until two conditions are met:
- The goal is locally consistent, and
- The node at the top of the priority queue has a key which is greater than or equal to the key for the goal.
Initial Run
The graph is initialized by setting the rhs-value of the start node to 0 and its g-value to infinity. For all other nodes, both the g-value and the rhs-value are assumed to be infinity until assigned otherwise. This initially makes the start node the only locally inconsistent node, and thus the only node in the queue.
Cost Changes
When the cost of an edge changes, LPA* examines all nodes affected by the change, i.e. all nodes at which one of the changed edges terminates
- The rhs-values of the nodes are updated.
- Nodes which have become locally consistent are removed from the queue.
- Nodes which have become locally inconsistent are added to the queue.
Finding the Shortest Path
- Start at the goal.
- Move to the predecessor nā of the current node n for which g(nā ) + d(nā , n) is lowest (if the lowest score is shared by multiple nodes, each is a valid solution and any of them can be chosen arbitrarily).
- Repeat the previous step until you have reached the start.
D* Lite
D* Lite is not based on the original D*, but implements the same behavior. It is simpler to understand and can be implemented in fewer lines of code, hence the name āD* Liteā. D* Lite is an incremental heuristic search algorithm which is based on Lifelong Planning A*, it has completely obsoleted D*. Thus, there is never any reason to use D*; use D*-Lite instead.
Incremental heuristic search methods use heuristics to focus their search and reuse information from previous searches to ļ¬nd solutions to series of similar search tasks much faster than is possible by solving each search task from scratch
Search Direction
We ļ¬rst need to switch the search direction of LPA*. LPA* searches from the start vertex to the goal vertex and thus its g-values are estimates of the start distances. D* Lite searches from the goal vertex to the start vertex and thus its g-values are estimates of the goal distances. It is derived from LPA* by exchanging the start and goal vertex and reversing all edges in the pseudo code.
Changed Edge cost
In case of changed edge cost, it recalculates a shortest path from its current cell to the goal cell by recalculating only those goal distances that have changed (or have not been calculated before) and are relevant for recalculating the shortest path. It thus calculates only the g-values of those vertices that are important to determine a shortest path.
The big caveat is that the location of changed edge cost with respect to the goal location makes an enormous difference to the efficiency of the algorithms. When the changed cost information is close to the perimeter of the expanding search front (the āvisitedā region), few paths have to change, and the incremental updates are fast.
When the changed cost information is close to the goal of the search (or your scenario sees the goal change locations, not just the start), these algorithms suffer catastrophic slowdown. In this scenario, almost all the saved information needs to be updated, because the changed region is so close to the goal that almost all pre-calculated paths pass through the changes and must be re-evaluated. Due to the overhead of storing extra information and calculations to do incremental updates, a re-evaluation on this scale is slower than a fresh start.
D* vs D* Lite: First of all, D*-Lite is considered much simpler than D*, and since it always runs at least as fast as D*, it has completely obsoleted D*.
D* Lite vs A*: The D* Lite algorithm works by basically running A* search in reverse starting from the goal and attempting to work back to the start. As opposed to repeated A* search, the D* Lite algorithm avoids replanning from scratch and incrementally repair path.
LPA* VS D*Lite: Basically, in LPA*, the search begin at start position and the direction of search is from start configuration to goal configuration. In D* Lite, everything goes conversely. The search begin at the Goal position and the direction of search is from goal configuration to start configuration.
The pseudo code of D* Lite and LPA* are completely similar only the edge cost changes and the direction of search is reversed. The termination condition is reversed ad the predecessor and successors are interchanged. Following is the pseudo code of D* Lite:
D* Lite Algorithm
