Inconsistent heuristics in theory and practice

In the field of heuristic search it is usually assumed that admissible heuristics are consistent, implying that consistency is a desirable attribute. The term "inconsistent heuristic" has, at times, been portrayed negatively, as something to be avoided. Part of this is historical: early research discovered that inconsistency can lead to poor performance for At (nodes might be re-expanded many times). However, the issue has never been fully investigated, and was not re-considered after the invention of IDA*. This paper shows that many of the preconceived notions about inconsistent heuristics are outdated. The worst-case exponential time of inconsistent heuristics is shown to only occur on contrived graphs with edge weights that are exponential in the size of the graph. Furthermore, the paper shows that rather than being something to be avoided, inconsistent heuristics often add a diversity of heuristic values into a search which can lead to a reduction in the number of node expansions. Inconsistent heuristics are easy to create, contrary to the common perception in the Al literature. To demonstrate this, a number of methods for achieving effective inconsistent heuristics are presented. Pathmax is a way of propagating inconsistent heuristic values in the search from parent to children. This technique is generalized into bidirectional pathmax (BPMX) which propagates values from a parent to a child node, and vice versa. BPMX can be integrated into IDA* and A*. When inconsistent heuristics are used with BPMX, experimental results show a large reduction in the search effort required by IDA*. Positive results are also presented for At searches. (C) 2011 Elsevier B.V. All rights reserved.