Journal of experimental & theoretical artificial intelligence
Paginering:
Jaargang 7 (1995) nr. 2 pagina's 237-251
Jaar:
1995-04-01
Inhoud:
This paper presents a method for improving heuristics using a triangulation technique. Instead of using a heuristic to directly estimate distance (X1, X2) between nodes X1 and X2, the proposed technique selects a reference node Ri applies the heuristic to (X1,Ri) and (X2,Ri), and uses the Euclidean distance formula to calculate a new heuristic value. If two nodes are close to each other, then they should also be approximately equidistant to a third reference node. Utilizing a set of many such reference nodes, node expansions can be reduced for a large class of heuristics. Very early results for this method, referred to as multi-dimensional heuristics, showed that fewer node expansions were needed when using the triangulation technique. New results in this paper include the development of a new learning procedure for selecting reference nodes, experimentation on reusing reference node sets for multiple goal instances, a comparison of multi-dimensional heuristics with weighting and how they dynamically weight states near the goal, and some observations which help explain how and why this technique improves heuristics.
Tijdschrift beschrijving