Euclidean Heuristic Optimization

Authors

  • D. Chris Rayner University of Alberta
  • Michael Bowling University of Alberta
  • Nathan Sturtevant University of Denver

Abstract

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

Downloads

Published

2011-08-04

How to Cite

Rayner, D. C., Bowling, M., & Sturtevant, N. (2011). Euclidean Heuristic Optimization. Proceedings of the AAAI Conference on Artificial Intelligence, 25(1), 81-86. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/7815

Issue

Section

Constraints, Satisfiability, and Search