Computer Science – Artificial Intelligence
Scientific paper
2011-04-11
IJCAI-2011
Computer Science
Artificial Intelligence
7 pages, 2 figures, to appear in IJCAI-2011, http://www.ijcai.org/
Scientific paper
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.
Shimony Solomon Eyal
Tolpin David
No associations
LandOfFree
Rational Deployment of CSP Heuristics does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Rational Deployment of CSP Heuristics, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Rational Deployment of CSP Heuristics will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-58575