A Qualitative Trajectory Calculus and the Composition of Its Relations | SpringerLink
Skip to main content
Springer Nature Link
Log in

A Qualitative Trajectory Calculus and the Composition of Its Relations

  • Conference paper
GeoSpatial Semantics (GeoS 2005)

Part of the book series: Lecture Notes in Computer Science ((LNISA,volume 3799))

Included in the following conference series:

  • 867 Accesses

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.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Allen, J.F.: Maintaining Knowledge about Temporal Intervals. Communications of the ACM 26(11), 832–843 (1983)

    Article  MATH  Google Scholar 

  2. Freksa, C.: Temporal Reasoning Based on Semi Intervals. Artificial Intelligence 54, 199–227 (1992)

    Article  MathSciNet  Google Scholar 

  3. Cohn, A.G., Hazarika, S.M.: Qualitative Spatial Representation and Reasoning: An Overview. Fundamenta Informaticae 46(1–2), 1–29 (2001)

    MATH  MathSciNet  Google Scholar 

  4. Wolfson, O., Xu, B., Chamberlain, S., Jiang, L.: Moving Object Databases: Issues and Solutions. In: Proc. of SSDBM, Capri, Italy, pp. 111–122 (1998)

    Google Scholar 

  5. 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)

    Article  Google Scholar 

  6. 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)

    Article  Google Scholar 

  7. Nabil, M., Ngu, A., Shepherd, A.J.: Modelling and Retrieval of Moving Objects. Multimedia Tools and Applications 13, 35–71 (2001)

    Article  MATH  Google Scholar 

  8. Pfoser, D.: Indexing the Trajectories of Moving Objects. IEEE Data Engineering Bulletin 25(2), 3–9 (2002)

    Google Scholar 

  9. 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)

    Google Scholar 

  10. Galton, A.: Qualitative Spatial Change, p. 409. University Press, Oxford (2000)

    Google Scholar 

  11. 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)

    Article  Google Scholar 

  12. Claramunt, C., Jiang, B.: An Integrated Representation of Spatial and Temporal Relationships between Evolving Regions. Geographical Systems 3(4), 411–428 (2001)

    Article  Google Scholar 

  13. 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)

    Google Scholar 

  14. 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)

    Google Scholar 

  15. Egenhofer, M., Franzosa, R.: Point Set Topological Spatial Relations. International Journal of Geographical Information Systems 5(2), 161–174 (1991)

    Article  Google Scholar 

  16. 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)

    Google Scholar 

  17. 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)

    Google Scholar 

  18. 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)

    Google Scholar 

  19. 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)

    Google Scholar 

  20. 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)

    Google Scholar 

  21. Vieu, L.: Spatial Representation and Reasoning in Artificial Intelligence. In: Stock, O. (ed.) Spatial and Temporal Reasoning, pp. 5–41. Kluwer, Dordrecht (1997)

    Chapter  Google Scholar 

  22. Bennett, B.: Logical Representations for Automated Reasoning about Spatial Relationships, PhD thesis, UK, University of Leeds, School of Computer Studies, p. 211 (1997)

    Google Scholar 

  23. 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)

    Google Scholar 

  24. 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)

    Google Scholar 

  25. 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)

    Google Scholar 

  26. 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)

    Google Scholar 

  27. Frank, A.U.: Qualitative Spatial reasoning: Cardinal Directions as an Example. International Journal of Geographical Information Science 10(3), 269–290 (1996)

    Article  Google Scholar 

  28. 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)

    Google Scholar 

  29. Mukerjee, A., Joe, G.: A qualitative Model for Space. In: Proc. of AAAI, Los Altos, USA, pp. 721–727 (1990)

    Google Scholar 

  30. 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)

    Google Scholar 

  31. Hernández, D.: Qualitative Representation of Spatial Knowledge. LNCS (LNAI), vol. 804, p. 202. Springer, Heidelberg (1994)

    Book  MATH  Google Scholar 

  32. Schlieder, C.: Reasoning about Ordering. In: Kuhn, W., Frank, A.U. (eds.) COSIT 1995. LNCS, vol. 988, pp. 341–349. Springer, Heidelberg (1995)

    Google Scholar 

  33. Hernández, D., Jungert, E.: Qualitative Motion of Point-Like Objects. Journal of Visual Languages and Computing 10, 269–289 (1999)

    Article  Google Scholar 

  34. 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)

    Google Scholar 

  35. 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)

    Google Scholar 

  36. 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)

    Article  Google Scholar 

  37. Nabil, M., Ngu, A., Shepherd, A.J.: Modelling and Retrieval of Moving Objects. Multimedia Tools and Applications 13(1), 35–71 (2001)

    Article  MATH  Google Scholar 

  38. Hornsby, K., Egenhofer, M.: Modelling Moving Objects over Multiple Granularities. Annals of Mathematics and Artificial Intelligence 36(1–2), 177–194 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  39. 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)

    Chapter  Google Scholar 

  40. Du Mouza, C., Rigaux, P.: Multi-Scale Classification of Moving Object Trajectories. In: Proc. of SSDBM, Santorini Island, Greece, pp. 307–316 (2004)

    Google Scholar 

  41. 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)

    Chapter  Google Scholar 

  42. 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)

    Google Scholar 

  43. Worboys, M.: Event-Oriented Approaches to Geographic Phenomena. International Journal of Geographical Information Science 19(1), 1–28 (2005)

    Article  Google Scholar 

  44. 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)

    Google Scholar 

  45. Zimmermann, K., Freksa, C.: Qualitative Spatial Reasoning Using Orientation, Distance, and Path Knowledge. Applied Intelligence 6, 49–58 (1996)

    Article  Google Scholar 

  46. Kulpa, Z.: Diagrammatic Representation for a Space of Intervals. Machine Graphics and Vision 6(1), 5–24 (1997)

    MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Geography, Ghent University, Krijgslaan 281 (S8), B-9000, Ghent, Belgium

    Nico Van de Weghe, Peter Bogaert & Philippe De Maeyer

  2. Theoretical Computer Science Group, Hasselt University, Agoralaan, Gebouw D, B-3590, Diepenbeek, Belgium

    Bart Kuijpers

Authors
  1. Nico Van de Weghe
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Bart Kuijpers
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Peter Bogaert
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Philippe De Maeyer
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Center for Web Research, Chile

    M. Andrea Rodríguez

  2. Department of Computer Science, University of Illinois at Chicago, 851 South Morgan Street (M/C 152), 60607, Chicago, IL, USA

    Isabel Cruz

  3. National Polytechnic, Institute, Mexico, Centro de Investigacion en Computacion, Mexico

    Sergei Levashkin

  4. National Center for Geographic Information and Analysis and Department of Spatial Information Science and Engineering, University of Maine, Boardman Hall, 04469-5711, Orono, ME, USA

    Max J. Egenhofer

Rights and permissions

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

Publish with us

Policies and ethics

Search

Navigation