OPEN ACCESS
We study the problem of consistency checking for constraint networks over combined qualitative formalisms. We propose a framework which encompasses loose integrations, multiscale reasoning and a form of spatio-temporal reasoning. In particular, we identify sufficient conditions ensuring the polynomiality of consistency checking, and we use them to find tractable subclasses.
qualitative constraint networks, consistency checking, multi-scale reasoning, loose integration, tractable subclass, temporal reasoning
Allen J. F. (1983). Maintaining knowledge about temporal intervals. Commun. ACM, vol. 26, no 11, p. 832-843.
Beek P. van, Cohen R. (1989). Approximation algorithms for temporal reasoning. University of Waterloo. Department of Computer Science.
Chen J., Cohn A. G., Liu D., Wang S., Ouyang J., Yu Q. (2015). A survey of qualitative spatial representations. The Knowledge Engineering Review, vol. 30, no 01, p. 106-136.
Chittaro L., Montanari A. (2000). Temporal representation and reasoning in artificial intelligence: Issues and approaches. Annals of Mathematics and Artificial Intelligence, vol. 28, no 1-4, p. 47-106.
Cohen-Solal Q., Bouzid M., Niveau A. (2015a). An algebra of granular temporal relations for qualitative reasoning. In Proc. of IJCAI, p. 2869-2875.
Cohen-Solal Q., Bouzid M., Niveau A. (2015b). Une algèbre des relations temporelles granulaires pour le raisonnement qualitatif. In Actes des neuvièmes journées de l'intelligence artificielle fondamentale.
Cohen-Solal Q., Bouzid M., Niveau A. (2017). Checking the consistency of combined qualitative constraint networks. In Proc. of AAAI.
Cohn A. G., Li S., Liu W., Renz J. (2014). Reasoning about topological and cardinal direction relations between 2-dimensional spatial objects. Journal of Artificial Intelligence Research, vol. 51, p. 493-532.
Condotta J.-F., Kaci S., Marquis P., Schwind N. (2009). Merging qualitative constraint networks defined on different qualitative formalisms. In Proc. of the international conference on spatial information theory, p. 106-123.
Dylla F., Mossakowski T., Schneider T., Wolter D. (2013). Algebraic properties of qualitative spatio-temporal calculi. In Proc. of the international conference on spatial information theory, p. 516-536.
Euzenat J. (2001). Granularity in relational formalisms with application to time and space representation. Computational intelligence, vol. 17, no 4, p. 703-737.
Euzenat J., Montanari A. (2005). Time granularity. Foundations of Artificial Intelligence, vol. 1, p. 59-118.
Freksa C. (1991). Conceptual neighborhood and its role in temporal and spatial reasoning. In Proc. of the IMACS workshop on decision support systems and qualitative reasoning, p. 181-187.
Gerevini A., Nebel B. (2002). Qualitative spatio-temporal reasoning with RCC-8 and Allen's interval calculus: Computational complexity. In Proc. of ECAI, p. 312-316.
Gerevini A., Renz J. (2002). Combining topological and size information for spatial reasoning. Artificial Intelligence, vol. 137, no 1, p. 1-42.
Goyal R., Egenhofer M. J. (2000). Cardinal directions between extended spatial objects. IEEE Transactions on Knowledge and Data Engineering, p. 291-301.
Hobbs J. R. (1985). Granularity. In Proc. of IJCAI, p. 432-435.
Jonsson P., Krokhin A. (2004). Complexity classification in qualitative temporal constraint reasoning. Artificial Intelligence, vol. 160, no 1, p. 35-51.
Li S., Cohn A. G. (2012). Reasoning with topological and directional spatial information. Computational Intelligence, vol. 28, no 4, p. 579-616.
Li S., Nebel B. (2007). Qualitative spatial representation and reasoning: A hierarchical approach. The Computer Journal, vol. 50, no 4, p. 391-402.
Ligozat G. (2011). Raisonnement qualitatif sur le temps et l’espace. Lavoisier.
Ligozat G., Renz J. (2004). What is a qualitative calculus? A general framework. In Proc. of the Pacific Rim international conference on artificial intelligence, p. 53-64.
Long Z., Li S. (2015). On distributive subalgebras of qualitative spatial and temporal calculi. In Spatial information theory, p. 354-374. Springer.
Meiri I. (1996, novembre). Combining qualitative and quantitative constraints in temporal reasoning. Artificial Intelligence, vol. 87, no 1-2, p. 343-385.
Moratz R., Renz J., Wolter D. (2000). Qualitative spatial reasoning about line segments. In Proc. of ECAI, p. 234-238.
Navarrete I., Morales A., Sciavicco G., Cardenas-Viedma M. A. (2013). Spatial reasoning with rectangular cardinal relations. Annals of Mathematics and Artificial Intelligence, vol. 67, no 1, p. 31-70.
Randell D. A., Cui Z., Cohn A. G. (1992). A spatial logic based on regions and connection. In Proc. of KR, p. 165-176.
Renz J. (1999). Maximal tractable fragments of the region connection calculus: A complete analysis. In Proc. of IJCAI, p. 448-455.
Renz J., Ligozat G. (2005). Weak composition for qualitative spatial and temporal reasoning. In Proc. of CP, p. 534-548. Springer.
Westphal M., Hué J., Wölfl S., Nebel B. (2013). Transition constraints: A study on the computational complexity of qualitative change. In Proc. of IJCAI, p. 1169-1175.
Westphal M., Woelfl S. (2008). Bipath consistency revisited. In Proc. of the ECAI workshop on spatial and temporal reasoning, p. 36-40.