Euclidean Heuristic Optimization

We pose the problem of constructing good search heuristics as anoptimization problem: minimizing the loss between the true distances andthe heuristic estimates subject to admissibility and consistency constraints.For a well-motivated choice of loss function, we show performing thisoptimization is tractable. In fact, it corresponds to a recently proposedmethod for dimensionality reduction.We prove this optimization is guaranteed to produce admissible and consistentheuristics, generalizes and gives insight into differential heuristics, and showexperimentally that it produces strong heuristics on problems from threedistinct search domains.