Memory-Bounded A* Graph Search

May 2002

Proceedings of the Fifteenth International Florida Artificial Intelligence Research Society Conference (FLAIRS 2002)

Volume

Proceedings of the Fifteenth International Florida Artificial Intelligence Research Society Conference (FLAIRS 2002)

All Papers

The strategy for memory-bound A* search adopted by MA* (Chakrabarti et al. 1989), SMA* (Russell 1992), and SMAG* (Kaindl and Khorsand 1994) is to prune the least-promising nodes from the open list when memory is full, in order to make room for insertion of new nodes. To preserve search information from pruned nodes, heuristic estimates are backed-up through the search graph. We show that even when the heuristic function is consistent, backed-up heuristic estimates become inconsistent. Thus, it is always possible to find a better path to a node that has been previously expanded. We describe how to modify a memory-bounded A* graph-search algorithm so that it handles the discovery of a better path to a previously expanded node in a more efficient way. We demonstrate its improved performance on a challenging graph-search problem in computational biology.