Lifelong Planning A*


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 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 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 has predecessors and successors:
  • Any node from which an edge leads towards is a predecessor of.
  • Any node to which an edge leads from is a successor of.
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 for each node:
  • , the previously calculated g-value as in A*
  • , a lookahead value based on the g-values of the node's predecessors
For the start node, the following always holds true:
If equals, then 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, it is placed in a priority queue for re-evaluation. LPA* uses a two-dimensional key:
Entries are ordered by, then by.

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, 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, the g-value is set to infinity. 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, 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:

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 :
  • 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.

Finding the shortest path

Once node expansion has finished, the shortest path is evaluated. If the cost for the goal equals infinity, there is no finite-cost path from start to goal. Otherwise, the shortest path can be determined by moving backwards:
  • Start at the goal.
  • Move to the predecessor of the current node for which is lowest.
  • Repeat the previous step until you have reached the start.

Pseudocode

This code assumes a priority queue queue, which supports the following operations:topKey returns the lowest priority of any node in the queue pop removes the node with the lowest priority from the queue and returns itinsert inserts a node with a given priority into the queueremove removes a node from the queuecontains returns true if the queue contains the specified node, false if not

void main
void initialize
/** Expands the nodes in the priority queue. */
void computeShortestPath
/** Recalculates rhs for a node and removes it from the queue.
* If the node has become locally inconsistent, it is inserted into the queue with its new key. */
void updateNode
int calculateKey

Properties

Being algorithmically similar to A*, LPA* shares many of its properties.
  • Each node is expanded at most twice for each run of LPA*. Locally overconsistent nodes are expanded at most once per LPA* run, thus its initial run has similar performance to A*, which visits each node at most once.
  • The keys of the nodes expanded for each run are monotonically nondecreasing over time, as is the case with A*.
  • The more informed the heuristics are, the fewer nodes need to be expanded.
  • The priority queue implementation has a significant impact on performance, as in A*. Using a Fibonacci heap can lead to a significant performance increase over less efficient implementations.
For an A* implementation which breaks ties between two nodes with equal f-values in favor of the node with the smaller g-value, the following statements are also true:
  • The order in which locally overconsistent nodes are expanded is identical to A*.
  • Of all locally overconsistent nodes, only those whose cost does not exceed that of the goal need to be expanded, as is the case in A*.
LPA* additionally has the following properties:
  • When edge costs change, LPA* outperforms A* as only a fraction of nodes need to be expanded again.

Variants

  • D* Lite, a reimplementation of the D* algorithm based on LPA*