LPA* or Lifelong Planning A* is an incremental heuristic search algorithm based on A*. It was first described by Sven Koenig and Maxim Likhachev in 2001.
Description 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. Like A*, LPA* uses a heuristic, which is a lower boundary for the cost of the path from a given node to the goal. A heuristic is admissible if it is guaranteed to be non-negative (zero being admissible) and never greater than the cost of the cheapest path to the goal.
Predecessors and successors With the exception of the start and goal node, each node n has predecessors and successors:
Any node from which an edge leads towards n is a predecessor of n. Any node to which an edge leads from n is a successor of n. In the following description, these two terms refer only to the immediate predecessors and successors, not to predecessors of predecessors or successors of successors.
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 lookahead 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. If all nodes are locally consistent, then a shortest path can be determined as with A*. 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. LPA* uses a two-dimensional key:
k ( n ) = [ k 1 ( n ) k 2 ( n ) ] = [ min ( g ( n ) , r h s ( n ) ) + h ( n , g o a l ) min ( g ( n ) , r h s ( n ) ) ] {\displaystyle k(n)={\begin{bmatrix}k_{1}(n)\\k_{2}(n)\\\end{bmatrix}}={\begin{bmatrix}\min(g(n),rhs(n))+h(n,goal)\\\min(g(n),rhs(n))\\\end{bmatrix}}}
Entries are ordered by k1 (which corresponds directly to the f-values used in A*), then by k2.
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. Since changing the g-value of a node may also change the rhs-values of its successors (and thus their local consistence), they are evaluated and their queue membership and key is updated if necessary. 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. After that, node expansion begins. The first run of LPA* thus behaves in the same manner as A*, expanding the same nodes in the same order.
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 (if an edge can be traversed in both directions and the change affects both directions, both nodes connected by the edge are examined):
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. Nodes which remain locally inconsistent have their keys updated. After that, node expansion resumes until the end condition has been reached.
… excerpt ends here. Continue reading the full article.
