Heuristics for Bounded-Suboptimal Search

Abstract

In heuristic search, it is well-established that different types of heuristics are suited for optimal heuristic search (OHS) and unbounded suboptimal search (USS). In OHS, the heuristic should minimize the error in estimating the true cost of the shortest path, whereas in USS, it is more beneficial for the heuristic to exhibit a clear gradient toward the goal, regardless of the error. However, no study has specifically investigated which heuristic is most effective for bounded suboptimal search (BSS), and the current standard is to use heuristics designed for OHS. This paper introduces a novel method for creating heuristics tailored to BSS by linearly combining heuristics that were designed for OHS and USS. Through experimental evaluation, the proposed method is compared with those suited for OHS and USS. The results demonstrate that, within certain suboptimality bounds, our new heuristic approach outperforms OHS and USS heuristics for various BSS algorithms.