Multi-Dimensional Heuristic Searching

Abstract

A heuristic improvement technique referred to as multi-dimensional heuristics is presented. Instead of only applying the heuristic between two states X1/X1X2 and X2, when a distance estimate of is needed, this technique uses a reference state R and applies the heuristic function to (X1,R) and (X'2,R) and compares the resulting values. If two states are close to each other, then they should also be approximately equidistant to a third reference state. It is possible to use many such reference states to improve some heuristics. The reference states are used to map the search into an N-dimensional search space. The process of choosing reference states can be automated and is in fact a learning procedure. Test results using the 15-puzzle are presented in support of the effectiveness of multi-dimensional heuristics. This method has been shown to improve both a weak 15-puzzle heuristic, the tile reversal heuristic, as well as the stronger Manhattan distance heuristic.