{'fraction_non_alphanumeric': 0.03404255319148936, 'fraction_numerical': 0.00723404255319149, 'mean_word_length': 5.106493506493506, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Using Inconsistent Heuristics on A ∗ Search

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) to O(N). Additional issues surrounding BPMX and A∗ are addressed, and a variety of performance metrics are shown across two domains. Introduction It is widely believed that A∗ is optimal; given the same heuristic and tie-breaking mechanism there is no search algorithm which will always have fewer distinct node expansions. While this is true, it hides an important fact about inconsistent heuristics. Early research on search algorithms discovered that if A∗ uses an inconsistent heuristic, it may perform an exponential number of re-expansions (Martelli 1977). From this perspective, A∗ is inferior to alternative algorithms, which have a worst-case number of expansions and re-expansions of O(N). This result discouraged research on inconsistent heuristics for many years, in particular since most ‘natural’ heuristics seemed to be consistent. Recent research has shown that inconsistent heuristics are easy to create and can be used to great advantage in an IDA∗ search (Zahavi et al. 2007; Felner et al. 2005) by using the BPMX enhancement. Inconsistency hasn’t been a problem in IDA∗ because IDA∗ already performs many node reexpansions and is only used in domains where the cost of re-expansions is fully amortized over the cost of the search. The case for using inconsistent heuristics with IDA∗ has been made; it is time to revisit the perceptions regarding their use with A∗. This paper makes several contributions: • A new search algorithm, DELAY, improves the worstcase complexity of A∗ search with inconsistent heuristics fromO(N) toO(N). This result provides insight into when an inconsistent heuristic will dominate a consistent heuristic; Copyright c © 2008, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved. 0