Localizing A*

Book One

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 17

Search

Heuristic search in large problem spaces inherently calls for algorithms capable of running under restricted memory. This question has been investigated in a number of articles. However, in general the efficient usage of two-layered storage systems is not further discussed. Even if hard-disk capacity is sufficient for the problem instance at hand, the limitation of main memory}may still represent the bottleneck for their practical applications. Since breadth-first and best-first strategies do not exhibit any locality of expansion, standard virtual memory management can soon result in thrashing due to excessive page faults. In this paper a new extension scheme to the A* algorithm is proposed which minimizes page faults by reordering the sequence of expansions. We prove its admissibility and evaluate it in a real-world scenario of searching a large road map in a route planning system.