Using Inconsistent Heuristics on A* Search

Contents

Early research in heuristic search discovered that using inconsistent heuristics in an A* search could result in an exponential blow-up in the number of nodes expanded. As a result, the use of inconsistent heuristics has largely disappeared from practice. However, recent research has shown that they can yield dramatic performance improvements to an IDA* search using the BPMX enhancement. This paper revisits inconsistency in A*-like algorithms. The Delay algorithm is introduced which improves the worst-case complexity from O(N^2) to O(N^{1.5}). Additional issues surrounding BPMX and A* are addressed, and a variety of performance metrics are shown across two domains.