---
title: "Rational Deployment of CSP Heuristics"
authors:
  - "David Tolpin"
  - "Solomon Eyal Shimony"
doi: "10.5591/978-1-57735-516-8/IJCAI11-120"
url: "https://ijcai.org/proceedings/2011/120"
pdf: "https://ijcai.org/proceedings/2011/0120.pdf"
venue: "Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence"
year: 2011
pages: "680-685"
track: ""
keywords:
---

# Rational Deployment of CSP Heuristics

David Tolpin, Solomon Eyal Shimony

*Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence*, pages 680-685. DOI: [10.5591/978-1-57735-516-8/IJCAI11-120](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.