Proceedings

Qualitative CSP, Finite CSP, and SAT: Comparing Methods for Qualitative Constraint-based Reasoning

Download BibTeX Cite

Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence. Pages 628-632.

© 2009 International Joint Conferences on Artificial Intelligence

Abstract

Qualitative Spatial and Temporal Reasoning (QSR) is concerned with constraint-based formalisms for representing, and reasoning with, spatial and temporal information over infinite domains. Within the QSR community it has been a widely accepted assumption that genuine qualitative reasoning methods outperform other reasoning methods that are applicable to encodings of qualitative CSP instances. Recently this assumption has been tackled by several authors, who proposed to encode qualitative CSP instances as finite CSP or SAT instances. In this paper we report on the results of a broad empirical study in which we compared the performance of several reasoners on instances from different qualitative formalisms. Our results show that for small-sized qualitative calculi (e.g., Allen's interval algebra and RCC-8) a state-of-the-art implementation of QSR methods currently gives the most efficient performance. However, on recently suggested large-size calculi, e.g., OPRA4, finite CSP encodings provide a considerable performance gain. These results confirm a conjecture by Bessière stating that support-based constraint propagation algorithms provide better performance for large-sized qualitative calculi.Matthias Westphal, Stefan Wölfl

  1. [Allen, 1983] James F. Allen. Maintaining knowledge about temporal intervals. Commun. ACM, 26(11):832-843, 1983.
  2. [Bennett, 1997] Brandon Bennett. Logical Representations for Automated Reasoning about Spatial Relationships. PhD thesis, The University of Leeds, 1997.
  3. [Bessière, 1996] Christian Bessière. A simple way to im- prove path consistency processing in interval algebra net- works. In AAAI/IAAI, Vol. 1, pages 375-380, 1996.
  4. [Bessière, 2006] Christian Bessière. Constraint propagation. Technical Report LIRMM 06020, CNRS/University of Montpellier, 2006.
  5. [Boussemart et al., 2004] Frédéric Boussemart, Fred Hemery, Christophe Lecoutre, and Lakhdar Sais. Boost- ing systematic search by weighting constraints. In ECAI 2004, pages 146-150. IOS Press, 2004.
  6. [Brand, 2004] Sebastian Brand. Relation variables in quali- tative spatial reasoning. In KI 2004, LNCS: 3238, pages 337-350. Springer, 2004.
  7. [Condotta et al., 2006] Jean-Franc ¸ois Condotta, Dominique D'Almeida, Christophe Lecoutre, and Lakhdar Sais. From qualitative to discrete constraint networks. In Workshop on Qualitative Constraint Calculi held with KI 2006, pages 54-64, Bremen, Germany, 2006.
  8. [Condotta et al., 2007] Jean-Franc ¸ois Condotta, Gérard Ligozat, and Mahmoud Saade. Eligible and frozen constraints for solving temporal qualitative constraint networks. In CP 2007, LNCS: 4741, pages 806-814. Springer, 2007.
  9. [Dimopoulos and Stergiou, 2006] Yannis Dimopoulos and Kostas Stergiou. Propagation in CSP and SAT. In CP 2006, LNCS: 4204, pages 137-151. Springer, 2006. [Eén and Sörensson, 2003] Niklas Eén and Niklas Sörensson. An extensible SAT-solver. In SAT 2003, LNCS: 2919, pages 502-518. Springer, 2003.
  10. [Gantner et al., 2008] Zeno Gantner, Matthias Westphal, and Stefan Wölfl. GQR -A fast reasoner for binary qualitative constraint calculi. In AAAI-08 Workshop on Spatial and Temporal Reasoning, Chicago, USA, AAAI, 2008.
  11. [Hebrard, 2008] Emmanuel Hebrard. Mistral, a constraint satisfaction library. In Proceedings of the Third Interna- tional CSP Solver Competition, 2008.
  12. [Ladkin and Reinefeld, 1997] Peter B. Ladkin and Alexan- der Reinefeld. Fast algebraic methods for interval con- straint problems. Ann. Math. Artif. Intell., 19(3-4):383- 411, 1997.
  13. [Lecoutre et al., 2006] Christophe Lecoutre, Lakhdar Sais, Sébastien Tabary, and Vincent Vidal. Last conflict based reasoning. In ECAI 2006, pages 133-137. IOS Press, 2006.
  14. [Ligozat and Renz, 2004] Gérard Ligozat and Jochen Renz. What is a qualitative calculus? A general framework. In PRICAI 2004, LNCS: 3157, pages 53-64. Springer, 2004.
  15. [Moratz, 2004] Reinhard Moratz. Qualitative spatial reason- ing about oriented points. Technical Report 003/10-2004, SFB/TR 8 Spatial Cognition, 2004.
  16. [Nebel, 1997] Bernhard Nebel. Solving hard qualitative tem- poral reasoning problems: Evaluating the efficiency of us- ing the ORD-horn class. Constraints, 1(3):175-190, 1997.
  17. [Pham et al., 2006] Duc Nghia Pham, John Thornton, and Abdul Sattar. Towards an efficient SAT encoding for tem- poral reasoning. In CP 2006, LNCS: 4204, pages 421- 436. Springer, 2006.
  18. [Randell et al., 1992] David A. Randell, Zhan Cui, and An- thony G. Cohn. A spatial logic based on regions and con- nection. In KR 1992, pages 165-176, 1992.
  19. [Renz and Nebel, 2001] Jochen Renz and Bernhard Nebel. Efficient methods for qualitative spatial reasoning. J. Artif. Intell. Res. (JAIR), 15:289-318, 2001.
  20. [Walsh, 2000] Toby Walsh. SAT v CSP. In CP 2000, LNCS: 1894, pages 441-456. Springer, 2000.

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

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