FAHR: Focused A* Heuristic Recomputation

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.

I. INTRODUCTION

Good heuristic estimates are necessary for effective search. One typically computes a function based on the problem instance that approximates the cost from to the goal. The heuristic function can take a variety of forms. It may be static with respect to all problem instances. For example, straight-line distance is often used as a heuristic for the shortest path through a Euclidean space. It can also be computed on a per-problem basis. In the case of path planning, for example, this can be done by computing a single-source shortest path table through a lower-dimensional search space formed by a simplification of vehicle kinematics or dynamics. In either case, once the heuristic data structure is computed, its values typically do not change until a solution is found or declared not to exist. In this paper we show that it can be beneficial to recompute the heuristic function using information obtained about the search space while the search is underway, re-evaluate the open list using the new , and continue the search with the refined heuristic. We validate our approach using a path planning simulation for a ground vehicle.