Localizing A*

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 we propose a new search algorithm and suitable data structures in order to minimize page faults by a local reordering of the sequence of expansions. We prove its correctness and completeness and evaluate it in a real-world scenario of searching a large road map in a commercial route planning system.

Authors

• Stefan Edelkamp

Keywords

No keywords are indexed for this paper.