×

A condensed semantics for qualitative spatial reasoning about oriented straight line segments. (English) Zbl 1252.68278

Summary: More than 15 years ago, a set of qualitative spatial relations between oriented straight line segments (dipoles) was suggested by Schlieder. However, it turned out to be difficult to establish a sound constraint calculus based on these relations. In this paper, we present the results of a new investigation into dipole constraint calculi which uses algebraic methods to derive sound results on the composition of relations of dipole calculi. This new method, which we call condensed semantics, is based on an abstract symbolic model of a specific fragment of our domain. It is based on the fact that qualitative dipole relations are invariant under orientation preserving affine transformations.
The dipole calculi allow for a straightforward representation of prototypical reasoning tasks for spatial agents. As an example, we show how to generate survey knowledge from local observations in a street network. The example illustrates the fast constraint-based reasoning capabilities of dipole calculi. We integrate our results into two reasoning tools which are publicly available.

MSC:

68T27 Logic in artificial intelligence
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Allen, J. F., Maintaining knowledge about temporal intervals, Comm. ACM, 832-843 (1983) · Zbl 0519.68079
[2] B. Bennett, O. Bennett, A. Isli, A.G. Cohn, When does a composition table provide a complete and tractable proof procedure for a relational constraint language?, in: Proc. of the IJCAI97 Workshop on Spatial and Temporal Reasoning, 1997.; B. Bennett, O. Bennett, A. Isli, A.G. Cohn, When does a composition table provide a complete and tractable proof procedure for a relational constraint language?, in: Proc. of the IJCAI97 Workshop on Spatial and Temporal Reasoning, 1997.
[3] Clementini, E.; Felice, P. D.; Hernandez, D., Qualitative representation of positional information, Artificial Intelligence, 95, 317-356 (1997) · Zbl 0894.68143
[4] Cohn, A. G., Qualitative spatial representation and reasoning techniques, (Brewka, G.; Habel, C.; Nebel, B., Proc. of KI-97. Proc. of KI-97, Lecture Notes in Artificial Intelligence, vol. 1303 (1997), Springer-Verlag), 1-30 · Zbl 0974.68206
[5] Coxeter, H. S.M., Self-dual configurations and regular graphs, Bull. Amer. Math. Soc., 56, 413-455 (1950) · Zbl 0040.22803
[6] M. Cristani, Reasoning about qualitative relations between straight lines, Tech. rep., University of Verona, 2003.; M. Cristani, Reasoning about qualitative relations between straight lines, Tech. rep., University of Verona, 2003.
[7] F. Dylla, L. Frommberger, J.O. Wallgrün, D. Wolter, S. Wölfl, B. Nebel, SailAway: Formalizing navigation rules, in: Proc. of the AISBʼ07 Artificial and Ambient Intelligence Symposium on Spatial Reasoning and Communication, 2007.; F. Dylla, L. Frommberger, J.O. Wallgrün, D. Wolter, S. Wölfl, B. Nebel, SailAway: Formalizing navigation rules, in: Proc. of the AISBʼ07 Artificial and Ambient Intelligence Symposium on Spatial Reasoning and Communication, 2007.
[8] F. Dylla, R. Moratz, Exploiting qualitative spatial neighborhoods in the situation calculus, in: C. Freksa, M. Knauff, B. Krieg-Brückner, B. Nebel, T. Barkowsky (Eds.), Proc. of Spatial Cognition 2004, 2005, pp. 304-322.; F. Dylla, R. Moratz, Exploiting qualitative spatial neighborhoods in the situation calculus, in: C. Freksa, M. Knauff, B. Krieg-Brückner, B. Nebel, T. Barkowsky (Eds.), Proc. of Spatial Cognition 2004, 2005, pp. 304-322.
[9] Egenhofer, M.; Franzosa, R., Point-set topological spatial relations, Int. J. Geogr. Inform. Syst., 5, 2, 161-174 (1991)
[10] Frank, A., Qualitative spatial reasoning with cardinal directions, (Kaindl, H., Proc. of 7th Österreichische Artificial-Intelligence-Tagung (1991), Springer), 157-167
[11] C. Freksa, Conceptual neighborhood and its role in temporal and spatial reasoning, in: M.G. Singh, L. Travé-Massuyès (Eds.), Proc. of the IMACS Workshop on Decision Support Systems and Qualitative Reasoning, 1991, pp. 181-187.; C. Freksa, Conceptual neighborhood and its role in temporal and spatial reasoning, in: M.G. Singh, L. Travé-Massuyès (Eds.), Proc. of the IMACS Workshop on Decision Support Systems and Qualitative Reasoning, 1991, pp. 181-187.
[12] Freksa, C., Using orientation information for qualitative spatial reasoning, (Frank, A. U.; Campari, I.; Formentini, U., Theories and Methods of Spatial-Temporal Reasoning in Geographic Space (1992), Springer), 162-178
[13] Freksa, C., Using orientation information for qualitative spatial reasoning, (Frank, A. U.; Campari, I.; Formentini, U., Theories and Methods of Spatio-Temporal Reasoning in Geographic Space. Theories and Methods of Spatio-Temporal Reasoning in Geographic Space, Lecture Notes in Comput. Sci., vol. 639 (1992), Springer), 162-178
[14] Gallier, J. H., Curves and Surfaces in Geometric Modeling: Theory and Algorithms (2000), Morgan Kaufmann
[15] Galton, A., Qualitative Spatial Change (2000), Oxford University Press
[16] Z. Gantner, M. Westphal, S. Wölfl, GQR - a fast reasoner for binary qualitative constraint calculi, in: Proc. of the AAAI-08 Workshop on Spatial and Temporal Reasoning, 2008.; Z. Gantner, M. Westphal, S. Wölfl, GQR - a fast reasoner for binary qualitative constraint calculi, in: Proc. of the AAAI-08 Workshop on Spatial and Temporal Reasoning, 2008.
[17] Goodman, J. E.; Pollack, R.; Sturmfels, B., Coordinate representation of order types requires exponential storage, (STOC ʼ89: Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing (1989), ACM: ACM New York, NY, USA), 405-410
[18] R.K. Goyal, M.J. Egenhofer, Similarity of cardinal directions, in: Advances in Spatial and Temporal Databases, 7th International Symposium, SSTD 2001, 2001, pp. 36-58.; R.K. Goyal, M.J. Egenhofer, Similarity of cardinal directions, in: Advances in Spatial and Temporal Databases, 7th International Symposium, SSTD 2001, 2001, pp. 36-58. · Zbl 0997.68632
[19] Grünbaum, B., Arrangements and Spreads, Regional Conference Series in Mathematics, vol. 10 (1972), American Mathematical Society: American Mathematical Society Providence, RI · Zbl 0249.50011
[20] Harrison, J., HOL light: An overview, (Berghofer, S.; Nipkow, T.; Urban, C.; Wenzel, M., Proc. of TPHOLs-09. Proc. of TPHOLs-09, Lecture Notes in Comput. Sci., vol. 5674 (2009), Springer), 60-66 · Zbl 1252.68255
[21] E.G. Hoel, H. Samet, Efficient processing of spatial queries in line segment databases, in: O. Günter, H.-J. Schek (Eds.), Proc. of the 2nd Symp. on Large Spatial Databases (SSDʼ91), Zürich, 1991, pp. 237-255.; E.G. Hoel, H. Samet, Efficient processing of spatial queries in line segment databases, in: O. Günter, H.-J. Schek (Eds.), Proc. of the 2nd Symp. on Large Spatial Databases (SSDʼ91), Zürich, 1991, pp. 237-255.
[22] Isli, A.; Cohn, A. G., A new approach to cyclic ordering of 2D orientations using ternary relation algebras, Artificial Intelligence, 122, 1-2, 137-187 (2000) · Zbl 0948.68170
[23] A. Isli, R. Moratz, Qualitative spatial representation and reasoning: algebraic models for relative position, Tech. rep., Universität Hamburg, FB Informatik, Hamburg, 1999.; A. Isli, R. Moratz, Qualitative spatial representation and reasoning: algebraic models for relative position, Tech. rep., Universität Hamburg, FB Informatik, Hamburg, 1999.
[24] Ladkin, P.; Maddux, R., On binary constraint problems, J. ACM, 41, 3, 435-469 (1994) · Zbl 0813.03045
[25] Levinson, S. C., Frames of reference and Molyneuxʼs question: Crosslinguistic evidence, (Bloom, P.; Peterson, M.; Nadel, L.; Garrett, M., Language and Space (1996), MIT Press), 109-169
[26] Li, S.; Ying, M., Region connection calculus: Its models and composition table, Artificial Intelligence, 145, 1-2, 121-146 (2003) · Zbl 1082.68821
[27] Ligozat, G., Qualitative triangulation for spatial reasoning, (Frank, A. U.; Campari, I., Proc. International Conference on Spatial Information Theory. Proc. International Conference on Spatial Information Theory, Lecture Notes in Comput. Sci., vol. 716 (1993), Springer), 54-68
[28] Ligozat, G., Reasoning about cardinal directions, J. Vis. Lang. Comput., 9, 1, 23-44 (1998)
[29] G. Ligozat, J. Renz, What is a qualitative calculus? A general framework, in: C. Zhang, H.W. Guesgen, W.-K. Yeap (Eds.), Proc. of PRICAI-04, 2004, pp. 53-64.; G. Ligozat, J. Renz, What is a qualitative calculus? A general framework, in: C. Zhang, H.W. Guesgen, W.-K. Yeap (Eds.), Proc. of PRICAI-04, 2004, pp. 53-64.
[30] Lücke, D.; Mossakowski, T.; Wolter, D., Qualitative reasoning about convex relations, (Freksa, C.; Newcombe, N. S.; Gaerdenfors, P., Spatial Cognition VI 2008. Spatial Cognition VI 2008, Lecture Notes in Computer Science, vol. 5248 (2008), Springer), 426-440
[31] Mackworth, A. K., Consistency in networks of relations, Artificial Intelligence, 8, 99-118 (1977) · Zbl 0341.68061
[32] Maddux, R., Relation Algebras, Stud. Logic Found. Math. (2006), Elsevier Science · Zbl 1197.03051
[33] Montanari, U., Networks of constraints: Fundamental properties and applications to picture processing, Inform. Sci., 7, 95-132 (1974) · Zbl 0284.68074
[34] Moratz, R., Representing relative direction as a binary relation of oriented points, (Brewka, G.; Coradeschi, S.; Perini, A.; Traverso, P., Proc. of ECAI-06. Proc. of ECAI-06, Frontiers in Artificial Intelligence and Applications, vol. 141 (2006), IOS Press), 407-411
[35] Moratz, R.; Ragni, M., Qualitative spatial reasoning about relative point position, J. Vis. Lang. Comput., 19, 1, 75-98 (2008)
[36] R. Moratz, J. Renz, D. Wolter, Qualitative spatial reasoning about line segments, in: Proc. of ECAI 2000, 2000, pp. 234-238.; R. Moratz, J. Renz, D. Wolter, Qualitative spatial reasoning about line segments, in: Proc. of ECAI 2000, 2000, pp. 234-238.
[37] Moratz, R.; Tenbrink, T., Spatial reference in linguistic human-robot interaction: Iterative, empirically supported development of a model of projective relations, Spatial Cogn. Comput., 6, 1, 63-107 (2006)
[38] F. Mossakowski, Algebraische Eigenschaften qualitativer Constraint-Kalküle, Masterʼs thesis, Universität Bremen, 2007.; F. Mossakowski, Algebraische Eigenschaften qualitativer Constraint-Kalküle, Masterʼs thesis, Universität Bremen, 2007.
[39] T. Mossakowski, S. Wölfl, An algebraic charaterisation of qualitative spatial and temporal calculi, unpublished results.; T. Mossakowski, S. Wölfl, An algebraic charaterisation of qualitative spatial and temporal calculi, unpublished results.
[40] A. Musto, K. Stein, A. Eisenkolb, T. Röfer, Qualitative and quantitative representations of locomotion and their application in robot navigation, in: Proc. of IJCAI-99, 1999, pp. 1067-1072.; A. Musto, K. Stein, A. Eisenkolb, T. Röfer, Qualitative and quantitative representations of locomotion and their application in robot navigation, in: Proc. of IJCAI-99, 1999, pp. 1067-1072.
[41] Nebel, B.; Bürckert, H.-J., Reasoning about temporal relations: A maximal tractable subclass of Allenʼs interval algebra, J. ACM, 42, 43-66 (1995) · Zbl 0886.68077
[42] B. Nebel, S. Wölfl (Eds.), AAAI Spring Symposium on Benchmarking of Qualitative Spatial and Temporal Reasoning Systems, AAAI Technical Report SS-09-02, 2009.; B. Nebel, S. Wölfl (Eds.), AAAI Spring Symposium on Benchmarking of Qualitative Spatial and Temporal Reasoning Systems, AAAI Technical Report SS-09-02, 2009.
[43] Nipkow, T.; Paulson, L. C.M.; Wenzel, M., Isabelle/HOL — A Proof Assistant for Higher-Order Logic (2002), Springer · Zbl 0994.68131
[44] Randell, D. A.; Cohn, A. G., Modelling topological and metrical properties of physical processes, (Brachman, R. J.; Levesque, H. J.; Reiter, R., Proc. of KR-89 (1989), Morgan Kaufmann), 357-368 · Zbl 0709.68093
[45] Randell, D. A.; Cui, Z.; Cohn, A. G., A spatial logic based on regions and connection, (Nebel, B.; Rich, C.; Swartout, W., Proc. of KR-92 (1992), Morgan Kaufmann), 165-176
[46] Renz, J., Qualitative Spatial Reasoning with Topological Information (2002), Springer · Zbl 0999.68206
[47] Renz, J.; Ligozat, G., Weak composition for qualitative spatial and temporal reasoning, (van Beek, P., Proc. of CP-05. Proc. of CP-05, Lecture Notes in Comput. Sci., vol. 3709 (2005), Springer), 534-548 · Zbl 1153.68482
[48] Renz, J.; Mitra, D., Qualitative Direction Calculi with Arbitrary Granularity, (Zhang, C.; Guesgen, H. W.; Yeap, W.-K., Proc. of PRICAI-04. Proc. of PRICAI-04, Lecture Notes in Comput. Sci., vol. 3157 (2004), Springer), 65-74
[49] Renz, J.; Nebel, B., On the complexity of qualitative spatial reasoning: A maximal tractable fragment of the region connection calculus, Artificial Intelligence, 108, 1-2, 69-123 (1999) · Zbl 0914.68160
[50] Renz, J.; Nebel, B., Qualitative spatial reasoning using constraint calculi, (Aiello, M.; Pratt-Hartmann, I.; van Benthem, J., Handbook of Spatial Logics (2007), Springer), 161-215
[51] Renz, J.; Schmid, F., Customizing qualitative spatial and temporal calculi, (Orgun, M. A.; Thornton, J., Proc. of Australian Conference on Artificial Intelligence. Proc. of Australian Conference on Artificial Intelligence, Lecture Notes in Comput. Sci., vol. 4830 (2007), Springer), 293-304
[52] Röhrig, R., Representation and processing of qualitative orientation knowledge, (Brewka, G.; Habel, C.; Nebel, B., Proc. of KI-97. Proc. of KI-97, Lecture Notes in Artificial Intelligence, vol. 1303 (1997), Springer), 219-230
[53] Schlieder, C., Reasoning about ordering, (Frank, A.; Kuhn, W., Spatial Information Theory: A Theoretical Basis for GIS. Spatial Information Theory: A Theoretical Basis for GIS, Lecture Notes in Comput. Sci., vol. 988 (1995), Springer: Springer Berlin), 341-349
[54] Scivos, A.; Nebel, B., The finest of its class: The natural point-based ternary calculus for qualitative spatial reasoning, (Freksa, C.; Knauff, M.; Brückner, B. K.; Nebel, B.; Barkowski, T., Spatial Cognition. Spatial Cognition, Lecture Notes in Comput. Sci., vol. 3343 (2004), Springer), 283-303
[55] Skiadopoulos, S.; Koubarakis, M., Composing cardinal direction relations, Artificial Intelligence, 152, 143-171 (2004) · Zbl 1082.68108
[56] T. Soller, Spezifikation und Integration von qualitativem Orientierungswissen, Masterʼs thesis, Universität Bremen, 2005.; T. Soller, Spezifikation und Integration von qualitativem Orientierungswissen, Masterʼs thesis, Universität Bremen, 2005.
[57] van Beek, P.; Manchak, D. W., The design and experimental analysis of algorithms for temporal reasoning, J. Artificial Intelligence Res., 4, 1-18 (1996) · Zbl 0900.68389
[58] J.O. Wallgrün, L. Frommberger, F. Dylla, D. Wolter, SparQ User Manual v0.7, University of Bremen, January 2009.; J.O. Wallgrün, L. Frommberger, F. Dylla, D. Wolter, SparQ User Manual v0.7, University of Bremen, January 2009.
[59] Wallgrün, J. O.; Frommberger, L.; Wolter, D.; Dylla, F.; Freksa, C., Qualitative spatial representation and reasoning in the SparQ-Toolbox, (Barkowsky, T.; Knauff, M.; Ligozat, G.; Montello, D. R., Spatial Cognition. Spatial Cognition, Lecture Notes in Comput. Sci., vol. 4387 (2006), Springer), 39-58
[60] M. Westphal, S. Wölfl, Qualitative CSP, finite CSP, and SAT: Comparing methods for qualitative constraint-based reasoning, in: C. Boutilier (Ed.), IJCAI, 2009, pp. 628-633.; M. Westphal, S. Wölfl, Qualitative CSP, finite CSP, and SAT: Comparing methods for qualitative constraint-based reasoning, in: C. Boutilier (Ed.), IJCAI, 2009, pp. 628-633.
[61] D. Wolter, L.J. Latecki, Shape matching for robot mapping, in: C. Zhang, H.W. Guesgen, W.K. Yeap (Eds.), Proc. of 8th Pacific Rim International Conference on Artificial Intelligence, 2004, pp. 693-702.; D. Wolter, L.J. Latecki, Shape matching for robot mapping, in: C. Zhang, H.W. Guesgen, W.K. Yeap (Eds.), Proc. of 8th Pacific Rim International Conference on Artificial Intelligence, 2004, pp. 693-702.
[62] Wolter, D.; Lee, J. H., On qualitative reasoning about relative point position, Artificial Intelligence, 174, 1498-1507 (2010) · Zbl 1210.68112
[63] D. Wolter, L. Moshagen, Algebraic methods for analyzing qualitative spatio-temporal calculi, in: Proc. of ECAI-Workshop Spatial and Temporal Reasoning, 2008.; D. Wolter, L. Moshagen, Algebraic methods for analyzing qualitative spatio-temporal calculi, in: Proc. of ECAI-Workshop Spatial and Temporal Reasoning, 2008.
[64] Worboys, M. F.; Clementini, E., Integration of imperfect spatial information, J. Vis. Lang. Comput., 12, 61-80 (2001)
[65] Zimmermann, K.; Freksa, C., Qualitative spatial reasoning using orientation, distance, and path knowledge, Appl. Intelligence, 6, 49-58 (1996)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.