Memory-bounded Heuristic Search

Task: Solve A* space problems, but maintain completeness and optimality Iterative-deepening A* (IDA*) Here cutoff information is the f-cost (g+h) instead of depth Cutoff is smallest f-cost of any node that exceeded cutoff on previous iteration Recursive best-first search (RBFS) Recursive algorithm that attempts to mimic standard best-first search with linear space. (simple) Memory-bounded A* ((S)MA*) Drop the worst-leaf node when memory is full Back up if necessary