×

Reasoning about cardinal directions between 3-dimensional extended objects using answer set programming. (English) Zbl 1468.68224

Summary: We propose a novel formal framework (called 3D-NCDC-ASP) to represent and reason about cardinal directions between extended objects in 3-dimensional (3D) space, using Answer Set Programming (ASP). 3D-NCDC-ASP extends Cardinal Directional Calculus (CDC) with a new type of default constraints, and NCDC-ASP to 3D. 3D-NCDC-ASP provides a flexible platform offering different types of reasoning: Nonmonotonic reasoning with defaults, checking consistency of a set of constraints on 3D cardinal directions between objects, explaining inconsistencies, and inferring missing CDC relations. We prove the soundness of 3D-NCDC-ASP, and illustrate its usefulness with applications.

MSC:

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

Software:

z3; Potassco
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Allen, J. F.1983. Maintaining knowledge about temporal intervals. Commun. ACM 26, 11, 832-843. · Zbl 0519.68079
[2] Balbiani, P., Condotta, J., and Del Cerro, L. F.2002. Tractability results in the block algebra. J. Log. Comput. 12, 5, 885-909. · Zbl 1021.68087
[3] Baryannis, G., Tachmazidis, I., Batsakis, S., Antoniou, G., Alviano, M., Sellis, T., and Tsai, P.-W.2018. A trajectory calculus for qualitative spatial reasoning using answer set programming. Theory and Practice of Logic Programming 18, 3-4, 355-371. · Zbl 1451.68252
[4] Borrmann, A. and Beetz, J.2010. Towards spatial reasoning on building information models. In Proceedings of the 8th European Conference on Product and Process Modeling (ECPPM). 61-67.
[5] Brenton, C., Faber, W., and Batsakis, S.2016. Answer set programming for qualitative spatio-temporal reasoning: Methods and experiments. In OASIcs-OpenAccess Series in Informatics. Vol. 52. · Zbl 1428.68282
[6] Calimeri, F., Faber, W., Gebser, M., Ianni, G., Kaminski, R., Krennwallner, T., Leone, N., Maratea, M., Ricca, F., and Schaub, T.2020. Asp-Core-2 input language format. Theory and Practice of Logic Programming 20, 2, 294-309. · Zbl 1472.68180
[7] Chen, J., Cohn, A. G., Liu, D., Wang, S., Ouyang, J., and Yu, Q.2015. A survey of qualitative spatial representations. The Knowledge Engineering Review 30, 1, 106-136.
[8] Chen, J., Liu, D., Jia, H., and Zhang, C.2007. Cardinal direction relations in 3D space. In Proc. of International Conference on Knowledge Science, Engineering and Management. 623-629.
[9] Cohn, A. G., Bennett, B., Gooday, J., and Gotts, N. M.1997. Qualitative spatial representation and reasoning with the region connection calculus. GeoInformatica 1, 3, 275-316.
[10] Costantini, S., Gasperis, G. D., and Olivieri, R.2019. Digital forensics and investigations meet artificial intelligence. Ann. Math. Artif. Intell. 86,1-3, 193-229.
[11] Randell, David A., Z. C. and Cohn, A. G. 1992. A spatial logic based on regions and connection. In Proc. of KR.
[12] De Moura, L. and Bjørner, N.2008. Z3: An efficient smt solver. In Tools and Algorithms for the Construction and Analysis of Systems. 337-340.
[13] Dylla, F., Lee, J. H., Mossakowski, T., Schneider, T., Delden, A. V., Ven, J. V. D., and Wolter, D.2017. A survey of qualitative spatial and temporal calculi: algebraic and computational properties. ACM Computing Surveys (CSUR) 50, 1, 7.
[14] Gebser, M., Kaufmann, B., Kaminski, R., Ostrowski, M., Schaub, T., and Schneider, M. T.2011. Potassco: The potsdam answer set solving collection. AI Commun. 24, 2, 107-124. · Zbl 1215.68214
[15] Gelfond, M. and Lifschitz, V.1988. The stable model semantics for logic programming. In Proc. of ICLP. MIT Press, 1070-1080.
[16] Gelfond, M. and Lifschitz, V.1991. Classical negation in logic programs and disjunctive databases. New Generation Computing 9, 365-385. · Zbl 0735.68012
[17] Goyal, R. and Egenhofer, M. J.1997. The direction-relation matrix: A representation for directions relations between extended spatial objects. The annual assembly and the summer retreat of University Consortium for Geographic Information Systems Science 3, 95-102.
[18] Hou, R., Wu, T., and Yang, J.2016. Reasoning with cardinal directions in 3D space based on block algebra. Proc. of ICEITI.
[19] Izmirlioglu, Y. and Erdem, E.2018. Qualitative reasoning about cardinal directions using answer set programming. In Proc. of AAAI.
[20] Izmirlioglu, Y. and Erdem, E.2020. Reasoning about Cardinal Directions between 3-Dimensional Extended Objects using Answer Set Programming (arXiv).
[21] Li, C., Lu, J., Yin, C., and Ma, L.2009. Qualitative spatial representation and reasoning in 3D space. In Proc. of ICICTA. 653-657.
[22] Lifschitz, V.2002. Answer set programming and plan generation. Artificial Intelligence 138, 39-54. · Zbl 0995.68020
[23] Liu, W., Zhang, X., Li, S., and Ying, M.2010. Reasoning about cardinal directions between extended objects. Artificial Intelligence 174, 12-13, 951-983. · Zbl 1205.68399
[24] Marek, V. and Truszczyński, M.1999. Stable models and an alternative logic programming paradigm. In The Logic Programming Paradigm: a 25-Year Perspective. Springer Verlag, 375-398. · Zbl 0979.68524
[25] Mota, T. and Sridharan, M.2018. Incrementally grounding expressions for spatial relations between objects. In Proc. of IJCAI. 1928-1934.
[26] Niemelä, I.1999. Logic programs with stable model semantics as a constraint programming paradigm. Annals of Mathematics and Artificial Intelligence 25, 241-273. · Zbl 0940.68018
[27] Pais, J. and Pinto-Ferreira, C.2000. Spatial representation and reasoning using the n-dimensional projective approach. In Tech. Report, AAAI Workshop on Spatial and Temporal Granularity. 79-82.
[28] Skiadopoulos, S. and Koubarakis, M.2004. Composing cardinal direction relations. Artificial Intelligence 152, 2, 143-171. · Zbl 1082.68108
[29] Skiadopoulos, S. and Koubarakis, M.2005. On the consistency of cardinal direction constraints. Artificial Intelligence 163, 1, 91-135. · Zbl 1132.68713
[30] Walega, P. A., Schultz, C., and Bhatt, M.2017. Non-monotonic spatial reasoning with answer set programming modulo theories. Theory and Practice of Logic Programming 17, 2, 205-225. · Zbl 1379.68303
[31] Zampogiannis, K., Yang, Y., Fermüller, C., and Aloimonos, Y.2015. Learning the spatial semantics of manipulation actions through preposition grounding. In Proc. of ICRA. 1389-1396.
[32] Zereik, E., Bibuli, M., Miskovic, N., Ridao, P., and Pascoal, A.2018. Challenges and future trends in marine robotics. Annual Reviews in Control.
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.