Using Inconsistent Heuristics on A* Search

Nathan R. Sturtevant, Zhifu Zhang, Robert Holte, Jonathan Schaeffer

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.

Subjects: 15.7 Search; 1.11 Planning

Submitted: May 5, 2008

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.