Abstract
Continuously moving objects are prevalent in many domains. Although there have been attempts to combine both spatial and temporal relationships from a reasoning, a database, as well as from a logical perspective, the question remains how to describe motion adequately within a qualitative calculus. In this paper, a Qualitative Trajectory Calculus (QTC) for representing and reasoning about moving objects in two dimensions is presented. Specific attention is given to a central concept in qualitative reasoning, namely the composition of relations. The so-called composition-rule table is presented, which is a neat way of representing a composition table. The usefulness of QTC and the composition-rule table is illustrated by an example.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Allen, J.F.: Maintaining Knowledge about Temporal Intervals. Communications of the ACM 26(11), 832–843 (1983)
Freksa, C.: Temporal Reasoning Based on Semi Intervals. Artificial Intelligence 54, 199–227 (1992)
Cohn, A.G., Hazarika, S.M.: Qualitative Spatial Representation and Reasoning: An Overview. Fundamenta Informaticae 46(1–2), 1–29 (2001)
Wolfson, O., Xu, B., Chamberlain, S., Jiang, L.: Moving Object Databases: Issues and Solutions. In: Proc. of SSDBM, Capri, Italy, pp. 111–122 (1998)
Erwig, M., Güting, R.H., Schneider, M., Vazirgiannis, M.: Spatio Temporal Data Types: An Approach to Modelling Objects in Databases. Geoinformatica 3(3), 269–296 (1999)
Moreira, J., Ribeiro, C., Saglio, J.M.: Representation and Manipulation of Moving Points: An Extended Data Model for Location Estimation. Cartography and Geographic Information Systems 26(2), 109–123 (1999)
Nabil, M., Ngu, A., Shepherd, A.J.: Modelling and Retrieval of Moving Objects. Multimedia Tools and Applications 13, 35–71 (2001)
Pfoser, D.: Indexing the Trajectories of Moving Objects. IEEE Data Engineering Bulletin 25(2), 3–9 (2002)
Muller, P.: A Qualitative Theory of Motion Based on Spatiotemporal Primitives. In: Cohn, A.G., Schubert, L., Shapiro, S. (eds.) Proc. of KR, Trento, Italy, pp. 131–142 (1998)
Galton, A.: Qualitative Spatial Change, p. 409. University Press, Oxford (2000)
Hornsby, K., Egenhofer, M.: Identity Based Change: A Foundation for Spatio Temporal Knowledge Representation. International Journal of Geographical Information Science 14(3), 207–224 (2000)
Claramunt, C., Jiang, B.: An Integrated Representation of Spatial and Temporal Relationships between Evolving Regions. Geographical Systems 3(4), 411–428 (2001)
Hazarika, S.M., Cohn, A.G.: Qualitative Spatio Temporal Continuity. In: Montello, D.R. (ed.) COSIT 2001. LNCS, vol. 2205, pp. 92–107. Springer, Heidelberg (2001)
Randell, D., Cui, Z., Cohn, A.G.: A Spatial Logic Based on Regions and Connection. In: Nebel, B., Swartout, W., Rich, C. (eds.) Proc. of KR, San Mateo, USA, pp. 165–176 (1992)
Egenhofer, M., Franzosa, R.: Point Set Topological Spatial Relations. International Journal of Geographical Information Systems 5(2), 161–174 (1991)
Van de Weghe, N.: Representing and Reasoning about Moving Objects: A Qualitative Approach, PhD thesis, Belgium, Ghent University, Faculty of Sciences, Department of Geography, pp. 268 (2004)
Van de Weghe, N., Cohn, A.G., Bogaert, P., De Maeyer, P.: Representation of Moving Objects along a Road Network. In: Proc. of Geoinformatics, Gävle, Sweden, pp. 187–197 (2004)
Bogaert, P., Van de Weghe, N., De Maeyer, P.: Description, Definition and Proof of a Qualitative State Change of Moving Objects along a Road Network. In: Raubal, M., Sliwinski, A., Kuhn, W. (eds.) Proc. of the Münster GI Days. Geoinformation and Mobility, from Research to Applications, Münster, Germany, pp. 239–248 (2004)
Van de Weghe, N., Cohn, A.G., De Maeyer, P., Witlox, F.: Representing Moving Objects in Computer-Based Expert Systems: The Overtake Event Example. Expert Systems with Applications 29(4) (2005) (Accepted for publication)
Freksa, C., Zimmermann, K.: On the Utilization of Spatial Structures for Cognitively Plausible and Efficient Reasoning. In: Proc. of the Conf. on Systems, Man, and Cybernetics, Chicago, USA, pp. 261–266 (1992)
Vieu, L.: Spatial Representation and Reasoning in Artificial Intelligence. In: Stock, O. (ed.) Spatial and Temporal Reasoning, pp. 5–41. Kluwer, Dordrecht (1997)
Bennett, B.: Logical Representations for Automated Reasoning about Spatial Relationships, PhD thesis, UK, University of Leeds, School of Computer Studies, p. 211 (1997)
Goyal, R.K.: Similarity Assessment for Cardinal Directions Between Extended Spatial Objects, PhD thesis, USA, University of Maine, Graduate School, Spatial Information Science and Engineering, p. 167 (2000)
Randell, D.A., Cohn, A.G.: Modelling Topological and Metrical Properties of Physical Processes. In: Brachman, R., Levesque, H., Reiter, R. (eds.) Proc. of KR, Toronto, Canada, pp. 55–66 (1989)
Egenhofer, M.: Reasoning about Binary Topological Relations. In: Günther, O., Schek, H.-J. (eds.) SSD 1991. LNCS, vol. 525, pp. 143–160. Springer, Heidelberg (1991)
Zimmermann, K., Freksa, C.: Enhancing Spatial reasoning by the Concept of Motion. In: Sloman, A., Hogg, D., Humphreys, A., Ramsay, A., Partridge, D. (eds.) Proc. of AISB, Birmingham, UK, pp. 140–147 (1993)
Frank, A.U.: Qualitative Spatial reasoning: Cardinal Directions as an Example. International Journal of Geographical Information Science 10(3), 269–290 (1996)
Gooday, J.M., Cohn, A.G.: Conceptual Neighbourhoods in Temporal and Spatial Reasoning. In: Rodriguez, R. (ed.) Proc. of the ECAI Spatial and Temporal Reasoning Workshop, Amsterdam, Netherlands (1994)
Mukerjee, A., Joe, G.: A qualitative Model for Space. In: Proc. of AAAI, Los Altos, USA, pp. 721–727 (1990)
Jungert, E.: The Observer’s Point of View: an Extension of Symbolic Projections. In: Frank, A.U., Formentini, U., Campari, I. (eds.) GIS 1992. LNCS, vol. 639, pp. 179–195. Springer, Heidelberg (1992)
Hernández, D.: Qualitative Representation of Spatial Knowledge. LNCS (LNAI), vol. 804, p. 202. Springer, Heidelberg (1994)
Schlieder, C.: Reasoning about Ordering. In: Kuhn, W., Frank, A.U. (eds.) COSIT 1995. LNCS, vol. 988, pp. 341–349. Springer, Heidelberg (1995)
Hernández, D., Jungert, E.: Qualitative Motion of Point-Like Objects. Journal of Visual Languages and Computing 10, 269–289 (1999)
Musto, A., Eisenkolb, A., Röfer, T., Stein, K.: Qualitative and Quantitative Representations of Locomotion and their Application in Robot Navigation. In: Proc. of IJCAI, San Francisco, USA, pp. 1067–1073 (1999)
Sogo, T., Ishiguro, H., Ishida, T.: Acquisition of Qualitative Spatial Representation by Visual Observation. In: Proc. of IJCAI, San Francisco, USA, pp. 1054–1060 (1999)
Fernyhough, J.H., Cohn, A.G., Hogg, D.C.: Constructing Qualitative Event Models Automatically from Video Input. Image and Vision Computing 18(2), 81–103 (2000)
Nabil, M., Ngu, A., Shepherd, A.J.: Modelling and Retrieval of Moving Objects. Multimedia Tools and Applications 13(1), 35–71 (2001)
Hornsby, K., Egenhofer, M.: Modelling Moving Objects over Multiple Granularities. Annals of Mathematics and Artificial Intelligence 36(1–2), 177–194 (2002)
Stolzenburg, F., Obst, O., Murray, J.: Qualitative Velocity and Ball Interception. In: Jarke, M., Köhler, J., Lakemeyer, G. (eds.) KI 2002. LNCS, vol. 2479, pp. 283–298. Springer, Heidelberg (2002)
Du Mouza, C., Rigaux, P.: Multi-Scale Classification of Moving Object Trajectories. In: Proc. of SSDBM, Santorini Island, Greece, pp. 307–316 (2004)
Dylla, F., Moratz, R.: Exploiting Qualitative Spatial Neighborhoods in the Situation Calculus. In: Freksa, C., Knauff, M., Krieg-Brückner, B., Nebel, B., Barkowsky, T. (eds.) Spatial Cognition IV. LNCS, vol. 3343, pp. 304–322. Springer, Heidelberg (2005)
Parent, C., Spaccapietra, S., Zimanyi, E.: Spatio-Temporal Conceptual Models: Data Structures + Space + Time. In: Proc. of ACM GIS, Kansas City, USA, pp. 26–33 (1999)
Worboys, M.: Event-Oriented Approaches to Geographic Phenomena. International Journal of Geographical Information Science 19(1), 1–28 (2005)
Freksa, C.: Using Orientation Information for Qualitative Spatial Reasoning. In: Frank, A.U., Formentini, U., Campari, I. (eds.) GIS 1992. LNCS, vol. 639, pp. 162–178. Springer, Heidelberg (1992)
Zimmermann, K., Freksa, C.: Qualitative Spatial Reasoning Using Orientation, Distance, and Path Knowledge. Applied Intelligence 6, 49–58 (1996)
Kulpa, Z.: Diagrammatic Representation for a Space of Intervals. Machine Graphics and Vision 6(1), 5–24 (1997)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Van de Weghe, N., Kuijpers, B., Bogaert, P., De Maeyer, P. (2005). A Qualitative Trajectory Calculus and the Composition of Its Relations. In: Rodríguez, M.A., Cruz, I., Levashkin, S., Egenhofer, M.J. (eds) GeoSpatial Semantics. GeoS 2005. Lecture Notes in Computer Science, vol 3799. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11586180_5
Download citation
DOI: https://doi.org/10.1007/11586180_5
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-30288-9
Online ISBN: 978-3-540-32283-2
eBook Packages: Computer ScienceComputer Science (R0)