A* is optimal and, with a consistent heuristic, expands no node more than once. That is a strong guarantee, and in practice it breaks on four kinds of problem: the open and closed sets do not fit in memory, a uniform grid creates thousands of equivalent paths, a caller needs some answer before the optimal one is ready, or the map changes while an agent is following the path. Each A* variant is a targeted change to one part of the algorithm that relaxes exactly one of those limits.
This article implements the variants you are most likely to need, IDA*, bidirectional A*, jump point search, ARA* and D* Lite, and states the condition each one needs to stay correct. It assumes you know plain A*; the A* pathfinding article covers the base algorithm, admissible and consistent heuristics, tie-breaking and weighted A*.
What each variant changes
Every variant keeps the same evaluation, f(n) = g(n) + h(n), and changes what is stored, which nodes are generated, or how much work is reused.
| Variant | What it changes | Optimal? | Needs |
|---|---|---|---|
| Weighted A* | f = g + w h with w > 1 | Within factor w | Admissible h |
| IDA* | No open list; depth-first with an f threshold | Yes | Admissible h, cheap node generation |
| Bidirectional A* | Two searches, start forward and goal backward | Yes, with the right stop rule | Reverse edges, heuristics to both ends |
| Jump point search | Generates only jump points on a grid | Yes | Uniform-cost grid, fixed movement rules |
| ARA* | Weighted A* repeated with falling w, reusing work | Bound improves to optimal | Admissible h |
| D* Lite | Searches goal to start and repairs after edge changes | Yes, for the current map | Consistent h, reverse edges |
IDA*: A* in linear memory
IDA* (Korf, 1985) runs depth-first searches that prune any node whose f exceeds a threshold. The first threshold is h(start). Each failed iteration returns the smallest f that exceeded the threshold, and that becomes the next one. Memory is proportional to the path depth, because only the current path is stored.
def ida_star(start, goal, h, neighbors):
path = [start]
on_path = {start}
bound = h(start)
def dfs(node, g, bound):
f = g + h(node)
if f > bound:
return f, False
if node == goal:
return f, True
smallest = float("inf")
for nxt, cost in neighbors(node):
if nxt in on_path: # cycle check on the current path only
continue
path.append(nxt); on_path.add(nxt)
t, found = dfs(nxt, g + cost, bound)
if found:
return t, True
smallest = min(smallest, t)
path.pop(); on_path.discard(nxt)
return smallest, False
while True:
t, found = dfs(start, 0, bound)
if found:
return path, t
if t == float("inf"):
return None, None # no path exists
bound = tThe cost is repeated work. Each iteration re-expands everything from the previous one, which is cheap when f values come in a few distinct levels (the 15-puzzle with unit moves and Manhattan distance) and ruinous when every path has a different real-valued cost, because each iteration then admits only one new node. IDA* also has no duplicate detection beyond the current path, so on graphs with many routes to the same state it re-explores them. Use it on tree-like puzzle spaces with integer costs. On road graphs or grids with real weights, use A* with a memory budget instead.
Bidirectional A* and the stop rule
Bidirectional A* runs a forward search from the start with h_F estimating distance to the goal and a backward search from the goal over reversed edges with h_B estimating distance to the start. When a node has been reached by both, g_F(n) + g_B(n) is the cost of a real path. Keep the best such cost in mu.
The classic bug is stopping the moment the two searches touch. The first meeting point is usually not on the shortest path. A correct stop rule for admissible heuristics is: stop when mu is no larger than the larger of the two frontiers' minimum f values. Any path cheaper than mu would have to pass through an open node in each frontier with f at most its cost, so once both minimums reach mu, no cheaper path remains.
import heapq
def bidirectional_astar(start, goal, succ, pred, hF, hB):
gF, gB = {start: 0}, {goal: 0}
openF, openB = [(hF(start), start)], [(hB(goal), goal)]
mu, meet = float("inf"), None
while openF and openB:
if mu <= max(openF[0][0], openB[0][0]): # the stop rule
return mu, meet
# expand the side with the smaller frontier
if len(openF) <= len(openB):
g, other, opn, nbrs, h = gF, gB, openF, succ, hF
else:
g, other, opn, nbrs, h = gB, gF, openB, pred, hB
f, u = heapq.heappop(opn)
if f > g[u] + h(u):
continue # stale heap entry
for v, cost in nbrs(u):
ng = g[u] + cost
if ng < g.get(v, float("inf")):
g[v] = ng
heapq.heappush(opn, (ng + h(v), v))
if v in other and ng + other[v] < mu:
mu, meet = ng + other[v], v
return mu, meetReconstruct the path by following forward parents from meet to start and backward parents from meet to goal (parent maps are omitted above for brevity). Bidirectional A* often expands more nodes than plain A* when the heuristic is good, because the two searches overlap before the stop rule fires. It earns its keep with weak heuristics, on road networks where Dijkstra-like searches meet in the middle, and as the base of algorithms such as MM (Holte and colleagues, 2016) that guarantee the frontiers meet in the middle.
Jump point search on uniform grids
On an 8-connected grid with uniform cost, many different move sequences reach the same cell at the same cost. A* adds all of them to the open list. Jump point search (Harabor and Grastien, 2011) keeps moving in a straight or diagonal line from a node until it finds a node where the optimal path might turn, called a jump point, and only adds those. It is still optimal on uniform-cost grids, often with far fewer heap operations.
The rules depend on whether diagonal moves may cut past a blocked corner, and many bugs come from mixing rules. Below is the jump function for the common variant that forbids diagonal moves when either orthogonal neighbour is blocked:
def jump(grid, x, y, dx, dy, goal):
# returns the next jump point reached by moving (dx, dy) from (x-dx, y-dy), or None
# recursion depth = run length; convert to a loop on large grids
if not grid.walkable(x, y):
return None
if (x, y) == goal:
return (x, y)
if dx and dy: # diagonal move
if jump(grid, x + dx, y, dx, 0, goal) or jump(grid, x, y + dy, 0, dy, goal):
return (x, y)
if grid.walkable(x + dx, y) and grid.walkable(x, y + dy):
return jump(grid, x + dx, y + dy, dx, dy, goal)
return None
if dx: # horizontal: look for a forced turn
if (grid.walkable(x, y - 1) and not grid.walkable(x - dx, y - 1)) or \
(grid.walkable(x, y + 1) and not grid.walkable(x - dx, y + 1)):
return (x, y)
else: # vertical
if (grid.walkable(x - 1, y) and not grid.walkable(x - 1, y - dy)) or \
(grid.walkable(x + 1, y) and not grid.walkable(x + 1, y - dy)):
return (x, y)
return jump(grid, x + dx, y + dy, dx, dy, goal)The surrounding A* is unchanged except that successors of a node are the jump points found in its pruned directions, and g increases by the octile distance travelled. The neighbour-pruning rules for a node must match the jump rules exactly; test against plain A* on random maps and compare costs. JPS does not apply to weighted terrain; for that, plain A* or preprocessing such as hierarchical pathfinding is the right tool.
ARA*: anytime search with a bound
ARA* (Likhachev, Gordon and Thrun, 2003) runs weighted A* with a large weight to get a path fast, then lowers the weight and improves the path, reusing everything already computed. It can be stopped at any time with a solution and a known bound on how far it is from optimal.
The reuse is the clever part. During one iteration, a node already expanded in this iteration (in CLOSED) is not reopened when its g improves; it goes to an INCONS list instead. When the weight drops, OPEN and INCONS are merged and re-keyed with the new weight, and CLOSED is cleared.
key(s) = g(s) + eps * h(s)
improve_path():
while key(goal) > min key over OPEN:
s = OPEN.pop_min(); CLOSED.add(s)
for s2 in succ(s):
if g(s2) > g(s) + c(s, s2):
g(s2) = g(s) + c(s, s2); parent(s2) = s
if s2 not in CLOSED: OPEN.insert_or_update(s2, key(s2))
else: INCONS.add(s2)
ara_star(eps0, step):
g(start) = 0; g(others) = inf; eps = eps0
OPEN = {start}; CLOSED = {}; INCONS = {}
improve_path(); publish(path, bound(eps))
while bound(eps) > 1 and time remains:
eps = max(1, eps - step)
OPEN = OPEN + INCONS; INCONS = {}; rekey OPEN with new eps; CLOSED = {}
improve_path(); publish(path, bound(eps))
bound(eps) = min(eps, g(goal) / min over OPEN + INCONS of (g(s) + h(s)))The published bound is what makes ARA* usable in a planner with a deadline: the caller knows the current path is at most bound times the optimal cost. Pick eps0 by measuring time to first solution on representative queries, and keep step small enough that each iteration has a chance to finish before the deadline.
D* Lite: repair instead of replan
A robot that discovers a new obstacle should not plan from scratch. D* Lite (Koenig and Likhachev, 2002) searches backwards from the goal, so the g values it keeps are distances to the goal and stay valid as the robot moves. Each node has g and a one-step lookahead rhs; a node whose g differs from rhs is inconsistent and sits in the priority queue. When an edge cost changes, only nodes near the change become inconsistent and are repaired.
key(s) = [min(g(s), rhs(s)) + h(s_start, s) + k_m, min(g(s), rhs(s))] # compared lexicographically
update_vertex(u):
if u != goal: rhs(u) = min over s2 in succ(u) of c(u, s2) + g(s2)
remove u from U if present
if g(u) != rhs(u): U.insert(u, key(u))
compute_shortest_path():
while U.top_key() < key(s_start) or rhs(s_start) != g(s_start):
k_old = U.top_key(); u = U.pop()
if k_old < key(u): U.insert(u, key(u)) # key grew because k_m grew
elif g(u) > rhs(u): g(u) = rhs(u); for s in pred(u): update_vertex(s)
else: g(u) = inf; for s in pred(u) + [u]: update_vertex(s)
main():
k_m = 0; g = rhs = inf everywhere; rhs(goal) = 0; U.insert(goal, key(goal))
s_last = s_start; compute_shortest_path()
while s_start != goal:
s_start = argmin over s2 in succ(s_start) of c(s_start, s2) + g(s2); move there
if edge costs changed:
k_m += h(s_last, s_start); s_last = s_start
for each changed edge (u, v): update its cost; update_vertex(u)
compute_shortest_path()The k_m term is the subtle part: the heuristic is measured from the robot's current position, which moves, so instead of re-keying the whole queue D* Lite adds the distance moved to every new key. If g(s_start) is infinite after a repair, there is no path on the current map.
Worked example: a warehouse robot
A warehouse robot plans on a 1,000 by 1,000 occupancy grid with uniform move costs, re-plans when its lidar marks new cells blocked, and must start moving within 50 milliseconds. Walk the choices in order:
- Memory is not the limit: a million cells fit easily, so IDA* is not needed.
- The grid is uniform-cost, so JPS would cut expansions for the initial plan. But D* Lite's repair is the bigger win once the robot moves, and the two do not combine directly.
- The map changes as the robot drives, and changes are mostly near the robot. D* Lite is the fit: one full search at the start, then small repairs.
- If the first full search misses the 50 millisecond budget, run an inflated heuristic on the first plan (the anytime D* family combines ARA* and D* Lite ideas) or plan on a coarser grid first.
Failure modes
- Bidirectional search stopping at first contact. Returns a valid but suboptimal path. Use the mu rule.
- Inconsistent heuristic with closed sets. A* and D* Lite assume consistency to avoid reopening; an admissible but inconsistent h can return suboptimal paths unless closed nodes may be reopened.
- IDA* on real-valued costs. Each iteration adds one node; runtime explodes. Round costs or switch to A*.
- JPS with mismatched corner rules. Paths clip walls or miss valid shortcuts. Fix the movement model first and test against A*.
- ARA* without INCONS. Improved nodes are lost between iterations and the bound is wrong.
- D* Lite with a heuristic to the goal. It must estimate distance from the robot's position, h(s_start, s).
Trade-offs and related reading
Every variant moves cost somewhere else. Start with plain A* and a good heuristic; switch only when a measurement shows which limit you hit.
Related reading: Dijkstra's algorithm is A* with h = 0 and explains the settled-frontier invariant these variants rely on; 0-1 BFS covers graphs where a deque replaces the heap; and constrained shortest path handles searches with resource limits on the path.
What to do next
- Profile plain A* first: memory peak, expansions and wall time on representative queries.
- Name the binding limit: memory, symmetric grid paths, deadline, or changing map.
- Implement the matching variant behind the same interface as your A*.
- Build a test that compares path cost against plain A* or Dijkstra on hundreds of random maps.
- For bidirectional search, assert the mu stop rule in a unit test with a map where the first meeting is not optimal.
- For anytime planners, log the published bound with each path so callers can trust it.