deployment for γ = 10−3and of uniform random deployment, with total number of solution count estimations equal to that of the VOI-driven deployment. For both schemes, the values for which solution counts were not estimated were ordered randomly, and the search was repeated 20 times. The mean search time for the random deployment is ≈ 1.6 times longer than for the VOI-driven deployment, and has ≈ 100 times greater standard deviation.

  \begin{tabular}{c|c|c|c}  & mean($T$), sec & median($T$), sec & sd($T$), sec \\ \hline VOI-driven & 19.841 & 19.815 & 0.188 \\ \hline random & 31.421 & 42.085 & 20.038 \\ \end{tabular}  
Table 2: VOI-driven vs. random deployment

## 6 Discussion And Related Work

The principles of bounded rationality appear in [Horvitz, 1987]. [Russell and Wefald, 1991] provided a formal description of rational metareasoning and case studies of applications in several problem domains. A typical use of rational metareasoning in search is in finding which node to expand, or in a CSP context determining a variable or value assignment. The approach taken in this paper adapts these methods to whether to spend the time to compute a heuristic.

Runtime selection of heuristics has lately been of interest, e.g. deploying heuristics for planning [Domshlak *et al.*,
2010]. The approach taken is usually that of *learning* which heuristics to deploy based on features of the search state. Although our approach can also benefit from learning, since we have a parameter that needs to be tuned, its value is mostly algorithm dependent, rather than problem-instance dependent.

This simplifies learning considerably, as opposed to having to learn a classifier from scratch. Comparing metareasoning techniques to learning techniques (or possibly a combination of both, e.g. by learning more precise distribution models) is an interesting issue for future research.

Although rational metareasoning is applicable to other types of heuristics, solution-count estimation heuristics are natural candidates for the type of optimization suggested in this paper. [Dechter and Pearl, 1987] first suggested solution count estimates as a value-ordering heuristic (using propagation on trees) for constraint satisfaction problems, refined in
[Meisels *et al.*, 1997] to multi-path propagation.

[Horsch and Havens, 2000] used a value-ordering heuristic that estimated relative solution counts to solve constraint satisfaction problems and demonstrated efficiency of their algorithm (called pAC, probabilistic Arc Consistency). However, the computational overhead of the heuristic was large, and the relative solution counts were computed offline. [Kask et al., 2004] introduced a CSP algorithm with a solution counting heuristic based on the Iterative Join-Graph Propagation
(IJGP-SC), and empirically showed performance advances over MAC in most cases. In several cases IJGP-SC was still slower than MAC due to the computational overhead.

Impact-based value ordering [Refalo, 2004] is another heavy informative heuristic. One way to decrease its overhead, suggested in [Refalo, 2004], is to learn the impact of an assignment by averaging the impact of earlier assignments of the same value to the same variable. Rational deployment of this heuristic by estimating the probability of backtracking based on the impact may be possible, an issue for future research. [Gomes *et al.*, 2007] propose a technique that adds random generalized XOR constraints and counts solutions with high precision, but at present requires *solving* CSPs, thus seems not to be immediately applicable as a search heuristic.

The work presented in this paper differs from the above related schemes in that it does not attempt to introduce new heuristics or solution-count estimates. Rather, an "off the shelf" heuristic is deployed selectively based on value of information, thereby significantly reducing the heuristic's "effective" computational overhead, with an improvement in performance for problems of different size and hardness.

In summary, this paper suggests a model for adaptive deployment of value ordering heuristics in algorithms for constraint satisfaction problems. As a case study, the model was applied to a value ordering heuristic based on solution count estimates, and a steady improvement in the overall algorithm performance was achieved compared to *always* computing the estimates, as well as to other simple deployment tactics.

The experiments showed that for many problem instances the optimum performance is achieved when solution counts are estimated only in a relatively small number of search states.

## Acknowledgments

The research is partially supported by the IMG4 Consortium under the MAGNET program of the Israeli Ministry of Trade and Industry, by Israel Science Foundation grant 305/09, by the Lynne and William Frankel Center for Computer Sciences, and by the Paul Ivanier Center for Robotics Research and Production Management.

## References

[Ansotegui ´ *et al.*, 2006] Carlos Ansotegui, Ram ´ on B ´ ejar, ´
Cesar Fern ´ andez, Carla Gomes, and Carles Mateu. The `
impact of balancing on problem hardness in a highly structured domain. In Proc. of 9th Int. Conf. on Theory and Applications of Satisfiability Testing (SAT 06), 2006.

[Boussemart *et al.*, 2005] Fred´ eric Boussemart, Fred ´
Hemery, and Christophe Lecoutre. Description and representation of the problems selected for the first international constraint satisfaction solver competition. Technical report, Proc. of CPAI'05 workshop, 2005.

[Dechter and Pearl, 1987] Rina Dechter and Judea Pearl.

Network-based heuristics for constraint-satisfaction problems. *Artif. Intell.*, 34:1–38, December 1987.

[Domshlak *et al.*, 2010] Carmel Domshlak, Erez Karpas, and Shaul Markovitch. To max or not to max: Online learning for speeding up optimal planning. In *AAAI*, 2010.

[Geelen, 1992] Pieter Andreas Geelen. Dual viewpoint heuristics for binary constraint satisfaction problems. In Proc. 10th European Conf. on AI, ECAI '92, pages 31–35, New York, NY, USA, 1992. John Wiley & Sons, Inc.