A system of operators for spatial-temporal analysis of dynamic scenes
https://doi.org/10.15514/ISPRAS-2018-30(6)-13
Abstract
The rapid growth in the volume of information and the need for its comprehensive analysis lead to the development of new methods of working with multidimensional and space-time data. To work with such data, Qualitative Spatial Reasoning is often used to extract (produce) new knowledge based on facts established in one way or another. Despite the variety of formal analysis systems available, sets of operators do not allow for the identification of complex space-time relationships between objects. Existing software tools, such as SparQ, GQR, QAT, CLP (QS), are focused on analyzing one aspect and are applicable mainly for interval analysis of time series of events and production of conclusions about some spatial relationships. In practice, tools are usually used to analyze simple relationships in simple scenes. The lack of interfaces limits their combined use with quantitative analysis tools, necessary, for example, to establish primary facts, and use within the framework of the concepts of 4D (space-time), 5D (space-time and cost) and multi-D (multidimensional) modeling. This paper proposes a system of topological, metric, directional and temporal operators for complex spatial-temporal analysis of dynamic scenes. This system allows combined usage of qualitative and quantitative analysis methods, which is essential not only for determining initial facts, but also for producing new knowledge based on these facts. The system of operators proposed is deemed prospective for problems of spatial-temporal (4D) modeling and planning of industrial projects, and particularly for specifying and detecting of non-trivial conflicts in project schedules.
About the Authors
K. S. Petrishchev
Ivannikov Institute for System Programming of the Russian Academy of Sciences
Russian Federation
Russian Federation
V. A. Zolotov
Ivannikov Institute for System Programming of the Russian Academy of Sciences
Russian Federation
Russian Federation
V. A. Semenov
Ivannikov Institute for System Programming of the Russian Academy of Sciences; Moscow Institute of Physics and Technology (State University); National Research University, Higher School of Economics
Russian Federation
Russian Federation
References
1. . C. Freksa. Spatial computing. Cognitive and Linguistic Aspects of Geographic Space, Heidelberg, Springer Berlin, 2013, pp. 23-42.
2. . D. Heesom, L. Mahdjoubi. Trends of 4D CAD applications for construction planning. Construction Management and Economics, vol. 22, 2004, pp. 171-182.
3. . M.L.A.E. Borges, I.C. de Souza, S. Melo, J.P. Giesta. 4D Building Information Modelling: A Systematic Mapping Study. In Proc. of the 35th International Symposium on Automation and Robotics in Construction, Berlin, 2018.
4. . В. Золотов, В. Семенов. Cовременные методы поиска и индексации многомерных данных в приложениях моделирования больших динамических сцен. Труды ИСП РАН, т. 24, 2013 г, стр. 381-416. DOI: 10.15514/ISPRAS-2013-24-17.
5. . V. Semenov, K. Kazakov, S. Morozov, O. Tarlapan, V. Zolotov, T. Dengenis. 4D modeling of large industrial projects using spatio-temporal decomposition. In eWork and eBusiness in Architecture, Engineering and Construction, 2010, pp. 89-95.
6. . Золотов В.А., Семенов В.А. Исследование и развитие метода декомпозиции для анализа больших пространственных данных. Труды ИСП РАН, том 25, 2013 г., стр. 121-166. DOI: 10.15514/ISPRAS-2013-25-8.
7. . Золотов В.А., Семенов В.А. Перспективные схемы пространственно-временной индексации для визуального моделирования масштабных индустриальных проектов. Труды ИСП РАН, том 26, вып. 2, 2014 г., стр. 175-196. DOI: 10.15514/ISPRAS-2014-26(2)-8.
8. . A.G. Cohn, S.M. Hazarika. Qualitative Spatial Representation and Reasoning: An Overview. Fundamenta Informaticae, vol. 46, № 1-2, 2001, pp. 1-29.
9. . J.F. Allen. Maintaining knowledge about temporal intervals. Communications of the ACM, vol. 26, issue 11, 1983, pp. 832-843.
10. . E.A. Emerson. Chapter 16 - Temporal and Modal Logic. In Handbook of Theoretical Computer Science, B: Formal Models and Semantics, Elsevier, 1990, pp. 995-1072.
11. . M.B. Vilain, H. Kautz. Constraint Propagation Algorithms for Temporal Reasoning. In Proc. of the 5th National Conference on Artificial Intelligence, 1986, pp. 377-382.
12. . A.U. Frank. Qualitative spatial reasoning about distances and directions in geographic space. Journal of Visual Languages & Computing, vol. 3, № 4, 1992, pp. 343-371.
13. . C. Freksa. Using orientation information for qualitative spatial reasoning. Lecture Notes in Computer Science, vol. 639, 1992, pp. 162-178.
14. . G.F. Ligozat. Qualitative triangulation for spatial reasoning. Lecture Notes in Computer Science, vol. 716, 1993, pp. 54-68.
15. . R. Moratz, J. Renz, D. Wolter. Qualitative Spatial Reasoning About Line Segments. In Proc. of the 14th European Conference on Artificial Intelligence, 2000, pp. 234-238.
16. . P. Balbiani, J.-F. Condotta, L.F. del Cerro. A new tractable subclass of the rectangle algebra. In Proc. of the 16th International joint conference on Artifical Intelligence, vol. 1, 1999, pp. 442-447.
17. . R.K. Goyal, M.J. Egenhofer. Similarity of cardinal directions. Lecture Notes in Computer Science, vol. 2121, 2001, pp. 36-55.
18. . S. Skiadopoulos, M. Koubarakis. On the consistency of cardinal direction constraints. Artificial Intelligence, vol. 163, № 1, 2005, pp. 91-135.
19. . M.J. Egenhofer, R.D. Franzosa. Point-set topological spatial relations. International Journal of Geographical Information Systems, vol. 5, № 2, 1991, pp. 161-174.
20. . D. A. Randell, Z. Cui, A. G. Cohn. A spatial logic based on regions and connection. In Proc. of the 1st International Conference Principles of Knowledge Representation and Reasoning, 1992, стр. 165-176.
21. . N. Eloe. VRCC-3D+: Qualitative spatial and temporal reasoning in 3 dimensions. PhD Thesis, Missouri University of Science and Technology, 2015.
22. . A.G. Cohn, J. Renz. Qualitative Spatial Representation and Reasoning. In Handbook of Knowledge Representation, Elsevier, 2008, pp. 551-596.
23. . M.J. Egenhofer, J. Sharma, D.M. Mark. A Critical Comparison of the 4-Intersection and 9-Intersection Models for Spatial Relations: Formal Analysis. In Proc. of the International Research Symposium on Computer-based Cartography, AutoCarto 11, 1993, pp. 1-12.
24. . T. Mossakowski, R. Moratz. Qualitative Reasoning about Relative Direction of Oriented Points. Artificial Intelligence, vol. 180-181, 2012, pp. 34-45.
25. . K. Zimmermann. Measuring without measures the D-calculus. Lecture Notes in Computer Science, vol. 988, 1995, pp. 59-67.
26. . R. Moratz, B. Nebel, C. Freksa. Qualitative spatial reasoning about relative position. Lecture Notes in Computer Science, vol. 2685, 2002, pp. 385-400.
27. . A. Gerevini, B. Nebel. Qualitative Spatio-Temporal Reasoning with {RCC-8} and Allen's Interval. In Proc. of the 15th Eureopean Conference on Artificial Intelligence, ECAI'2002, 2002, pp. 312-316.
28. . N. Van de Weghe, A. Cohn, G. De Tre, P. De Maeyer. A qualitative trajectory calculus as a basis for representing moving objects in geographical information systems. Control and Cybernetics, vol. 35, № 1, 2006, pp. 97-119.
29. . A. Frank. Qualitative Spatial Reasoning: Cardinal Directions as an Example. International Journal of Geographical Information Systems, vol. 10, issue 3, 1996, pp. 269-290.
30. . J. Renz, D. Mitra. Qualitative Direction Calculi with Arbitrary Granularity. Lecture Notes in Computer Science, vol. 3157, 2004, pp. 65-74.
31. . A. Borrmann, E. Rank. Query support for BIMs using semantic and spatial conditions. In Handbook of Research on Building Information Modeling and Construction Informatics: Concepts and Technologies, IGI Global, 2009, pp. 405-450.
32. . A. Carvalho, C. Ribeiro, A. Augusto de Sousa. A Spatio-temporal Database System Based on TimeDB and Oracle Spatial. Research and Practical Issues of Enterprise Information Systems, IFIP International Federation for Information Processing, vol. 205, 2006, pp. 11-20, Boston, MA, Springer US.
33. . C. Xinmin Chen, C. Zaniolo. SQLST : A Spatio-Temporal Data Model and Query Language. Lecture Notes in Computer Science, vol. 1920, 2000, pp. 96-111.
34. . M. Erwig, M. Schneider. Developments in spatio-temporal query languages. In Proc. of the Tenth International Workshop on Database and Expert Systems Applications, DEXA 99, 1999, pp. 441-449.
35. . P. Muller. A Qualitative Theory of Motion Based on Spatio-Temporal Primitives. In Proceedings of the Sixth International Conference on Principles of Knowledge Representation and Reasoning (KR '98), 1998, pp. 131-141.
36. . E. Davis. Describing spatial transitions using mereotopological relations over histories. Technical Report #2000-809, New York University, 2000.
Review
For citations:
Petrishchev K.S., Zolotov V.A., Semenov V.A. A system of operators for spatial-temporal analysis of dynamic scenes. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2018;30(6):237-258. (In Russ.) https://doi.org/10.15514/ISPRAS-2018-30(6)-13
Email this article 