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. |
Year | Venue | Keywords |
---|---|---|
1989 | IJCAI | multi-dimensional heuristic,tile reversal heuristic,multi-dimensional heuristics,heuristic improvement technique,heuristic function,stronger manhattan distance heuristic,reference state r,reference state,n-dimensional search space,15-puzzle heuristic,states x1,heuristic search |
Field | DocType | Citations |
Incremental heuristic search,Computer science,Heuristics,Artificial intelligence,Null-move heuristic,Consistent heuristic,Equidistant,Mathematical optimization,Heuristic,Multi dimensional,Euclidean distance,Algorithm,Machine learning | Conference | 1 |
PageRank | References | Authors |
0.36 | 3 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Peter C. Nelson | 1 | 220 | 25.22 |
Lawrence J. Henschen | 2 | 478 | 280.94 |