Euclidean Heuristic Optimization

D. Chris Rayner, Michael H. Bowling, Nathan R. Sturtevant

AAAI 2011 pp. 81-86

doi:10.1609/AAAI.V25I1.7815 /aaai/2011/rayner2011aaai-euclidean/

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.

PDF AAAI Semantic Scholar

Cite

Text

Rayner et al. "Euclidean Heuristic Optimization." AAAI Conference on Artificial Intelligence, 2011. doi:10.1609/AAAI.V25I1.7815

Markdown

[Rayner et al. "Euclidean Heuristic Optimization." AAAI Conference on Artificial Intelligence, 2011.](https://mlanthology.org/aaai/2011/rayner2011aaai-euclidean/) doi:10.1609/AAAI.V25I1.7815

BibTeX

@inproceedings{rayner2011aaai-euclidean,
  title     = {{Euclidean Heuristic Optimization}},
  author    = {Rayner, D. Chris and Bowling, Michael H. and Sturtevant, Nathan R.},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2011},
  pages     = {81-86},
  doi       = {10.1609/AAAI.V25I1.7815},
  url       = {https://mlanthology.org/aaai/2011/rayner2011aaai-euclidean/}
}