Qualitative Spatial Reasoning Using Constraint Calculi

• AAAI-96 (1996). Proceedings of the 13th National Conference of the American Association for Artificial Intelligence, Portland, OR. MIT Press.

  Google Scholar 

• Achlioptas, D., Kirousis, L., Kranakis, E., Krizanc, D., Molloy, M., and Stamatiou, Y. (1997). Random constraint satisfaction: a more accurate picture. In 3rd Conference on the Principles and Practice of Constraint Programming (CP’97), volume 1330 of Lecture Notes in Computer Science, pages 107–120. Springer Verlag.

  Chapter  Google Scholar 

• Allen, James F. (1983). Maintaining knowledge about temporal intervals. Communications of the ACM, 26(11):832–843.

  Article  Google Scholar 

• Asher, Nicholas and Vieu, Laure (1995). Towards a geometry of common sense: A semantics and a complete axiomatization of mereotopology. In IJCAI-95, 1995, pages 846–852.

  Google Scholar 

• Balbiani, Philippe, Condotta, Jean-François, and Farinas del Cerro, Luis (1998). A model for reasoning about bidimensional temporal relations. In Cohn et al., 1998, pages 124–130.

  Google Scholar 

• Balbiani, Philippe, Condotta, Jean-François, and Farinas del Cerro, Luis (1999a). A new tractable subclass of the rectangle algebra. In IJCAI-99, 1999, pages 442–447.

  Google Scholar 

• Balbiani, Philippe, Condotta, Jean-François, and Farinas del Cerro, Luis (1999b). A tractable subclass of the block algebra: constraint propagation and preconvex relations. In Proccedings of the 9th Portuguese Conference on Artificial Intelligence, pages 75–89.

  Google Scholar 

• Bennett, Brandon (1994). Spatial reasoning with propositional logic. In Doyle, J., Sandewall, E., and Torasso, P., editors, Principles of Knowledge Representation and Reasoning: Proceedings of the 4th International Conference, pages 51–62, Bonn, Germany. Morgan Kaufmann.

  Google Scholar 

• Bessière, Christian (1996). A simple way to improve path-consistency in Interval Algebra networks. In AAAI-96, 1996, pages 375–380.

  Google Scholar 

• Biacino, Loredana and Gerla, Giangiacomo (1991). Connection structures. Notre Dame Journal of Formal Logic, 32(2):242–247.

  Article  Google Scholar 

• Borgo, Stefano, Guarino, Nicola, and Masolo, Claudio (1996). A pointless theory of space based on strong connection and congruence. In Aiello, L.C., Doyle, J., and Shapiro, S.C., editors, Principles of Knowledge Representation and Reasoning: Proceedings of the 5th International Conference, pages 220–229, Cambridge, MA. Morgan Kaufmann.

  Google Scholar 

• Cheeseman, Peter, Kanefsky, Bob, and Taylor, William M. (1991). Where the really hard problems are. In Proceedings of the 12th International Joint Conference on Artificial Intelligence, pages 331–337, Sydney, Australia. Morgan Kaufmann.

  Google Scholar 

• Clarke, Bowman L. (1981). A calculus of individuals based on connection. Notre Dame Journal of Formal Logic, 22(3):204–218.

  Article  Google Scholar 

• Clarke, Bowman L. (1985). Individuals and points. Notre Dame Journal of Formal Logic, 26(1):61–75.

  Article  Google Scholar 

• Clementini, Eliseo, di Felice, Paolino, and Hernandez, Daniel (1997). Qualitative representation of positional information. Artificial Intelligence, 95(2): 317–356.

  Article  Google Scholar 

• Cohn, A.G., Schubert, L., and Shapiro, S.C., editors (1998). Principles of Knowledge Representation and Reasoning: Proceedings of the 6th International Conference, Trento, Italy.

  Google Scholar 

• Cohn, Anthony G., Bennett, Brandon, Gooday, John, and Gotts, Nicholas M. (1997). Representing and reasoning with qualitative spatial relations about regions. In Stock, O., editor, Spatial and Temporal Reasoning, pages 97–134. Kluwer, Dordrecht, Holland.

  Chapter  Google Scholar 

• Cohn, Anthony G. and Varzi, Achille C. (1998). Connection relations in mereotopology. In Proceedings of the 13th European Conference on Artificial Intelligence, pages 150–154, Amsterdam, The Netherlands. Wiley.

  Google Scholar 

• Cohn, Anthony G. and Varzi, Achille C. (1999). Modes of connection. In Spatial Information Theory: Cognitive and Computational Foundations of Geographic Information Science, pages 299–314.

  Google Scholar 

• Cook, Stephen A. (1971). The complexity of theorem-proving procedures. In Proc. 3rd Ann. ACM Symp. on Theory of Computing, pages 151–158, New York. Association for Computing Machinery.

  Chapter  Google Scholar 

• Cormen, Thomas H., Leiserson, Charles E., and Rivest, Ronald L. (1990). Introduction to Algorithms. MIT Press.

  Google Scholar 

• Dornheim, Christoph (1998). Undecidability of plane polygonal mereotopology. In Cohn et al., 1998.

  Google Scholar 

• Egenhofer, Max J. (1991). Reasoning about binary topological relations. In Günther, O. and Schek, H.-J., editors, Proceedings of the Second Symposium on Large Spatial Databases, SSD’91, volume 525 of Lecture Notes in Computer Science, pages 143–160. Springer-Verlag, Berlin, Heidelberg, New York.

  Google Scholar 

• Egenhofer, Max J., Clementini, Eliseo, and Felice, Paolino Di (1994). Topological relations between regions with holes. International Journal of Geographical Information Systems, 8(2):129–144.

  Article  Google Scholar 

• Egenhofer, Max J. and Franzosa, Robert D. (1994). On the equivalence of topological relations. International Journal of Geographical Information Systems, 8(6):133–152.

  Google Scholar 

• Egenhofer, Max J. and Sharma, Jayant (1993). Assessing the consistency of complete and incomplete topological information. Geographical Systems, 1(1):47–68.

  Google Scholar 

• Forbus, Kenneth D., Nielsen, Paul, and Faltings, Boi (1987). Qualitative kinematics: A framework. In McDermott, J., editor, Proceedings of the 10th International Joint Conference on Artificial Intelligence, Milan, Italy. Morgan Kaufmann.

  Google Scholar 

• Frank, Andrew U. (1991). Qualitative spatial reasoning about cardinal directions. In Proceedings of the 7th Austrian Conference on Artificial Intelligence, pages 157–167.

  Google Scholar 

• Freksa, Christian (1992). Using orientation information for qualitative spatial reasoning. In A.U. Frank, I. Campari, U. Formentini, editor, Theories and Methods of Spatio-Temporal Reasoning in Geographic Space, volume 639 of Lecture Notes in Computer Science. Springer-Verlag, Berlin, Heidelberg, New York.

  Google Scholar 

• Galton, Antony (1999). Mereotopology of discrete space. In Freksa, C. and Mark, D.M., editors, Spatial information theory: Cognitive and computational foundations of geographic information science, volume 1661 of Lecture Notes in Computer Science, pages 251–266, Berlin, Heidelberg, New York. Springer Verlag.

  Google Scholar 

• Garey, Michael R. and Johnson, David S. (1979). Computers and Intractability-A Guide to the Theory of NP-Completeness. Freeman, San Francisco, CA.

  Google Scholar 

• Gent, Ian P. and Walsh, Toby (1996). The satisfiability constraint gap. Artificial Intelligence, 81(1–2):59–80.

  Article  Google Scholar 

• Gerevini, Alfonso and Renz, Jochen (1998). Combining topological and qualitative size constraints for spatial reasoning. In Proceedings of the 4th International Conference on Principles and Practice of Constraint Programming, Pisa, Italy.

  Google Scholar 

• Gerevini, Alfonso and Renz, Jochen (2002). Combining topological and size information for spatial reasoning. Artificial Intelligence, 137(1–2):1–42.

  Article  Google Scholar 

• Golumbic, Martin C. and Shamir, Ron (1993). Complexity and algorithms for reasoning about time: A graph-theoretic approach. Journal of the Association for Computing Machinery, 40(5):1128–1133.

  Google Scholar 

• Gotts, Nicholas M. (1996). Using the RCC formalism to describe the topology of spherical regions. Technical Report 96-24, University of Leeds, School of Computer Studies.

  Google Scholar 

• Gotts, Nicholas M., Gooday, John M., and Cohn, Anthony G. (1996). A connection based approach to commonsense topological description and reasoning. The Monist, 79(1):51–75.

  Google Scholar 

• Goyal, Roop and Egenhofer, Max (2001). Similarity of direction relations. In Jensen, C., Schneider, M., Seeger, B. and Tsotras, V., editors, Seventh international symposium on spatial and temporal databases, volume 2121 of Lecture Notes in Computer Science, pages 36–55, LosAngeles, CA. Springer-Verlag.

  Google Scholar 

• Grigni, Michelangelo, Papadias, Dimitris, and Papadimitriou, Christos (1995). Topological inference. In IJCAI-95, 1995, pages 901–906.

  Google Scholar 

• Grzegorczyk, Andrzej (1951). Undecidability of some topological theories. Fundamenta Mathematicae, 38:137–152.

  Google Scholar 

• Guesgen, Hans (1989). Spatial reasoning based on Allen’s temporal logic. Technical Report TR-89-049, ICSI, Berkeley, CA.

  Google Scholar 

• Hernàndez, Daniel (1994). Qualitative Representation of Spatial Knowledge, volume 804 of Lecture Notes in Artificial Intelligence. Springer-Verlag, Berlin, Heidelberg, New York.

  Google Scholar 

• Hernàndez, Daniel, Clementini, Eliseo, and di Felice, Paolino (1995). Qualitative distances. In Spatial Information Theory: A Theoretical basis for GIS, volume 988 of Lecture Notes in Computer Science, pages 45–58, Berlin, Heidelberg, New York. Springer-Verlag.

  Google Scholar 

• Hirsch, Robin (1999). A finite relation algebra with undecidable network satisfaction problem. Bulletin of the IGPL.

  Google Scholar 

• Hogg, Tad, Huberman, Bernardo A., and (eds), Colin P. Williams (1996). Special volume on frontiers in problem solving: Phase transistions and complexity. Artificial Intelligence, 81(1–2).

  Google Scholar 

• IJCAI-95 (1995). Proceedings of the 14th International Joint Conference on Artificial Intelligence, Montreal, Canada.

  Google Scholar 

• IJCAI-99 (1999). Proceedings of the 16th International Joint Conference on Artificial Intelligence, Stockholm, Sweden.

  Google Scholar 

• Isli, Amar and Moratz, Reinhard (1999). Qualitative spatial representation and reasoning: Algebraic models for relative position. Technical Report 284, Universität Hamburg, Fachbereich Informatik.

  Google Scholar 

• Johnson, David S. (1990). A catalog of complexity classes. In van Leeuwen, J., editor, Handbook of Theoretical Computer Science, Vol. A, pages 67–161. MIT Press.

  Google Scholar 

• Kautz, Henry A. and Ladkin, Peter B. (1991). Integrating metric and qualitative temporal reasoning. In Proceedings of the 9th National Conference of the American Association for Artificial Intelligence, pages 241–246, Anaheim, CA. MIT Press.

  Google Scholar 

• Krokhin, Andrei A., Jeavons, Peter, and Jonsson, Peter (2003). Reasoning about temporal relations: The tractable subalgebras of allen’s interval algebra. Journal of the ACM, 50(5):591–640.

  Article  Google Scholar 

• Ladkin, Peter B. and Maddux, Roger (1994). On binary constraint problems. Journal of the Association for Computing Machinery, 41(3):435–469.

  Google Scholar 

• Ladkin, Peter B. and Reinefeld, Alexander (1992). Effective solution of qualitative interval constraint problems. Artificial Intelligence, 57(1):105–124.

  Article  Google Scholar 

• Ligozat, Gerard (1996). A new proof of tractability for ORD-Horn relations. In AAAI-96, 1996, pages 715–720.

  Google Scholar 

• Ligozat, Gerard (1998). Reasoning about cardinal directions. Journal of Visual Languages and Computing, 9:23–44.

  Article  Google Scholar 

• Mackworth, Alan K. (1977). Consistency in networks of relations. Artificial Intelligence, 8:99–118.

  Article  Google Scholar 

• Mackworth, Alan K. and Freuder, Eugene C. (1985). The complexity of some polynomial network consistency algorithms for constraint satisfaction problems. Artificial Intelligence, 25:65–73.

  Article  Google Scholar 

• Montanari, Ugo (1974). Networks of constraints: fundamental properties and applications to picture processing. Information Science, 7:95–132.

  Article  Google Scholar 

• Montello, Daniel R. (1993). Scale and multiple psychologies of space. In Frank, A.U. and Campari, I., editors, Spatial information Theory: A theoretical basis for GIS, volume 716 of Lecture Notes in Computer Science, pages 312–321, Berlin, Heidelberg, New York. Springer Verlag.

  Google Scholar 

• Nebel, Bernhard (1997). Solving hard qualitative temporal reasoning problems: Evaluating the efficiency of using the ORD-Horn class. CONSTRAINTS, 3(1):175–190.

  Article  Google Scholar 

• Nebel, Bernhard and Bürckert, Hans-Jürgen (1995). Reasoning about temporal relations: A maximal tractable subclass of Allen’s interval algebra. Journal of the Association for Computing Machinery, 42(1):43–66.

  Google Scholar 

• Papadias, Dimitris and Theodoridis, Yannis (1997). Spatial relations, minimum bounding rectangles, and spatial data structures. International Journal of Geographic Information Systems, 11(2):111–138.

  Article  Google Scholar 

• Papadimitriou, Christos H. (1994). Computational Complexity. Addison-Wesley, Reading, MA.

  Google Scholar 

• Piaget, Jean and Inhelder, Bärbel (1948). La représentation de l’espace chez l’enfant. Presses universitaires de France, Paris, France.

  Google Scholar 

• Pratt, Ian and Schoop, Dominik (1998). A complete axiom system for polygonal mereotopology of the real plane. Journal of Philosophical Logic, 27: 621–658.

  Article  Google Scholar 

• Pujari, Arun K., Kumari, G. Vijaya, and Sattar, Abdul (1999). INDU: An interval and duration network. In Australian Joint Conference on Artificial Intelligence, pages 291–303.

  Google Scholar 

• Randell, David A. and Cohn, Anthony G. (1989). Modelling topological and metrical properties in physical processes. In Brachman, R., Levesque, H. J., and Reiter, R., editors, Principles of Knowledge Representation and Reasoning: Proceedings of the 1st International Conference, pages 55–66, Toronto, ON. Morgan Kaufmann.

  Google Scholar 

• Randell, David A., Cui, Zhan, and Cohn, Anthony G. (1992). A spatial logic based on regions and connection. In Nebel, B., Swartout, W., and Rich, C., editors, Principles of Knowledge Representation and Reasoning: Proceedings of the 3rd International Conference, pages 165–176, Cambridge, MA. Morgan Kaufmann.

  Google Scholar 

• Renz, Jochen (1998). A canonical model of the Region Connection Calculus. In Cohn et al., 1998, pages 330 – 341.

  Google Scholar 

• Renz, Jochen (1999). Maximal tractable fragments of the Region Connection Calculus: A complete analysis. In IJCAI-99, 1999, pages 448–454.

  Google Scholar 

• Renz, Jochen (2001). A spatial odyssey of the interval algebra: 1. directed intervals. In Proceedings of the 17th International Joint Conference on Artificial Intelligence, pages 51–56, Seattle, WA.

  Google Scholar 

• Renz, Jochen (2002). Qualitative Spatial Reasoning with Topological Information, volume 2293 of Lecture Notes in Artificial Intelligence. Springer Verlag, Berlin, Heidelberg, New York.

  Google Scholar 

• Renz, Jochen (2007). Qualitative spatial and temporal reasoning: Efficient algorithms for everyone. In Proceedings of the 20th International Joint Conference on Artificial Intelligence, January 6-12, pages 526–531, Hyderabad, India.

  Google Scholar 

• Renz, Jochen and Mitra, Debasis (2004). Qualitative direction calculi with arbitrary granularity. In PRICAI 2004: Trends in Artificial Intelligence, 8th Pacific Rim International Conference on Artificial Intelligence, pages 65–74.

  Google Scholar 

• Renz, Jochen and Nebel, Bernhard (1999). On the complexity of qualitative spatial reasoning: A maximal tractable fragment of the Region Connection Calculus. Artificial Intelligence, 108(1–2):69–123.

  Article  Google Scholar 

• Renz, Jochen and Nebel, Bernhard (2001). Efficient methods for qualitative spatial reasoning. Journal of Artificial Intelligence Research, 15:289–318.

  Google Scholar 

• Schaefer, Thomas J. (1978). The complexity of satisfiability problems. In Proc. 10th Ann. ACM Symp. on Theory of Computing, pages 216–226, New York. Association for Computing Machinery.

  Google Scholar 

• Schoop, Dominik (1999). A model-theoretic approach to mereotopology. PhD thesis, Faculty of Science and Engineering, University of Manchester.

  Google Scholar 

• Scivos, Alexander and Nebel, Bernhard (2001). Double-crossing: Decidability and computational complexity of a qualitative calculus for navigation. In Spatial Information Theory: Foundations of Geographic Information Science.

  Google Scholar 

• Skiadopoulos, Spiros and Koubarakis, Manolis (2005). On the consistency of cardinal direction constraints. Artificial Intelligence, 163(1):91–135.

  Article  Google Scholar 

• Smith, Terence R. and Park, Keith K. (1992). Algebraic approach to spatial reasoning. International Journal of Geographic Information Systems, 6(3): 177–192.

  Article  Google Scholar 

• Tarski, Alfred (1941). On the calculus of relations. Journal of Symbolic Logic, 6:73–89.

  Article  Google Scholar 

• van Beek, Peter (1992). Reasoning about qualitative temporal information. Artificial Intelligence, 58(1–3):297–321.

  Article  Google Scholar 

• van Beek, Peter and Manchak, Dennis W. (1996). The design and experimental analysis of algorithms for temporal reasoning. Journal of Artificial Intelligence Research, 4:1–18.

  Article  Google Scholar 

• Vilain, Marc B. and Kautz, Henry A. (1986). Constraint propagation algorithms for temporal reasoning. In Proceedings of the 5th National Conference of the American Association for Artificial Intelligence, pages 377–382, Philadelphia, PA.

  Google Scholar 

• Vilain, Marc B., Kautz, Henry A., and van Beek, Peter (1989). Constraint propagation algorithms for temporal reasoning: A revised report. In Weld, D. S. and de Kleer, J., editors, Readings in Qualitative Reasoning about Physical Systems, pages 373–381. Morgan Kaufmann, San Mateo, CA.

  Google Scholar 

• Whitehead, Alfred N. (1929). Process and Reality. The MacMillan Company, New York.

  Google Scholar 

Download references