Bidirectional & Memory-Bounded Search
Meeting in the middle, IDA* and limited memory.
Search from both ends, and two searches of depth replace one of depth : for and , 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 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 -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 and backward from the goal , and stops when they meet. If both are breadth-first and meet halfway, each only goes 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.
Forward BFS to depth and backward BFS to depth , with branching factor in both directions, generate about
against for one-directional BFS, a saving that itself grows exponentially with the depth:
Memory shrinks too, but stays exponential: to notice the meeting, at least one side's frontier must be kept for membership tests.
With and the goal at depth , about how many times fewer nodes does bidirectional BFS generate than ordinary BFS? Use the leading terms and .
Show the answer
5000
. At the factor would be : the gain is itself exponential in the depth.
Suppose the optimal cost satisfies , and take a cheapest path . For each state on , the prefix and suffix costs are the true distances and , so
By Dijkstra's invariant, every state with has been expanded forward with , and likewise backward. Along , prefix costs grow and suffix costs shrink, so the forward-expanded states form a prefix of , the backward-expanded ones a suffix, and together they cover . Hence some edge of has expanded forward and expanded backward (or one state is expanded by both).
Expanding reached with , and was reached backward with . Whichever came second updated , so
This contradicts . (If a single state was expanded by both searches, directly.) So 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 with step costs (total 6) and a second path with costs (total 7). Alternating, the forward search expands and then , the backward search and then , which already finds through . Next both sides expand (at cost 3.5 each), the first state expanded by both, and the tempting rule returns 7. The correct rule stops earlier: after and , , 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 and a backward node with optimal -values, let , where is the smallest edge cost. Under mild assumptions, every admissible front-to-end bidirectional algorithm must expand or for each pair with , 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.
Why does MM order nodes by rather than by alone?
- The term stops each search from expanding nodes beyond the midpoint, those with
- Doubling makes the heuristic consistent
- It speeds the search up by overestimating the remaining cost
- It is needed for completeness on infinite graphs
Show the answer
A. The term stops each search from expanding nodes beyond the midpoint, those with
A node with has priority , and MM stops before expanding any node whose priority exceeds , so each search stays on its own half of every optimal path while the term still lets a good heuristic prune. With the priority is just : balanced bidirectional uniform-cost search.
IDA*: optimal search in linear space
IDA* (Korf, 1985) is iterative deepening with in place of depth. Each iteration is a depth-first search that prunes every node whose exceeds the current bound, and the next bound is the smallest that was pruned. Memory stays linear, as in DFS, while the bounds guarantee optimality, as in A*.
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 nextBounds never overshoot. Admissibility gives for every node on an optimal path. While the bound is below , an iteration prunes the first node of that path whose exceeds the bound, so the next bound, the smallest pruned , is at most :
Optimality. Bounds increase strictly and range over the finitely many -values at most (such nodes lie at depth at most ). So within finitely many iterations the bound reaches at the latest, no node of an optimal path is pruned, and the search finds a goal. Since at a goal, any goal it returns satisfies
If the number of nodes with grows by a factor 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:
With real-valued costs the -values can all be distinct, and each new bound may admit a single new node. If A* would expand nodes, IDA* then runs about iterations of sizes :
The usual remedy raises every bound by at least some . That bounds the number of iterations, at the price of solutions that may be up to 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 paths of length but only states within distance . 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
| Algorithm | Memory | Optimal? | Idea |
|---|---|---|---|
| IDA* (Korf, 1985) | linear in depth | yes, with admissible | depth-first search with increasing -bounds |
| RBFS (Korf, 1993) | linear in depth | yes, with admissible | recursive best-first search: unwinds to the best alternative and backs up the best of each forgotten subtree to its parent |
| SMA* (Russell, 1992) | all available, nodes | yes, if an optimal solution path fits in memory | A* that, when memory is full, drops the worst leaf and backs its up to the parent |
| Beam search | nodes per level | no, and incomplete | keep only the best nodes of each level |
| Frontier search | the frontier only | yes, with exact duplicate detection | see Graph Search & Duplicate Detection |
Key takeaways
- Bidirectional search replaces by about , but needs predecessors and explicit goals, and it may stop only when , not at the first meeting.
- Front-to-end bidirectional heuristic search long disappointed; MM guarantees that neither direction expands a node with , 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 when all -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.
Which requirement does bidirectional search add to those of ordinary forward search?
- An admissible heuristic
- Unit step costs
- Computable predecessors and an explicitly known goal state
- 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.
Bidirectional uniform-cost search has found a path of cost . The smallest on the forward frontier is 4, and on the backward frontier 5. What should it do?
- Stop and return the path of cost 10
- Continue: a path costing as little as might still pass between the frontiers
- Stop, because the two frontiers have met
- Switch to one-directional search
Show the answer
B. Continue: a path costing as little as might still pass between the frontiers
The rule is to stop when . Here , so a cheaper path through unexpanded states cannot yet be ruled out.
IDA* runs on a problem with real-valued step costs in which every node has a different -value, and A* would expand nodes. How many expansions can IDA* need?
- About , as for iterative deepening
- Exactly
Show the answer
D.
Each new bound may admit just one new node, so there are about iterations of sizes , for expansions. Raising every bound by at least avoids this, at the price of solutions up to above optimal.
Why does IDA* perform poorly on an open grid, even with a good heuristic?
- It cannot detect transpositions: each cell is reached by many paths, and IDA* explores every one of them
- Manhattan distance is inadmissible on grids
- Grids have an infinite branching factor
- 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 paths of length with parent pruning, but only states within distance , 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.