Rational deployment of CSP heuristics
D Tolpin, SE Shimony - arXiv preprint arXiv:1104.1924, 2011 - arxiv.org
D Tolpin, SE Shimony
arXiv preprint arXiv:1104.1924, 2011•arxiv.orgHeuristics 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 …
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 …
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.
arxiv.org