AI Glossary / Graphs and symbolic AI / Advanced

SMA*

Definition

SMA*, or Simplified Memory-Bounded A*, is a heuristic search algorithm that works within a memory limit. It expands promising search-tree leaves using estimated solution costs and, when necessary, forgets less promising leaves while retaining information about their costs. Forgotten branches can later be regenerated if they become worth exploring.

What it means

Ordinary A* can retain a large frontier of possible paths. Memory may run out before the search reaches a solution, even when each individual path is short. SMA* addresses that limitation by managing what remains explicitly stored.
Forgetting is not intended to mean permanently declaring a branch useless. A backed-up value tells an ancestor how promising the forgotten continuation was. This distinguishes the method from simply discarding all but a fixed set of alternatives without preserving their search information. The tradeoff is that regenerating forgotten nodes can increase computation time.

How it works

Use an evaluation based on path cost g plus an admissible estimate h of remaining cost, together with backed-up information acquired during search. Expand a best leaf. When memory is full, remove a worst leaf and preserve its relevant value at its parent so the omitted continuation can be reconsidered.
Tie handling and backup rules matter; the standard account expands a newest best leaf and deletes an oldest worst leaf. If the memory limit cannot hold a required root-to-goal path, that solution is not reachable by the implementation's stored-path representation. Optimality and completeness claims therefore depend on sufficient memory, the heuristic, and the usual search assumptions.

Three practical examples

• A puzzle solver can explore paths under a specified node-storage budget while retaining estimates for forgotten alternatives.
• A constrained planning prototype can compare memory-limited search with ordinary A* when frontier storage is the bottleneck.
• An algorithms lesson can demonstrate how reducing memory can increase repeated computation even when the solution itself is short.

Think of it this way

Think of keeping only a limited number of folders open while leaving summary notes for folders put away. If the open folders become less promising, the notes help decide which one to retrieve. The analogy is limited because search backups have precise mathematical meanings and must preserve the information required by the algorithm.

Worked example

Consider an original tree with root R and children A, B, and C. The initial leaf estimates are f(A) = 5, f(B) = 7, and f(C) = 9. Suppose the illustrative storage budget holds four nodes, including the root, so the current tree fills it.
Expanding A generates its only child D, which is a goal with path cost 12. Its goal estimate is therefore 12. Under the usual best-first goal-selection discipline, generating a goal is not by itself a reason to stop while a cheaper solution may remain elsewhere.
To keep four stored nodes, the worst leaf D at value 12 is forgotten, and A retains the backed-up value 12 for that continuation. The stored leaves now have values A = 12, B = 7, and C = 9. B becomes the next best leaf.
Suppose B's only child G is a goal with path cost 8. Storing G would again exceed the budget. The worst remaining leaf A, valued at 12, can be forgotten with its information retained above it. The stored tree contains R, B, C, and G. G at cost 8 is better than C's lower bound of 9 and the forgotten alternative's bound of 12, so it can be selected as the solution.
These values can be realized with root edges of cost 1, edges A→D of cost 11 and B→G of cost 7, and an eventual C-branch goal of cost 10. Initial h values 4, 6, and 8 are admissible. The trace illustrates retention and forgetting, not every bookkeeping operation of a production implementation.

Illustrative case study

In a fictional case, Juniper Puzzles compares solvers on a collection of generated planning problems. Ordinary A* sometimes exceeds the available memory. The team tests SMA* with explicit node budgets and records both peak storage and the number of regenerated nodes.
Some problems fit comfortably; others repeatedly revisit forgotten branches. Developers report those differences instead of describing bounded memory as a free speed improvement. They also verify that each test's solution depth can fit within the relevant storage budget. No real benchmark performance is claimed.

Common misconceptions and mistakes

SMA* is not guaranteed to be faster than A*. Less memory can mean more regeneration and substantial overhead. An admissible heuristic alone does not overcome a budget too small to retain an optimal solution path.
Backing up a forgotten node's value is essential; deleting it without the necessary information changes the method. A goal discovered during expansion is not automatically the cheapest available solution. Also, theoretical budgets expressed as node counts are not exact byte counts: implementations need storage for states, links, queues, and backup metadata.

Business use

For business planning software, the relevant question is whether controlled memory use justifies additional search work. Measure actual memory, runtime, node generation, regeneration, and solution cost on representative workloads.
Specify what the memory limit includes and how repeated states are handled. Avoid advertising unconditional optimality when the required path may not fit. A useful evaluation compares several memory budgets and explains whether failures reflect an exhausted time budget, insufficient path storage, or an absence of a solution under the model.

People also ask

Does SMA* permanently discard every deleted branch?

No. Backed-up information can lead it to regenerate a forgotten branch.

Is bounded memory the same as bounded runtime?

No. Regeneration can make runtime large.

Does SMA* always return an optimal solution?

The standard guarantee requires an optimal solution to be reachable within the memory limit, along with the applicable heuristic and search assumptions.

Check your understanding

Why does B become preferable after A's child is examined?

Answer: A's backed-up estimate rises to 12, while B remains at 7. The search uses the updated information instead of repeating A's old estimate of 5.

Related terms

• Admissible heuristic
• Best-first search
• Recursive best-first search
• Frontier
• A* search
• memory-bounded search
• search-tree node
• path cost

Learn next

Imagine that every goal requires a path containing six stored nodes but the budget holds only four. Explain why clever deletion cannot make that complete root-to-goal path fit under this representation, even if heuristic estimates are accurate.

More in Graphs and symbolic AI

• Slack - In scheduling, slack is the amount of timing flexibility available to an activity under the schedule's assumptions.
• Sliding window - A sliding window is a fixed-size region moved across an input so that a repeated operation can be applied at successive positions.
• Slop (search algorithms) - Slop is a positional tolerance used in phrase or proximity search.
• Small-scale learning - Small-scale learning refers to machine learning with a relatively limited training dataset.
• Small-world - A small-world network is a graph that combines strong local clustering with relatively short routes between nodes across the network.
• SMDP - SMDP stands for semi-Markov decision process: a model for sequential decisions in which the time between decision points can vary.

Sources

Sources: Russell and Norvig, AIMA author-hosted chapter, SMA* behavior and memory-dependent guarantees: https://aima.cs.berkeley.edu/4th-ed/pdfs/newchap04.pdf . Russell, Efficient Memory-Bounded Search Methods, original paper university-hosted copy: https://cse.sc.edu/~mgv/csce580f11/gradPres/Russell_ecai92-sma.pdf .

Previous: Slot filling Next: Small data