Toward Rational Deployment of Multiple Heuristics in A

Tolpin, David; Beja, Tal; Shimony, Solomon Eyal; Felner, Ariel; Karpas, Erez

Toward Rational Deployment of Multiple Heuristics in A

David Tolpin, Tal Beja, Solomon Eyal Shimony, Ariel Felner, Erez Karpas

Download BibTeX Cite

Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Pages 674-679.

Abstract

The obvious way to use several admissible heuristics in A* is to take their maximum. In this paper we aim to reduce the time spent on computing heuristics. We discuss Lazy A*, a variant of A* where heuristics are evaluated lazily: only when they are essential to a decision to be made in the A* search process. We present a new rational meta-reasoning based scheme, Rational Lazy A*, which decides whether to compute the more expensive heuristics at all, based on a myopic value of information estimate. Both methods are examined theoretically. Empirical evaluation on several domains supports the theoretical results, and shows that Lazy A* and Rational Lazy A* are state-of-the-art heuristic combination methods.

David Tolpin, Tal Beja, Solomon Eyal Shimony, Ariel Felner, and Erez Karpas. 2013. Toward Rational Deployment of Multiple Heuristics in A. In Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13. IJCAI, 674–679. https://ijcai.org/proceedings/2013/106

@inproceedings{ijcai2013p106,
  title     = {Toward Rational Deployment of Multiple Heuristics in A},
  author    = {Tolpin, David and Beja, Tal and Shimony, Solomon Eyal and Felner, Ariel and Karpas, Erez},
  booktitle = {Proceedings of the Twenty-Third International Joint Conference on
               Artificial Intelligence, {IJCAI-13}},
  publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
  editor    = {Francesca Rossi},
  pages     = {674--679},
  year      = {2013},
  month     = {8},
  url       = {https://ijcai.org/proceedings/2013/106},
}

TY  - CPAPER
TI  - Toward Rational Deployment of Multiple Heuristics in A
AU  - Tolpin, David
AU  - Beja, Tal
AU  - Shimony, Solomon Eyal
AU  - Felner, Ariel
AU  - Karpas, Erez
T2  - Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13
PB  - AAAI Press / International Joint Conferences on Artificial Intelligence
PY  - 2013
SP  - 674
EP  - 679
UR  - https://ijcai.org/proceedings/2013/106
ER  -