Localizing A*

Stefan Edelkamp, Institut für Informatik; Stefan Schrödl, DaimlerChrysler Research and Technology

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.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.