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 A * (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 out-dated. The worst-case exponential time of inconsistent heuristics is shown to only occur on con-trived 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 AI 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 chil-dren. 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 A * searches