19th IEEE International Conference on Tools with Artificial Intelligence - Vol.2 (ICTAI 2007)
Determining the Basis for Performance Variations in CSP Heuristics
Paris, France
October 29-October 31
ISBN: 0-7695-3015-X
This paper develops the idea that variable ordering heuristics can be classified on the basis of a small number of distinguishable actions, and that while specific heuris- tics may be classified differently depending on the problem type, the basic actions that determine their classification are the same. Previous work demonstrated two basic categories of heuristics, and that problems in an apparently homoge- neous problem set differ in their amenability to heuristics of different types. The present paper shows that these heuris- tic actions, which may be described as building up con- tention and propagating effects, have distinct values for de- scriptive measures such as depth of failure and the depth at which a problem becomes tractable, that reflect differences in the rapidity of their effects with respect to search depth. Heuristics behave similarly with respect to their basic ac- tions across a wide range of propagation, from simple back- tracking to maintained arc consistency. The propagation- of-effects type of action is closely related to the "simplifi- cation hypothesis" of Hooker and Vinay. This work con- tributes to the goals of explaining heuristic performance and putting heuristic selection on a rational basis.
Citation:
Richard J. Wallace, "Determining the Basis for Performance Variations in CSP Heuristics," ictai, vol. 2, pp.473-480, 19th IEEE International Conference on Tools with Artificial Intelligence - Vol.2 (ICTAI 2007), 2007