Rational Deployment of CSP Heuristics

Tolpin, David; Shimony, Solomon Eyal

doi:10.5591/978-1-57735-516-8/IJCAI11-120

Rational Deployment of CSP Heuristics

David Tolpin, Solomon Eyal Shimony

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 680-685.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-120

Abstract

Heuristics are crucial tools in decreasing search effort in varied fields of AI. In order to be effective, a heuristic must be efficient to compute, as well as provide useful information to the search algorithm. However, some well-known heuristics which do well in reducing backtracking are so heavy that the gain of deploying them in a search algorithm might be outweighed by their overhead. We propose a rational metareasoning approach to decide when to deploy heuristics, using CSP backtracking search as a case study. In particular, a value of information approach is taken to adaptive deployment of solution-count estimation heuristics for value ordering. Empirical results show that indeed the proposed mechanism successfully balances the tradeoff between decreasing backtracking and heuristic computational overhead, resulting in a significant overall search time reduction.

David Tolpin, and Solomon Eyal Shimony. 2011. Rational Deployment of CSP Heuristics. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 680–685. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-120

@inproceedings{ijcai2011p120,
  title     = {Rational Deployment of CSP Heuristics},
  author    = {Tolpin, David and Shimony, Solomon Eyal},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {680--685},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-120},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-120},
}

TY  - CPAPER
TI  - Rational Deployment of CSP Heuristics
AU  - Tolpin, David
AU  - Shimony, Solomon Eyal
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 680
EP  - 685
DO  - 10.5591/978-1-57735-516-8/IJCAI11-120
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-120
ER  -