Proceedings

Probabilistic Consistency Boosts MAC and SAC

Download BibTeX Cite

Proceedings of the Twentieth International Joint Conference on Artificial Intelligence. Pages 143-147.

© 2007 International Joint Conferences on Artificial Intelligence

Abstract

Constraint Satisfaction Problems (CSPs) are ubiquitous in Artificial Intelligence. The backtrack algorithms that maintain some local consistency during search have become the de facto standard to solve CSPs. Maintaining higher levels of consistency, generally, reduces the search effort. However, due to ineffective constraint propagation, it often penalises the search algorithm in terms of time. If we can reduce ineffective constraint propagation, then the effectiveness of a search algorithm can be enhanced significantly. In order to do so, we use a probabilistic approach to resolve when to propagate and when not to. The idea is to perform only the useful consistency checking by not seeking a support when there is a high probability that a support exists. The idea of probabilistic support inference is general and can be applied to any kind of local consistency algorithm. However, we shall study its impact with respect to arc consistency and singleton arc consistency (SAC). Experimental results demonstrate that enforcing probabilistic SAC almost always enforces SAC, but it requires significantly less time than SAC. Likewise, maintaining probabilistic arc consistency and maintaining probabilistic SAC require significantly less time than maintaining arc consistency and maintaining SAC.

  1. [Bessière and Debruyne, 2005] C. Bessière and R. De- bruyne. Optimal and suboptimal singleton arc consistency algorithms. In Proceedings of the 19th International Joint Conference on Artificial Intelligence, pages 54-59, 2005. IJCAI
  2. [Bessière and Régin, 2001] C. Bessière and J.-C. Régin. Re- fining the basic constraint propagation algorithm. In Pro- ceedings of the 17th International Joint Conference on Ar- tificial Intelligence, pages 309-315, 2001. IJCAI
  3. [Boussemart et al., 2004] F. Boussemart, F. Hemery, C. Lecoutre, and L. Saïs. Boosting systematic search by weighting constraints. In Proceedings of the 13th European Conference on Artificial Intelligence, 2004.
  4. [Boussemart et al., 2005] F. Boussemart, F. Hemery, and C. Lecoutre. Description and representation of the prob- lems selected for the 1st international constraint satisfac- tion solver competition. In Proceedings of the 2nd Inter- national Workshop on Constraint Propagation and Imple- mentation, Volume 2 Solver Competition, 2005.
  5. [Chmeiss and Saïs, 2004] A. Chmeiss and L. Saïs. Con- straint satisfaction problems:backtrack search revisited. In Proceedings of the Sixteenth IEEE International Confer- ence on Tools with Artificial Intelligence, pages 252-257, Boca Raton, FL, USA, 2004. IEEE Computer Society.
  6. [Debruyne and Bessière, 1997] R. Debruyne and C. Bessière. Some practical filtering techniques for the constraint satisfaction problem. In Proceedings of the 15th International Joint Conference on Artificial Intelligence, pages 412-417, 1997.
  7. [Gent et al., 2001] I.P. Gent, E. MacIntyre, P. Prosser, B. Smith, and T. Walsh. Random constraint satisfaction: Flaws and structure. Journal of Constraints, 6(4), 2001.
  8. [Horsch and Havens, 2000] M. Horsch and W Havens. Prob- abilistic arc consistency: A connection between constraint reasoning and probabilistic reasoning. In 16th Conference on Uncertainity in Artificial Intelligence, 2000.
  9. [Lecoutre and Cardon, 2005] C. Lecoutre and S. Cardon. A greedy approach to establish singleton arc consistency. In Proceedings of the 19th International Joint Conference on Artificial Intelligence, pages 199-204, 2005. IJCAI
  10. [Mackworth, 1977] A.K. Mackworth. Consistency in net- works of relations. Artificial Intelligence, 8:99-118, 1977.
  11. [Mehta and van Dongen, 2005a] D. Mehta and M.R.C. van Dongen. Maintaining probabilistic arc consistency. In Pro- ceedings of the 2nd International Workshop on Constraint Propagation and Implementation, pages 49-64, 2005.
  12. [Mehta and van Dongen, 2005b] D. Mehta and M.R.C. van Dongen. Reducing checks and revisions in coarse-grained mac algorithms. In Proceedings of the Nineteenth Interna- tional Joint Conference on Artificial Intelligence, 2005. IJCAI
  13. [Prosser et al., 2000] P. Prosser, K. Stergiou, and T. Walsh. Singleton consistencies. In Proceedings of the 6th Inter- national Conference on Principles and Practice of Con- straint Programming, pages 353-368, 2000.
  14. [van Dongen, 2003] M.R.C. van Dongen. Lightweight MAC algorithms. In Proceedings of the 23 rd SGAI International Conference on Innovative Techniques and Applications of Artificial Intelligence, pages 227-240. Springer, 2003.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards