Lifelong Planning A* (LPA*), in depth: local consistency, the key and stop rule, a traced replan, tested code and measured costs against repeated A*

Two estimates and local consistency

Plain A* keeps one number per vertex, g(s), the cost of the best path found so far from the start. LPA* adds a second, the one-step lookahead rhs(s):

rhs(start) = 0
rhs(s)     = min over predecessors p of ( g(p) + c(p, s) )

The rhs value is what g(s) should be, given the current g values of its predecessors. A vertex is locally consistent when the two agree. If every vertex is locally consistent, then every g value satisfies the Bellman equations g(s) = min_p g(p) + c(p, s) with g(start) = 0, and with positive edge costs the unique solution of those equations is the true shortest-path distance. That is the whole correctness argument in one line: consistency everywhere means exact distances.

An edge change can only break consistency at the edge's head: changing c(u, v) changes rhs(v) and nothing else. LPA* recomputes that rhs, notices g(v) != rhs(v), and puts v on a priority queue. Repair spreads outward from there, and only as far as distances actually change.

There are two kinds of inconsistency. A vertex is overconsistent when g > rhs: a cheaper path appeared, and the fix is to lower g to rhs, exactly like an A* expansion. It is underconsistent when g < rhs: the path it relied on became more expensive. The fix is to set g to infinity, which makes the vertex overconsistent or consistent, and to notify its successors, which may have depended on it. An underconsistent vertex is therefore usually expanded twice: once to forget, once to settle at its new value. The paper proves no vertex is expanded more than twice per search when the heuristic is consistent.

Keys and the stopping rule

Repairs must happen in the right order, so the queue is sorted by a two-part key compared lexicographically:

key(s) = [ min(g(s), rhs(s)) + h(s) ,  min(g(s), rhs(s)) ]

The first component is A*'s f value, using the smaller of the two estimates so that an underconsistent vertex is processed early enough to retract its stale value before anything builds on it. The second breaks ties toward vertices nearer the start. The search stops when the goal is consistent and no queued key is smaller than the goal's key: at that point no remaining inconsistency can lower the goal's distance. The heuristic h must estimate distance to the goal and be consistent, h(goal) = 0 and h(s) <= c(s, t) + h(t); with an inconsistent heuristic the expansion bound above no longer holds. With h set to zero, LPA* is closely related to the incremental algorithm DynamicSWSF-FP (Ramalingam and Reps, 1996).

A complete implementation

The implementation below is complete and is exactly the code that produced every number in this article. The graph is passed in as functions, so the same class handles grids, road graphs or anything else. The priority queue uses lazy deletion: inq records each queued vertex's current key, and heap entries whose key no longer matches are discarded when they reach the top.

import heapq, math, random

INF = math.inf

class LPAStar:
    def __init__(self, succ, pred, cost, h, start, goal):
        self.succ, self.pred, self.cost, self.h = succ, pred, cost, h
        self.start, self.goal = start, goal
        self.g, self.rhs = {}, {start: 0.0}
        self.heap, self.inq = [], {}
        self.expansions = 0
        self._push(start)

    def G(self, s): return self.g.get(s, INF)
    def RHS(self, s): return self.rhs.get(s, INF)

    def key(self, s):
        m = min(self.G(s), self.RHS(s))
        return (m + self.h(s), m)

    def _push(self, s):
        k = self.key(s)
        self.inq[s] = k
        heapq.heappush(self.heap, (k, s))

    def _top(self):
        while self.heap and self.inq.get(self.heap[0][1]) != self.heap[0][0]:
            heapq.heappop(self.heap)          # lazy deletion of stale entries
        return self.heap[0] if self.heap else ((INF, INF), None)

    def update_vertex(self, s):
        if s != self.start:
            self.rhs[s] = min((self.G(p) + self.cost(p, s) for p in self.pred(s)), default=INF)
        self.inq.pop(s, None)
        if self.G(s) != self.RHS(s):
            self._push(s)

    def compute_shortest_path(self):
        while True:
            k, s = self._top()
            if not (k < self.key(self.goal) or self.RHS(self.goal) != self.G(self.goal)):
                return self.G(self.goal)
            heapq.heappop(self.heap); del self.inq[s]
            self.expansions += 1
            if self.G(s) > self.RHS(s):         # overconsistent: lock in the lower value
                self.g[s] = self.RHS(s)
                for t in self.succ(s): self.update_vertex(t)
            else:                               # underconsistent: forget, then re-derive
                self.g[s] = INF
                self.update_vertex(s)
                for t in self.succ(s): self.update_vertex(t)

    def edge_changed(self, u, v):
        self.update_vertex(v)                   # cost(u, v) has already changed

    def path(self):
        if self.G(self.goal) == INF: return None
        s, out = self.goal, [self.goal]
        while s != self.start:
            s = min(self.pred(s), key=lambda p: self.G(p) + self.cost(p, s))
            out.append(s)
        return out[::-1]

Usage is two calls. Call compute_shortest_path() once for the initial plan. After costs change, update your cost function first, then call edge_changed(u, v) for every changed edge, then call compute_shortest_path() again. On a grid, blocking a cell changes every edge into and out of it, so call edge_changed in both directions for each neighbour. The returned value is the goal's distance; path() walks back from the goal along predecessors that achieve the minimum.

Worked example: one edge gets more expensive

Take the five-vertex graph in the figure with a consistent heuristic. The first call behaves exactly as A* does: it expands S, A, B, C and G once each, all overconsistent, and finds S-A-B-C-G with cost 7. Every vertex ends consistent with g = rhs: S 0, A 1, B 3, C 4, G 7.

Now the edge B->C rises from 1 to 6. edge_changed('B', 'C') recomputes rhs(C) = min(g(A) + 5, g(B) + 6) = min(6, 9) = 6. Since g(C) = 4, C is underconsistent and is queued with key [4 + 2, 4] = [6, 4]. The second call then does four expansions:

The new path is S-A-C-G with cost 9. S, A and B were never touched, because their distances did not change. C and G were each expanded twice, once to forget and once to settle, which is the at-most-twice bound in action. A fresh A* would have expanded all five again. On a five-vertex graph that saving is trivial; on a 40,000-cell grid it is the whole point.

Measured against repeated A*

The benchmark used 4-connected grids with 25 percent random obstacles, unit costs, a Manhattan heuristic, the start in one corner and the goal in the opposite one. Each row is the mean over 200 replans. One change blocks a free cell and frees a blocked cell, so obstacle density stays constant; changes were drawn from the whole grid, from the quarter-side square at the start corner, or from the one at the goal corner. After each replan the result was checked against a fresh A* on the same grid; they always agreed. Expansions are the portable measure; milliseconds are from CPython 3.13 on one laptop and only meaningful relative to each other.

The first search expanded exactly as many vertices as A* (1,703 on the small grid, 12,433 on the large one), as the theory predicts. Three patterns stand out. Most changes are irrelevant: a cell far from the current search tree changes no distance and costs almost nothing. Location matters: a change near the start invalidates the g values of everything downstream of it, so the repair is large, while a change near the goal affects only a few vertices. And an LPA* expansion is several times more expensive than an A* expansion, because update_vertex rescans predecessors and churns the heap. In the fourth row LPA* did a quarter of the expansions and still took twice as long. A few replans in the start-corner rows had no path at all; they are included.

When to use LPA*, and when not

The measurements give the selection rule. Use LPA* when the start and goal are fixed, changes are few per replan and tend to fall far from the start. If the changes cluster near the start, which is exactly the situation of a robot sensing obstacles around itself, search in the other direction: run LPA* from the goal to the start, so changes near the robot fall at the far end of the search, where few vertices depend on them. That is D* Lite, which also handles a start that moves; it is covered in D* / D* Lite, in depth. If many edges change at once, count them and fall back to a fresh A* above a threshold you measure; a fresh search also resets any memory the incremental structures have accumulated. When nothing changes between queries, plain A* with a strong heuristic is simpler and faster, as shown in A* Search Deep Dive.

Failure modes

• Notifying before updating the cost. edge_changed reads the cost function, so it must see the new cost. Calling it first silently keeps the old value.
• Missing an edge. Blocking a grid cell changes up to eight directed edges on a 4-connected grid. Forget the outgoing ones and successors keep stale rhs values.
• Changing the goal. Keys include h toward the goal. A new goal changes every key; start a new search, or use D* Lite's key modifier if the start is what moves.
• Inconsistent heuristics. The paper's correctness and expansion results assume a consistent heuristic; without one, neither is guaranteed. Use a consistent h.
• Floating-point equality. The consistency test compares g and rhs exactly. Costs built from sums of floats can differ in the last bit and requeue vertices forever. Use integer costs or round to a fixed resolution.
• Unbounded memory. g and rhs are kept for every vertex ever touched. On a huge map that runs for days, bound the region or restart periodically.

What to do next

1. Copy the class above, run it on the five-vertex example and reproduce the four-step trace.
2. Wire it to your own graph with the cost function as the single source of truth, and add a test that compares every replan with a fresh A*, as the benchmark did.
3. Log where your changes occur relative to the start; if they cluster near it, switch to a backward search (D* Lite).
4. Measure expansions and wall-clock per replan against fresh A* on your real change pattern, and set a fall-back threshold from that measurement.
5. Use integer or fixed-resolution costs before the first production run.
6. Read A* Variants, in depth to compare LPA* with anytime and bidirectional alternatives, and Dijkstra's Algorithm, in depth for the zero-heuristic baseline.