Startseite des Instituts für Informatik, Universität Freiburg

FAST-QUAL-SPACE

Repräsentation und effiziente Verarbeitung reichhaltiger qualitativer räumlicher Information

Forschungsprojekt im Schwerpunktprogramm Raumkognition der Deutschen Forschungsgemeinschaft

Projektleiter: Prof. Dr. Bernhard Nebel
Projektmitarbeiter: Dipl. Inform. Jochen Renz
Studentische Hilfskräfte: Ronny Fehling, Thilo Weigel

Zusammenfassung:

Gegenstand des Forschungsvorhabens ist die Weiterentwicklung der formalen Grundlagen qualitativer räumlicher Repräsentationsmethoden und die Entwicklung effizienter Inferenzmethoden für das qualitative räumliche Schließen. Dabei sollen die vorhandenen Ansätze zur formalen Semantik dieser Kalküle weiterentwickelt und die Ausdruckskraft vorhandener Kalkül erhöht werden, es sollen Fragestellungen der Korrektheit und Vollständigkeit qualitativer räumlicher Kalküle untersucht und ihre Berechenbarkeitskomplexität bestimmt werden. Aufbauend darauf sollen effiziente Inferenzverfahren entwickelt, implementiert und evaluiert werden. Die theoretischen Ergebnisse werden in kognitionspsychologische Untersuchungen einfließen, die in Kooperation mit dem DFG-Projekt MEMOSPACE durchgeführt werden, und umgekehrt sollen die dabei gewonnenen Resultate in die theoretischen Untersuchungen einfließen. Anwendungen ergeben sich bei der Verarbeitung natürlicher Sprache, der Dokumentenanalyse, bei geographischen Informationssysteme und bei der Roboternavigation.

Publikationen:

• 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)

Sonstige Publikationen zu RCC:

• Leeds QSR Group Publications