×

A trajectory calculus for qualitative spatial reasoning using answer set programming. (English) Zbl 1451.68252

Summary: Spatial information is often expressed using qualitative terms such as natural language expressions instead of coordinates; reasoning over such terms has several practical applications, such as bus routes planning. Representing and reasoning on trajectories is a specific case of qualitative spatial reasoning that focuses on moving objects and their paths. In this work, we propose two versions of a trajectory calculus based on the allowed properties over trajectories, where trajectories are defined as a sequence of non-overlapping regions of a partitioned map. More specifically, if a given trajectory is allowed to start and finish at the same region, 6 base relations are defined (TC-6). If a given trajectory should have different start and finish regions but cycles are allowed within, 10 base relations are defined (TC-10). Both versions of the calculus are implemented as ASP programs; we propose several different encodings, including a generalised program capable of encoding any qualitative calculus in ASP. All proposed encodings are experimentally evaluated using a real-world dataset. Experiment results show that the best performing implementation can scale up to an input of 250 trajectories for TC-6 and 150 trajectories for TC-10 for the problem of discovering a consistent configuration, a significant improvement compared to previous ASP implementations for similar qualitative spatial and temporal calculi.

MSC:

68T27 Logic in artificial intelligence
68N17 Logic programming
68T30 Knowledge representation

Software:

Gringo; Clingo; Datalog
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Allen, J. F.; Hayes, P. J., IJCAI, An interval-based representation of temporal knowledge, 221-226, (1981), William Kaufmann
[2] Andrienko, G. L.; Andrienko, N. V.; Fuchs, G.; Wood, J., Revealing patterns and trends of mass mobility through spatial and temporal abstraction of origin-destination movement data, IEEE Trans. Vis. Comput. Graph., 23, 9, 2120-2136, (2017) · doi:10.1109/TVCG.2016.2616404
[3] Brenton, C.; Faber, W.; Batsakis, S.; Carro, M.; King, A.; Saeedloei, N.; Vos, M. D., ICLP (Technical Communications), Answer set programming for qualitative spatio-temporal reasoning: Methods and experiments, 4:1-4:15, (2016), Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
[4] Cadoli, M.; Schaerf, M., A survey of complexity results for nonmonotonic logics, J. Log. Program., 17, 2-3, 127-160, (1993) · Zbl 0784.68039 · doi:10.1016/0743-1066(93)90029-G
[5] Cohn, A. G.; Bennett, B.; Gooday, J.; Gotts, N. M., Qualitative spatial representation and reasoning with the region connection calculus, GeoInformatica, 1, 3, 275-316, (1997) · doi:10.1023/A:1009712514511
[6] Delafontaine, M.; Bogaert, P.; Cohn, A. G.; Witlox, F.; Maeyer, P. D.; De Weghe, N. V., Inferring additional knowledge from qtcn relations, Inf. Sci., 181, 9, 1573-1590, (2011) · doi:10.1016/j.ins.2010.12.021
[7] Delafontaine, M.; Cohn, A. G.; De Weghe, N. V., Implementing a qualitative calculus to analyse moving point objects, Expert Syst. Appl., 38, 5, 5187-5196, (2011) · doi:10.1016/j.eswa.2010.10.042
[8] Eiter, T.; Gottlob, G.; Mannila, H., Disjunctive datalog, ACM Trans. Database Syst., 22, 3, 364-418, (1997) · doi:10.1145/261124.261126
[9] Escrig, M. T.; Toledo, F.; Escrig, M. T.; Toledo, F.; Golobardes, E., CCIA, Qualitative velocity, 29-39, (2002), Springer
[10] Freuder, E. C.; Mackworth, A. K.; Rossi, F.; Van Beek, P.; Walsh, T., Handbook of Constraint Programming, Constraint Satisfaction: An Emerging Paradigm, 13-27, (2006), Elsevier Science Inc.: Elsevier Science Inc., New York, NY, USA
[11] Gebser, M.; Harrison, A.; Kaminski, R.; Lifschitz, V.; Schaub, T., Abstract gringo, TPLP, 15, 4-5, 449-463, (2015) · Zbl 1379.68031
[12] Gebser, M.; Kaminski, R.; Kaufmann, B.; Ostrowski, M.; Schaub, T.; Wanko, P.; Carro, M.; King, A., Technical Communications of the Thirty-second International Conference on Logic Programming (ICLP’16), Theory solving made easy with clingo 5, 2:1-2:15, (2016), Schloss Dagstuhl
[13] Hazarika, S. M.; Cohn, A. G.; Montello, D. R., COSIT, Qualitative spatio-temporal continuity, 92-107, (2001), Springer · Zbl 1042.68739
[14] Hu, S.-R.; Peeta, S.; Liou, H.-T., Integrated determination of network origin-destination trip matrix and heterogeneous sensor selection and location strategy, IEEE Trans. Intelligent Transportation Systems, 17, 1, 195-205, (2016) · doi:10.1109/TITS.2015.2473691
[15] Li, J. J., ICTAI, Qualitative spatial and temporal reasoning with answer set programming, 603-609, (2012), IEEE Computer Society
[16] Ma, Z.; Lu, D.; Liu, Q.; Wang, J.; Xiong, Z., (2017)
[17] Marek, V. W.; Truszczynski, M.; Lusk, E. L.; Overbeek, R. A., Logic Programming, Proceedings of the North American Conference 1989, Cleveland, Ohio, USA, October 16-20, 1989. 2 Volumes, Stable semantics for logic programs and default theories, 243-256, (1989), MIT Press
[18] Martínez-Martín, E.; Escrig, M. T.; Del Pobil, A. P., A general qualitative spatio-temporal model based on intervals, J. UCS, 18, 10, 1343-1378, (2012) · Zbl 1311.68153
[19] Moreira-Matias, L.; Gama, J.; Ferreira, M.; Mendes-Moreira, J.; Damas, L., Predicting taxi-passenger demand using streaming data, IEEE Trans. Intelligent Transportation Systems, 14, 3, 1393-1402, (2013) · doi:10.1109/TITS.2013.2262376
[20] Muller, P.; Cohn, A. G.; Schubert, L. K.; Shapiro, S. C., KR, A qualitative theory of motion based on spatio-temporal primitives, 131-143, (1998), Morgan Kaufmann
[21] Noyon, V.; Claramunt, C.; Devogele, T., A relative representation of trajectories in geogaphical spaces, GeoInformatica, 11, 4, 479-496, (2007) · doi:10.1007/s10707-007-0023-2
[22] Patroumpas, K.; Sellis, T. K.; Li, K.-C.; Jiang, H.; Yang, L. T.; Cuzzocrea, A., Big Data - Algorithms, Analytics, and Applications, Managing big trajectory data: Online processing of positional streams, 257-280, (2015), Chapman and Hall/CRC
[23] Renz, J., The Region Connection Calculus, 41-50, (2002), Springer Berlin Heidelberg
[24] Renz, J.; Rauh, R.; Knauff, M.; Freksa, C.; Brauer, W.; Habel, C.; Wender, K. F., Spatial Cognition, Towards cognitive adequacy of topological spatial relations, 184-197, (2000), Springer
[25] Van De Weghe, N.; Shekhar, S.; Xiong, H.; Zhou, X., Encyclopedia of GIS, Spatiotemporal relations for moving objects, 2177-2186, (2017), Springer
[26] Van De Weghe, N.; Cohn, A. G.; De Tré, G.; De Maeyer, P., A qualitative trajectory calculus as a basis for representing moving objects in geographical information systems, Control and Cybernetics, 35, 1, 97-119, (2006) · Zbl 1189.68170
[27] Van De Weghe, N.; Kuijpers, B.; Bogaert, P.; Maeyer, P. D.; Rodríguez, M. A.; Cruz, I. F.; Egenhofer, M. J.; Levashkin, S., GeoS, A qualitative trajectory calculus and the composition of its relations, 60-76, (2005), Springer
[28] Wałěga, P. A.; Schultz, C. P. L.; Bhatt, M., Non-monotonic spatial reasoning with answer set programming modulo theories, TPLP, 17, 2, 205-225, (2017) · Zbl 1379.68303
[29] Wang, Z.; Jin, B.; Zhang, F.; Yang, R.; Ji, Q., (2017)
[30] Yuan, J.; Zheng, Y.; Xie, X.; Sun, G., T-drive: Enhancing driving directions with taxi drivers’ intelligence, IEEE Trans. Knowl. Data Eng., 25, 1, 220-232, (2013) · doi:10.1109/TKDE.2011.200
[31] Zimmermann, K.; Freksa, C., Qualitative spatial reasoning using orientation, distance, and path knowledge, Appl. Intell., 6, 1, 49-58, (1996) · doi:10.1007/BF00117601
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.