A qualitative trajectory calculus as a basis for representing moving objects in Geographical Information Systems

• Autorzy: Weghe N. van de , Cohn A. G. , Tre G. de , Maeyer P. de
• Języki publikacji: EN

Abstrakty

EN

Qualitative formalisms, suited to express qualitative temporal or spatial relationships between entities, have gained wide acceptance as a useful way of abstracting from the real world. The question remains how to describe spatio-temporal concepts, such as the interaction between disconnected moving objects, adequately within a qualitative calculus and more specifically how to use this in geographical information systems. In this paper, the Basic Qualitative Trajectory Calculus (QTCB) for representing and reasoning about moving objects is presented. QTCB enables comparisons between positions of objects at different time points ro be made. The calculus is based on few primitives (i.e., distance and speed constraints), making it elegant and theoretically simple. To clarify the way in which trajectories are represented within QTCB: specific cases of movements (e.g. circular movement) are presented. To illustrate the naturalness of QTC, a "predator-prey" example is studied.

Słowa kluczowe

EN

moving objects; qualitative reasoning; qualitative representation; spatio-temporal modelling

PL

obiekt ruchomy; wnioskowanie jakościowe; specyfikacja jakościowa

• Wydawca: Systems Research Institute, Polish Academy of Sciences
• Czasopismo: Control and Cybernetics
• Rocznik: 2006
• Tom: Vol. 35, no 1
• Strony: 97--119
• Opis fizyczny: Bibliogr. 47 poz., rys.

Twórcy

autor

Weghe N. van de

autor

Cohn A. G.

autor

Tre G. de

autor

Maeyer P. de

• Department of Ge, Krijgslaan 281 (S8), B-9000 Gent, Belgium

Bibliografia

• ALLEN, J.F. (1983) Maintaining knowledge about temporal intervals. Communications of the ACM26 (11), 832-843.
• BENNETT, B. (1997) Logical Representations for Automated Reasoning about Spatial Relationships. Unpublished PhD thesis, UK, University of Leeds, School of Computer Studies.
• BOGAERT, P., VAN DE WEGHE, N. and DE MAEYER, PH. (2004) Description, definition and proof of a qualitative state change of moving objects along a road network. In: M. Raubal, A.Sliwinski, W. Kuhn, eds., Proceedings of the Munster GI Days. Miinster, Germany, 239-248.
• BURROUGH, P.A. and McDONNELL, R.A. (1998) Principles of Geographical Information Systems. Oxford University Press, New York, USA.
• CLEMENTINI, E., DI FELICE, P. and HERNANDEZ, D. (1997) Qualitative representation of positional information. Artificial Intelligence 95(2), 31-356.
• COHN, A.G. and HAZARIKA, S.M. (2001) Continuous transitions in mereotopology. Proceedings of the 5th Symposium on Logical Formalizations of Commonsense Reasoning. New York, USA, 71-80.
• COHN, A.G. and HAZARIKA,. S.M. (2001) Qualitative spatial representation and reasoning: an overview. Fundamenta Informaticae 46(1 2), 1-29.
• COHN. A.G. (1995) The challenge of qualitative spatial reasoning. ACM Computing Surveys 27(3), 323-325.
• COHN, A.G. (1996) Calculi for qualitative spatial reasoning. In: J. Calmet, J.A. Campbell and J. Pfaizgraf, eds., Proceedings of the 3rd Conference on Artificial Intelligence and Symbolic Computation, Steyr, Austria. LNCS 1138, Springer Verlag, 124-143.
• DE CALUWE, R., DE TRÉ, G. and BORDOGNA, G., EDS. (2004) Spatio-Temporal Databases. Flexible Querying and Reasoning. Springer Verlag, Heidelberg-Berlin, Germany.
• EGENHOFER, M. and FRANZOSA. R. (1991) Point set topological spatial relations. International Journal of Geographical Information Systems 5(2), 161-174.
• ERWIG, M., GUTING, R.H., SCHNEIDER, M. and VAZIRGIANNIS, M. (1999) Spatio-temporal data types: an approach to modelling objects in databases. Geoinformatica 3(3), 269-296.
• ESCHENBACH, C., HABEL, C. and KULIK, L. (1999) Representing simple trajectories as oriented curves, nave geography. In: A.N. Kumar, I. Russell, eds., Proceedings of the 12th Florida Artificial Intelligence Research Society Conference, Orlando, USA, 431-436.
• FERNYHOUGH, J.H., CORN, A.G. and HOGG, D.C. (2000) Constructing qualitative event models automatically from video input. Image and Vision Computing 18(2), 81-103.
• FRANK, A.U. and CAMPARI, I. (1993) Spatial information theory: theoretical basis for GIS. In: G. Goos and J. Hartmani, eds., LNCS 716, Springer Verlag.
• FRANK, A.U. (1996) Qualitative spatial reasoning: cardinal directions as an example. International Journal of Geographical Information Science 10(3), 269-290.
• FREKSA, C. (1992) Temporal reasoning based on semi intervals. Artificial Intelligence 54, 199-227.
• FREKSA, C. (1992) Using orientation information for qualitative spatial reasoning. In: A.U. Frank, I. Campari, U. Formentini, eds., Proceedings on the Conference on Theories and Methods of spatio-temporal Reasoning in Geographic Space, Pisa, Italy, LNCS 639, Springer Verlag, 162-178.
• GALTON, A.G. (1995) Towards a qualitative theory of movement. In: A.M. Frank, W. Kuhn, eds., Proceedings of the 2nd Conference on Spatial Information Theory, Semmering, Austria, LNCS 988, Springer Verlag, 377-396.
• GOODCHILD, M.F. (1992) Geographical information science. International Journal of Geographical Information Systems 6 (1), 305-314.
• GOODCHILD, M.F., EGENHOFER, M., KEMP, K., MARK, D. and SHEPPARD, E. (1999) Introduction to the Varenius Project. International Journal of Geographical Information Science. 13 (8), 731-745.
• GOYAL, R.K. (2000) Similarity Assessment for Cardinal Directions between Extended Spatial Objects. Unpublished PhD thesis, USA, University of Maine, Graduate School, Spatial Information Science and Engineering.
• HAZARIKA, S.M. and COHN, A.G. (2002) Abducing qualitative spatio temporal histories from partial observations. In: D. Fensel, F. Giunchiglia, D.L. McGuinness, M.-A. Williams, eds., Proceedings of 8th Conference on Principles of Knowledge Representation and Reasoning, Toulouse, France, 14-25.
• HOBBS, J.R. and NARAYANAN, S. (2002) Spatial representation and reasoning. In: L. Nadel, ed., Encyclopaedia of Cognitive Science. Nature Publishing Group, London, UK.
• ISLI, A. and COHN, A.G. (2000) A new approach to cyclic ordering of 2D orientations using ternary relation algebras. Artificial Intelligence 122(1-2), 137-187.
• KOPRULU, M., CICEKLI, N.K. and YAZICI, A. (2004) Spatio-temporal querying in video databases. Information Sciences 160(1-4), 131-152.
• LAUBE, P. (2001) A classification of analysis methods for dynamic point objects in environmental GIS. In: M. Konecny, ed.; Proceedings of the 4th. AGILE Conference, Brno, Czech Republic, 121-134.
• Li, J.Z., Ozsu, M.T. and SZAFRON, D. (1997) Modelling of moving objects in a video database. Proceedings of the IEEE Conference on Multimedia J Computing and Systems, Ottawa, Canada, 336-343.
• LIGOZAT, G. (1998) Reasoning about cardinal directions. Journal of Visual Languages and Computing 9(1), 23-44.
• MOREIRA, J., RIBEIRO, C. and SAGLIO, J.-M. (1999) Representation and manipulation of moving points: an extended data model for location estimation. Cartography and Geographic Information Systems 26(2), 109-123.
• MORTENSEN; M.E. (1999) Mathematics for Computer Graphics Applications. Industrial Press. New York, USA,
• MULLER, P. (1998) A qualitative theory of motion based on spatiotemporal primitives. In: A.G. Cohn, L. Schubert, S. Shapiro, eds., Proceedings of the 6th Conference on Principles of Knowledge Representation and Reasoning, Trento, Italy, 131-142.
• PETRY, F.E., ROBINSON, V.B. and COBB, M.A., EDS. (2005) Fuzzy Modeling with Spatial Information for Geographic Problems. Springer Verlag Heidelberg-Berlin, Germany.
• RAJAGOPALAN, R. (1995) Qualitative Reasoning about Dynamic Change in the Spatial Properties of a Physical System. Unpublished PhD thesis, USA, University of Texas, Department of Computer Sciences.
• RANDELL, D., GUI, Z.Z. and COHN, A.G. (1992) A spatial logic based on regions and connection. In: B. Nebel, W. Swartout and C. Rich, eds, Proceedings of the 3rd Conference on Knowledge Representation and Reasoning. San Mateo, USA, 165-176.
• SHARMA, J. (1996) Integrated Spatial reasoning in Geographic Information, Systems: Combining Topology and Direction. Unpublished PhD thesis, USA, University of Maine, Graduate School, Spatial Information Science and Engineering.
• STOLZENBURG, F., OBST, O. and MURRAY, J. (2002) Qualitative velocity and ball interception. In: M. Jarke, J. Köhler and G. Lakemeyer, eds., Proceedings of the 25th German Conference on Artificial Intelligence, Aachen, Germany, LNAI (2479), Springer Verlag, 283-298.
• TIMPF. S. and FRANK, A.U. (1997) Using hierarchical spatial data structures for hierarchical spatial reasoning. In: S.C. Hirtle, A.U. Frank, eds., Proceedings of the 3rd Conference on Spatial Information. Theory, Laurel Highlands, USA, LNCS 1329, Springer Verlag, 69-83.
• TOMLIN, C.D. (1990) Geographic Information Systems and. Cartographic Modelling. Prentice Hall, Englewoods Cliff, USA,
• VAN DE WEGHE, N. (2004) Representing and Reasoning about Moving Objects: A Qualitative Approach. Unpublished PhD thesis, Belgium, Ghent University, Faculty of Sciences, Department of Geography.
• VAN DE WEGHE, N., COHN, A.G., BOGAERT, P. and DE MAEYER, PH. (2004) Representation of moving objects along a road network. Proceedings of Geoinformatics, Gavle. Sweden, 187-197.
• VAN DE WEGHE, N., COHN, A.G.; DE MAEYER, PH. and WITLOX, F. (2005) Representing moving objects in computer based expert systems: the overtake event example. Expert Systems with Applications 29(4), 977-983.
• VIEU, L. (1997) Spatial representation and reasoning in artificial intelligence. In: O. Stock, ed., Spatial and Temporal Reasoning. Kluwer, Dordrecht, Netherlands, 5-41.
• WELD, D.S. and DE KLEER, J. (1990) Readings in Qualitative Reasoning about Physical Systems. Morgan Kaufmann, San Mateo. California.
• WOLFSON. O., Xu, B., CHAMBERLAIN, S. and JIANG, L. (1998) Moving object databases: issues and solutions. Proceedings of the 10th Conference on Scientific and Statistical Database Management. Capri, Italy, 111-122.
• YANG, Z. (2001) Modelling and Reasoning with Geospatial Lifelines in Geographic Information System. Unpublished PhD thesis, USA. University of New York at Buffalo, Faculty of the Graduate School of State. Department of Geography.
• ZIMMERMANN, K. and FREKSA, C. (1996) Qualitative spatial reasoning using orientation, distance, and path knowledge. Applied Intelligence 6(1), 49-58.