---
title: "A* Search with Inconsistent Heuristics"
authors:
  - "Zhifu Zhang"
  - "Nathan R. Sturtevant"
  - "Robert C. Holte"
  - "Jonathan Schaeffer"
  - "Ariel Felner"
doi: ""
url: "https://ijcai.org/proceedings/2009/111"
pdf: "https://ijcai.org/proceedings/2009/0111.pdf"
venue: "Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence"
year: 2009
pages: "634-638"
track: ""
keywords:
---

# A* Search with Inconsistent Heuristics

Zhifu Zhang, Nathan R. Sturtevant, Robert C. Holte, Jonathan Schaeffer, Ariel Felner

*Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence*, pages 634-638.

## Abstract

Early research in heuristic search discovered that using inconsistent heuristics with A* could result in an exponential increase in the number of node expansions. As a result, the use of inconsistent heuristics has largely disappeared from practice. Recently, inconsistent heuristics have been shown to be effective in IDA*, especially when applying the bidirectional pathmax (BPMX) enhancement. This paper presents new worst-case complexity analysis of A*'s behavior with inconsistent heuristics, discusses how BPMX can be used with A*, and gives experimental results justifying the use of inconsistent heuristics in A* searches.Zhifu Zhang, Nathan R. Sturtevant, Robert Holte, Jonathan Schaeffer, Ariel Felner