LPA* or Lifelong Planning A* is an incremental heuristic search algorithm based on A*.
Like A*, LPA* uses a heuristic, which is a lower boundary for the cost of the path from a given node to the goal.
However, when edge costs change, local consistency needs to be re-established only for those nodes which are relevant for the route.
LPA* uses a two-dimensional key: Entries are ordered by k1 (which corresponds directly to the f-values used in A*), then by k2.
Once node expansion has finished (i.e. the exit conditions are met), the shortest path is evaluated.