Heuristic improvement through triangulation

Abstract

This paper presents a method for improving heuristics using a triangulation technique. Instead of using a heuristic to directly estimate distance (X₁, X₂) between nodes X₁ and X₂, the proposed technique selects a reference node R_i applies the heuristic to (X₁,R_i) and (X₂,R_i), 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.