Department of Computer Science, Freiburg University
FAST-QUAL-SPACE 
Representation and efficient processing of rich qualitative spatial information
Project leader: Prof. Dr. Bernhard Nebel
Project member: Dipl. Inform. Jochen Renz
Student members: Ronny Fehling, Thilo Weigel
Abstract
In this project, we work on the formal foundations of qualitative
spatial representations and on the development of efficient inference
methods in this area. Starting from existing approaches, we intend to
increase the expressiveness of existing formalisms, we work on
questions concerning soundness and completeness, and on the
determination of computational complexity of inference problems. Based
on that, we will develop inference methods, implement them, and
evaluate them empircally. The theoretical results will be used in
psychological experiments we design and conduct together with the
Cognitive Science group MEMOSPACE
at the Institut für Informatik und Gesellschaft. Applications
of qualitative spatial reasoning can be found in areas such as natural
language processing, document analysis, geographic information systems
and robot navigation.
Publications:
- B. Nebel, H.-J. Bürckert, Reasoning about Temporal Relations: A Maximal Tractable Subclass of Allen's Interval Algebra, Journal of the ACM, 42(1): 43-66, 1995.
(gzip'ed postscript file)
- B. Nebel, Computational Properties of Qualitative Spatial
Reasoning: First Results, in: I. Wachsmuth,
C.-R. Rollinger, W. Brauer (eds.), KI-95: Advances in
Artificial Intelligence, Bielefeld, September 1995,
Springer-Verlag, 233-244.
(gzip'ed postscript file)
- B. Nebel, Solving Hard Qualitative Temporal Reasoning Problems:
Evaluating the Efficiency of Using the ORD-Horn Class,
CONSTRAINTS, 1(3): 175-190, 1997
(gzip'ed postscript file)
- J. Renz and B. Nebel, On the Complexity of Qualitative Spatial
Reasoning: A Maximal Tractable Fragment of the Region
Connection Calculus, Proceedings of the 15th
International Joint Conference on Artificial Intelligence
(IJCAI'97), August 1997, 522-527.
(gzip'ed postscript file) (Extended version presented at QR97)
- M. Knauff, R. Rauh, and J. Renz, A Cognitive Assessment of
Topological Spatial Relations: Results from an Empirical
Investigation, Proceedings of the 3rd International
Conference on Spatial Information Theory (COSIT'97),
October 1997. (gzip'ed postscript file)
-
M. Knauff, J. Renz, R. Rauh, Empirische Ergebnisse zur
konzeptuellen Adäquatheit topologischer
Relationensysteme, in: U. Kotkamp, W. Krause (eds.)
Intelligente Informationsverarbeitung, Deutscher
Universitätsverlag, Wiesbaden, 1998. (gzip'ed postscript file)
-
J. Renz, A Canonical Model of the Region Connection Calculus, in A.G. Cohn, L. Schubert, S.C. Shapiro (eds.)
Principles of Knowledge Representation and Reasoning, Proceedings
of the 6th International Conference (KR'98),
Trento, Italy, June 1998, 330-341. (gzip'ed postscript file)
-
J. Renz, B. Nebel, Spatial Reasoning with Topological
Information, in: C. Freksa, C. Habel, K.F. Wender
(eds.), Spatial Cognition - An interdisciplinary approach
to representation and processing of spatial knowledge,
LNCS 1404, Springer-Verlag, Berlin, 1998.(gzip'ed postscript file)
-
J. Renz, B. Nebel, Efficient Methods for Qualitative Spatial Reasoning, Proceedings of the 13th European Conference on Artificial Intelligence (ECAI'98), August 1998, 562-566. (gzip'ed postscript file)(gzip'ed tar-archive of C-programs used for the evaluation 25k) (gzip'ed tar-archive of hard instances 300k)
-
A. Gerevini, J. Renz, Combining Topological and Qualitative Size Constraints for Spatial Reasoning, in Proceedings of the Fourth International Conference on Principles and Practice of Constraint Programming (CP'98), October 1998.
(gzip'ed postscript file (slightly revised), ©Springer-Verlag)
-
J. Renz, B. Nebel, On the Complexity of Qualitative Spatial Reasoning:
A Maximal Tractable Fragment of the Region Connection Calculus,
Artificial Intelligence, 108(1-2):
69-123, 1999. (gzip'ed postscript file)
- J. Renz, Maximal Tractable Fragments of the Region Connection Calculus: A Complete Analysis, in: Proceedings of the 16th International Joint Conference on Artificial Intelligence (IJCAI'99), Stockholm, Sweden, August 1999. (gzip'ed postscript file)
-
J. Renz, R. Rauh, M. Knauff, Towards Cognitive Adequacy of Topological Spatial Relations, in: C. Freksa, W. Brauer, C. Habel, K.F. Wender, eds., Spatial Cognition II - Integrating abstract theories, empirical studies, formal models, and practical applications, LNCS 1849, Springer-Verlag, Berlin, 2000. (gzip'ed postscript file)
-
R. Moratz, J. Renz, and D. Wolter, Qualitative Spatial Reasoning about Line Segments, to appear in the 14th European Conference on Artificial Intelligence (ECAI'00), Berlin, Germany, August 2000. (gzip'ed postscript file)
-
M. Broxvall, P. Jonsson, and J. Renz, Refinements and Independence: A Simple Method for Identifying Tractable Disjunctive Constraints, to appear in the Sixth International Conference on Principles and Practice of Constraint Programming (CP'00), Singapore, September 2000.
-
A. Scivos, B. Nebel, Double-Crossing: Decidability and
Computational Complexity of a Qualitative Calculus for Navigation,
Proc. COSIT-2001, Springer-Verlag, 2001 (gzip'ed postscript file) (PDF file)
-
J. Renz, B. Nebel, Efficient Methods for Qualitative Spatial Reasoning, Journal for Artificial Intelligence Research (JAIR), to appear, 2001. (gzip'ed postscript file)
Other publications about RCC:
sppraum@informatik.uni-freiburg.de, October 9, 2001