FAHR: Focused A* Heuristic Recomputation

Abstract

In this paper we introduce focused A* heuristic recomputation (FAHR), an enhancement to A* search that can detect and correct large discrepancies between the heuristic cost-to-go estimate and the true cost function. In situations where these large discrepancies exist, the search may expend significant effort escaping from the ¿bowl¿ of a local minimum. A* typically computes supporting data structures for the heuristic once, prior to initiating the search. FAHR directs the search out of the bowl by recomputing parts of the heuristic function opportunistically as the search space is explored. FAHR may be used when the heuristic function is in the form of a pattern database. We demonstrate the effectiveness of the algorithm through experiments on a ground vehicle path planning simulation.