Understanding the differences between LPA* and D* Lite
An incremental version of A* which determines how to efficiently update a shortest path under changing edge costs when the start and end positions are static. The efficiency is achieved by only updating the values that need to be updated in order to find the shortest path.
Designed to be used by an agent traversing a graph under changing edge costs. Similar to LPA* except the start position is not static, it is the current position of the agent and thus always changing. This leads to the D* Lite algorithm having a couple of differences to LPA*, which are treated in detail below.
If the search is carried out from start to goal (i.e. the direction of search used in A* and LPA*; we’ll call this S-G) then all “start distances” (g values in the terminology of A* type algorithms) are invalidated every time the agent moves.
To remedy this, D* searches in the opposite direction (G-S) - expanding outwards from the goal (meaning the g values refer to distance from goal). This means, for example, if the agent observes a new wall that it didn’t see previously, the nodes which will need updating are those between it and the wall. In the S-G scenario, it is the nodes between the wall and the goal that will need updating, which are a) probably more numerous and b) likely unobserved and in need of future updates when further new walls are discovered
The priority of a node in the priority queue, which is based on the goal- and start-distances (g and h values) is invalid once the agent moves. For D* Lite’s G-S directed search this is because the previously calculated h values are now outdated. Some nodes will have a too-high-priority, because the agent has moved away from them and so their true “start distances”, or h values, have increased; and visa-versa for the nodes which are now closer to the agent. It is the nodes with a too-low-priority that are a real problem, as the nodes with a too-high-priority can simply be reinserted with their correct priority when encountered. Nodes with too-low-priority may not be processed at the correct time because even once the too-high-priority nodes are re-inserted with updated priorities, their updated (lower) priority may still be higher than the too-low-priority nodes’ apparent priority.
At first this might seem to mitigate the benefit of switching the direction of search, as the entire priority queue needs to be scanned and reordered. However, the authors use a method from the D* algorithm to circumvent this issue. The method exploits the following observation: if the queue-priority of all nodes in the priority queue is a lower-bound of its real queue-priority (NB. the highest priority node is the one with the lowest queue-priority value, so lower-bound here means “highest possible priority”), then, when processing a node from the queue, if its current queue-priority is the same as its true queue-priority it must be the highest priority node, since the next node at best is lower in priority.
How can this be exploited? As mentioned before, once the agent moves the queue-priority of all nodes is outdated. The key point is that the degree to which they are “off” from their true values is at most the heuristic distance between the current position of the agent and the position it was in the last time the queue-priorities were calculated (we’ll call this value hdelta). So to make the queue-priorities of all nodes in the queue a lower-bound of their real queue-priorities, we could subtract hdelta from the queue-priority of every node in the queue. But subtracting the same value from every element is a waste of computation, since the ordering of the queue when we are done will be identical. To not perform the subtraction, however, would result in new nodes inserted (with their up-to-date priorities) having a queue-priority value which is too low by hdelta. D* Lite solves this by adding a constant, km, to all newly calculated queue-priorities which is an accumulation of the hdelta values from previous steps.