Simple Algorithm
Artificial Intelligence · Deep Layer · 26 min

Bidirectional & Memory-Bounded Search

Meeting in the middle, IDA* and limited memory.

Search from both ends, and two searches of depth d/2d/2 replace one of depth dd: for b=10b=10 and d=10d=10, about two hundred thousand nodes instead of ten billion. Search with almost no memory, and you can still find optimal solutions, as IDA* did for the 15-puzzle in 1985. Both ideas hide subtle catches, about when it is safe to stop and how much work gets repeated, and this lesson proves where they lie.

What you’ll learn

  • Analyze bidirectional search: its O(bd/2)\order{b^{d/2}} cost, its requirements, and a provably correct stopping rule for bidirectional uniform-cost search.
  • Explain why front-to-end bidirectional heuristic search long disappointed, and what MM's meet-in-the-middle guarantee and must-expand pairs achieve.
  • Prove that IDA* is optimal in linear space, and quantify its overhead when iteration sizes grow geometrically and when all ff-values differ.
  • Compare RBFS, SMA*, beam search, transposition tables and frontier search as trade-offs between memory, time and guarantees.

Meeting in the middle

Bidirectional search runs two searches at once, forward from the start ss and backward from the goal tt, and stops when they meet. If both are breadth-first and meet halfway, each only goes d/2d/2 deep. The idea needs two things forward search does not: a way to compute predecessors (actions must be invertible, or their inverses known) and an explicit goal state rather than just a goal test. Checkmate, for instance, is a test satisfied by a huge, implicitly defined set of positions.

DerivationThe cost of meeting in the middle
  1. Nbi≈2∑k=0d/2bk=O(bd/2)N_{\mathrm{bi}}\approx2\sum_{k=0}^{d/2}b^k=\order{b^{d/2}}

    Forward BFS to depth ⌈d/2⌉\lceil d/2\rceil and backward BFS to depth ⌊d/2⌋\lfloor d/2\rfloor, with branching factor bb in both directions, generate about

  2. NuniNbi≈bd2 bd/2=12 bd/2\frac{N_{\mathrm{uni}}}{N_{\mathrm{bi}}}\approx\frac{b^d}{2\,b^{d/2}}=\tfrac12\,b^{d/2}

    against O(bd)\order{b^d} for one-directional BFS, a saving that itself grows exponentially with the depth:

  3. space=O(bd/2)\text{space}=\order{b^{d/2}}

    Memory shrinks too, but stays exponential: to notice the meeting, at least one side's frontier must be kept for membership tests.

Predict before you look

With b=10b=10 and the goal at depth d=8d=8, about how many times fewer nodes does bidirectional BFS generate than ordinary BFS? Use the leading terms bdb^d and 2bd/22b^{d/2}.

Show the answer

5000

108/(2⋅104)=5,00010^8/(2\cdot10^4)=5{,}000. At d=12d=12 the factor would be 500,000500{,}000: the gain 12bd/2\tfrac12b^{d/2} is itself exponential in the depth.

DerivationProof
  1. d(s,v)+d(v,t)=C∗<topF+topB⟹d(s,v)<topF  or  d(v,t)<topBd(s,v)+d(v,t)=C^*<\mathrm{top}_F+\mathrm{top}_B\quad\Longrightarrow\quad d(s,v)<\mathrm{top}_F\ \text{ or }\ d(v,t)<\mathrm{top}_B

    Suppose the optimal cost satisfies C∗<μ≤topF+topBC^*<\mu\le\mathrm{top}_F+\mathrm{top}_B, and take a cheapest path PP. For each state vv on PP, the prefix and suffix costs are the true distances d(s,v)d(s,v) and d(v,t)d(v,t), so

  2. P: s→⋯→x⏟forward→y⏟backward→⋯→tP:\ s\to\cdots\to\underbrace{x}_{\text{forward}}\to\underbrace{y}_{\text{backward}}\to\cdots\to t

    By Dijkstra's invariant, every state with d(s,v)<topFd(s,v)<\mathrm{top}_F has been expanded forward with gF(v)=d(s,v)g_F(v)=d(s,v), and likewise backward. Along PP, prefix costs grow and suffix costs shrink, so the forward-expanded states form a prefix of PP, the backward-expanded ones a suffix, and together they cover PP. Hence some edge (x,y)(x,y) of PP has xx expanded forward and yy expanded backward (or one state is expanded by both).

  3. μ≤gF(y)+gB(y)≤d(s,x)+c(x,y)+d(y,t)=C∗\mu\le g_F(y)+g_B(y)\le d(s,x)+c(x,y)+d(y,t)=C^*

    Expanding xx reached yy with gF(y)≤d(s,x)+c(x,y)g_F(y)\le d(s,x)+c(x,y), and yy was reached backward with gB(y)=d(y,t)g_B(y)=d(y,t). Whichever came second updated μ\mu, so

  4. topF+topB≥μ⟹μ=C∗\mathrm{top}_F+\mathrm{top}_B\ge\mu\quad\Longrightarrow\quad\mu=C^*

    This contradicts C∗<μC^*<\mu. (If a single state vv was expanded by both searches, μ≤gF(v)+gB(v)=C∗\mu\le g_F(v)+g_B(v)=C^* directly.) So μ=C∗\mu=C^* when the rule fires.

Think first A tempting rule: stop as soon as some state has been expanded by both searches, and return the path through it. Find what goes wrong.

Take a cheapest path s→x→y→ts\to x\to y\to t with step costs 2,2,22,2,2 (total 6) and a second path s→m→ts\to m\to t with costs 3.5,3.53.5,3.5 (total 7). Alternating, the forward search expands ss and then xx, the backward search tt and then yy, which already finds μ=6\mu=6 through x→yx\to y. Next both sides expand mm (at cost 3.5 each), the first state expanded by both, and the tempting rule returns 7. The correct rule stops earlier: after xx and yy, topF+topB=3.5+3.5=7≥μ=6\mathrm{top}_F+\mathrm{top}_B=3.5+3.5=7\ge\mu=6, and it returns 6.

Bidirectional heuristic search

Adding heuristics should make bidirectional search even better, yet for decades it rarely did. Pohl's bidirectional heuristic path algorithm (1971) used front-to-end heuristics, each search estimating the distance to its own target; front-to-front heuristics, which estimate distances between the two frontiers, are expensive to evaluate. It was long believed that the two searches pass each other "like missiles"; Kaindl and Kainz (1997) showed that they usually meet early, but then spend most of their effort proving that no cheaper path exists. Barker and Korf (2015) argued that with strong heuristics, front-to-end bidirectional search rarely beats A*.

Which nodes must any such algorithm expand? Eckerle, Chen, Sturtevant, Zilles and Holte (2017) answered precisely. For a forward node uu and a backward node vv with optimal gg-values, let lb(u,v)=max⁡(fF(u), fB(v), gF(u)+gB(v)+ε)\mathrm{lb}(u,v)=\max\big(f_F(u),\,f_B(v),\,g_F(u)+g_B(v)+\varepsilon\big), where ε\varepsilon is the smallest edge cost. Under mild assumptions, every admissible front-to-end bidirectional algorithm must expand uu or vv for each pair with lb(u,v)<C∗\mathrm{lb}(u,v)<C^*, so the least possible work is a minimum vertex cover of a bipartite graph. NBS (Chen, Holte, Zilles & Sturtevant, 2017) expands at most twice that minimum.

Check your understanding

Why does MM order nodes by max⁡(f(n),2g(n))\max\big(f(n),2g(n)\big) rather than by f(n)f(n) alone?

  1. The 2g2g term stops each search from expanding nodes beyond the midpoint, those with g(n)>C∗/2g(n)>C^*/2
  2. Doubling gg makes the heuristic consistent
  3. It speeds the search up by overestimating the remaining cost
  4. It is needed for completeness on infinite graphs
Show the answer

A. The 2g2g term stops each search from expanding nodes beyond the midpoint, those with g(n)>C∗/2g(n)>C^*/2

A node with g(n)>C∗/2g(n)>C^*/2 has priority 2g(n)>C∗2g(n)>C^*, and MM stops before expanding any node whose priority exceeds C∗C^*, so each search stays on its own half of every optimal path while the ff term still lets a good heuristic prune. With h≡0h\equiv0 the priority is just 2g2g: balanced bidirectional uniform-cost search.

IDA*: optimal search in linear space

IDA* (Korf, 1985) is iterative deepening with f=g+hf=g+h in place of depth. Each iteration is a depth-first search that prunes every node whose ff exceeds the current bound, and the next bound is the smallest ff that was pruned. Memory stays linear, as in DFS, while the bounds guarantee optimality, as in A*.

text
function IDA*(problem, h):
    bound ← h(problem.initial)
    loop:
        t ← BOUNDED-DFS(problem, Node(problem.initial, g = 0), bound)
        if t = FOUND: return the solution on the current path
        if t = ∞: return failure
        bound ← t                    # smallest f that exceeded the old bound

function BOUNDED-DFS(problem, node, bound):
    f ← node.g + h(node.state)
    if f > bound: return f
    if problem.is_goal(node.state): return FOUND
    next ← ∞
    for each child in EXPAND(problem, node):
        if child.state is on the current path: continue
        t ← BOUNDED-DFS(problem, child, bound)
        if t = FOUND: return FOUND
        next ← min(next, t)
    return next
DerivationProof sketch
  1. boundk<C∗⟹boundk+1≤C∗\mathrm{bound}_k<C^*\quad\Longrightarrow\quad\mathrm{bound}_{k+1}\le C^*

    Bounds never overshoot. Admissibility gives f≤C∗f\le C^* for every node on an optimal path. While the bound is below C∗C^*, an iteration prunes the first node of that path whose ff exceeds the bound, so the next bound, the smallest pruned ff, is at most C∗C^*:

  2. g(G)=f(G)≤bound≤C∗⟹g(G)=C∗g(G)=f(G)\le\mathrm{bound}\le C^*\quad\Longrightarrow\quad g(G)=C^*

    Optimality. Bounds increase strictly and range over the finitely many ff-values at most C∗C^* (such nodes lie at depth at most C∗/εC^*/\varepsilon). So within finitely many iterations the bound reaches C∗C^* at the latest, no node of an optimal path is pruned, and the search finds a goal. Since h(G)=0h(G)=0 at a goal, any goal GG it returns satisfies

DerivationOverhead: geometric growth versus distinct f-values
  1. ∑k≤KNk≈NK(1+1β+1β2+⋯)=ββ−1 NK\sum_{k\le K}N_k\approx N_K\Big(1+\frac1\beta+\frac1{\beta^2}+\cdots\Big)=\frac{\beta}{\beta-1}\,N_K

    If the number of nodes with f≤boundf\le\mathrm{bound} grows by a factor β>1\beta>1 from one iteration to the next, the iterations form a geometric series, and the total work is a constant factor above the last iteration, exactly as for iterative deepening:

  2. ∑k=1Nk=N(N+1)2=Θ(N2)\sum_{k=1}^{N}k=\frac{N(N+1)}{2}=\Theta(N^2)

    With real-valued costs the ff-values can all be distinct, and each new bound may admit a single new node. If A* would expand NN nodes, IDA* then runs about NN iterations of sizes 1,2,…,N1,2,\dots,N:

  3. boundk+1≥boundk+δ⟹solution cost<C∗+δ\mathrm{bound}_{k+1}\ge\mathrm{bound}_k+\delta\quad\Longrightarrow\quad\text{solution cost}<C^*+\delta

    The usual remedy raises every bound by at least some δ>0\delta>0. That bounds the number of iterations, at the price of solutions that may be up to δ\delta worse than optimal:

IDA* is a tree search: it detects cycles on its current path, but no other duplicates. That suits the 15-puzzle, which has few short cycles; there, IDA* with the Manhattan-distance heuristic found the first optimal solutions to random instances (Korf, 1985). On a grid the same design is ruinous: with parent pruning there are Θ(3d)\Theta(3^d) paths of length dd but only O(d2)\order{d^2} states within distance dd. Transposition tables, which cache bounds for states in whatever memory is available, recover much of the loss (Reinefeld & Marsland, 1994).

Other ways to live with limited memory

AlgorithmMemoryOptimal?Idea
IDA* (Korf, 1985)linear in depthyes, with admissible hhdepth-first search with increasing ff-bounds
RBFS (Korf, 1993)linear in depthyes, with admissible hhrecursive best-first search: unwinds to the best alternative and backs up the best ff of each forgotten subtree to its parent
SMA* (Russell, 1992)all available, MM nodesyes, if an optimal solution path fits in memoryA* that, when memory is full, drops the worst leaf and backs its ff up to the parent
Beam searchkk nodes per levelno, and incompletekeep only the kk best nodes of each level
Frontier searchthe frontier onlyyes, with exact duplicate detectionsee Graph Search & Duplicate Detection
Memory-bounded searches trade time, memory and guarantees in different ways.

Key takeaways

  • Bidirectional search replaces bdb^d by about 2bd/22b^{d/2}, but needs predecessors and explicit goals, and it may stop only when topF+topB≥μ\mathrm{top}_F+\mathrm{top}_B\ge\mu, not at the first meeting.
  • Front-to-end bidirectional heuristic search long disappointed; MM guarantees that neither direction expands a node with g>C∗/2g>C^*/2, and NBS expands at most twice the provable minimum.
  • IDA* finds optimal solutions with admissible heuristics in linear memory. Its overhead is a constant factor when iteration sizes grow geometrically, but Θ(N2)\Theta(N^2) when all ff-values differ.
  • Linear-space tree searches pay for every transposition; RBFS, SMA*, transposition tables, frontier search and beam search trade memory, time and guarantees in different ways.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

Which requirement does bidirectional search add to those of ordinary forward search?

  1. An admissible heuristic
  2. Unit step costs
  3. Computable predecessors and an explicitly known goal state
  4. A finite state space
Show the answer

C. Computable predecessors and an explicitly known goal state

The backward search must generate predecessors, so actions must be invertible or their inverses known, and it must start from concrete goal states. A goal given only as a test, like checkmate, defeats it.

Question 2

Bidirectional uniform-cost search has found a path of cost μ=10\mu=10. The smallest gg on the forward frontier is 4, and on the backward frontier 5. What should it do?

  1. Stop and return the path of cost 10
  2. Continue: a path costing as little as 4+5=94+5=9 might still pass between the frontiers
  3. Stop, because the two frontiers have met
  4. Switch to one-directional search
Show the answer

B. Continue: a path costing as little as 4+5=94+5=9 might still pass between the frontiers

The rule is to stop when topF+topB≥μ\mathrm{top}_F+\mathrm{top}_B\ge\mu. Here 9<109<10, so a cheaper path through unexpanded states cannot yet be ruled out.

Question 3

IDA* runs on a problem with real-valued step costs in which every node has a different ff-value, and A* would expand NN nodes. How many expansions can IDA* need?

  1. About bb−1N\tfrac{b}{b-1}N, as for iterative deepening
  2. Θ(Nlog⁡N)\Theta(N\log N)
  3. Exactly NN
  4. Θ(N2)\Theta(N^2)
Show the answer

D. Θ(N2)\Theta(N^2)

Each new bound may admit just one new node, so there are about NN iterations of sizes 1,2,…,N1,2,\dots,N, for N(N+1)/2N(N+1)/2 expansions. Raising every bound by at least δ\delta avoids this, at the price of solutions up to δ\delta above optimal.

Question 4

Why does IDA* perform poorly on an open grid, even with a good heuristic?

  1. It cannot detect transpositions: each cell is reached by many paths, and IDA* explores every one of them
  2. Manhattan distance is inadmissible on grids
  3. Grids have an infinite branching factor
  4. IDA* requires unit step costs
Show the answer

A. It cannot detect transpositions: each cell is reached by many paths, and IDA* explores every one of them

IDA* checks only for cycles on its current path. A grid has Θ(3d)\Theta(3^d) paths of length dd with parent pruning, but only O(d2)\order{d^2} states within distance dd, so the redundancy is exponential. A* with a table of reached states, or IDA* with a transposition table, avoids it.

Further reading

  • I. Pohl, "Bi-directional search," Machine Intelligence 6 (1971).
  • R. E. Korf, "Depth-first iterative-deepening: An optimal admissible tree search," Artificial Intelligence 27(1) (1985), 97–109.
  • R. E. Korf, "Linear-space best-first search," Artificial Intelligence 62 (1993), 41–78.
  • R. C. Holte, A. Felner, G. Sharon & N. R. Sturtevant, "Bidirectional search that is guaranteed to meet in the middle," AAAI (2016).
  • S. Russell & P. Norvig, Artificial Intelligence: A Modern Approach, 4th ed. (Pearson, 2020), sections 3.4–3.5.