{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,12]],"date-time":"2026-05-12T03:18:50Z","timestamp":1778555930544,"version":"3.51.4"},"reference-count":32,"publisher":"Cambridge University Press (CUP)","issue":"6","license":[{"start":{"date-parts":[[2020,9,22]],"date-time":"2020-09-22T00:00:00Z","timestamp":1600732800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Theory and Practice of Logic Programming"],"published-print":{"date-parts":[[2020,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We propose a novel formal framework (called 3D-<jats:sc>N<\/jats:sc>CDC-ASP) to represent and reason about cardinal directions between extended objects in 3-dimensional (3D) space, using Answer Set Programming (ASP). 3D-<jats:sc>N<\/jats:sc>CDC-ASP extends Cardinal Directional Calculus (CDC) with a new type of default constraints, and<jats:sc>N<\/jats:sc>CDC-ASP to 3D. 3D-<jats:sc>N<\/jats:sc>CDC-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-<jats:sc>N<\/jats:sc>CDC-ASP, and illustrate its usefulness with applications.<\/jats:p>","DOI":"10.1017\/s1471068420000411","type":"journal-article","created":{"date-parts":[[2020,9,22]],"date-time":"2020-09-22T02:43:15Z","timestamp":1600742595000},"page":"942-957","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":2,"title":["Reasoning about Cardinal Directions between 3-Dimensional Extended Objects using Answer Set Programming"],"prefix":"10.1017","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4740-5147","authenticated-orcid":false,"given":"Yusuf","family":"Izmirlioglu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8384-7810","authenticated-orcid":false,"given":"Esra","family":"Erdem","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2020,9,22]]},"reference":[{"key":"S1471068420000411_ref25","doi-asserted-by":"crossref","unstructured":"25. Mota, T. and Sridharan, M. 2018. Incrementally grounding expressions for spatial relations between objects. In Proc. of IJCAI. 1928\u20131934.","DOI":"10.24963\/ijcai.2018\/266"},{"key":"S1471068420000411_ref12","doi-asserted-by":"crossref","unstructured":"12. de Moura, L. and Bj\u00f8rner, N. 2008. Z3: An efficient smt solver. In Tools and Algorithms for the Construction and Analysis of Systems. 337\u2013340.","DOI":"10.1007\/978-3-540-78800-3_24"},{"key":"S1471068420000411_ref29","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/j.artint.2004.10.010","article-title":"On the consistency of cardinal direction constraints","volume":"1","author":"Skiadopoulos","year":"2005","journal-title":"Artificial Intelligence 163"},{"key":"S1471068420000411_ref15","unstructured":"15. Gelfond, M. and Lifschitz, V. 1988. The stable model semantics for logic programming. In Proc. of ICLP. MIT Press, 1070\u20131080."},{"key":"S1471068420000411_ref32","doi-asserted-by":"crossref","unstructured":"32. Zereik, E. , Bibuli, M. , Miskovic, N. , Ridao, P. , and Pascoal, A. 2018. Challenges and future trends in marine robotics. Annual Reviews in Control.","DOI":"10.1016\/j.arcontrol.2018.10.002"},{"key":"S1471068420000411_ref5","unstructured":"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."},{"key":"S1471068420000411_ref23","doi-asserted-by":"crossref","first-page":"951","DOI":"10.1016\/j.artint.2010.05.006","article-title":"Reasoning about cardinal directions between extended objects","volume":"12","author":"Liu","year":"2010","journal-title":"Artificial Intelligence 174"},{"key":"S1471068420000411_ref1","doi-asserted-by":"crossref","first-page":"832","DOI":"10.1145\/182.358434","article-title":"Maintaining knowledge about temporal intervals","volume":"11","author":"Allen","year":"1983","journal-title":"Commun. ACM 26"},{"key":"S1471068420000411_ref2","doi-asserted-by":"crossref","first-page":"885","DOI":"10.1093\/logcom\/12.5.885","article-title":"Tractability results in the block algebra","volume":"5","author":"Balbiani","year":"2002","journal-title":"J. Log. Comput. 12"},{"key":"S1471068420000411_ref19","doi-asserted-by":"crossref","unstructured":"19. Izmirlioglu, Y. and Erdem, E. 2018. Qualitative reasoning about cardinal directions using answer set programming. In Proc. of AAAI.","DOI":"10.1609\/aaai.v32i1.11568"},{"key":"S1471068420000411_ref18","doi-asserted-by":"crossref","unstructured":"18. Hou, R. , Wu, T. , and Yang, J. 2016. Reasoning with cardinal directions in 3D space based on block algebra. Proc. of ICEITI.","DOI":"10.12783\/dtcse\/iceiti2016\/6179"},{"key":"S1471068420000411_ref24","volume-title":"The Logic Programming Paradigm: a 25-Year Perspective","author":"Marek","year":"1999"},{"key":"S1471068420000411_ref31","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2015.7139371"},{"key":"S1471068420000411_ref21","doi-asserted-by":"crossref","unstructured":"21. Li, C. , Lu, J. , Yin, C. , and Ma, L. 2009. Qualitative spatial representation and reasoning in 3D space. In Proc. of ICICTA. 653\u2013657.","DOI":"10.1109\/ICICTA.2009.163"},{"key":"S1471068420000411_ref8","unstructured":"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\u2013629."},{"key":"S1471068420000411_ref3","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1017\/S147106841800011X","article-title":"A trajectory calculus for qualitative spatial reasoning using answer set programming","volume":"3","author":"Baryannis","year":"2018","journal-title":"Theory and Practice of Logic Programming 18"},{"key":"S1471068420000411_ref10","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1007\/s10472-019-09632-y","article-title":"Digital forensics and investigations meet artificial intelligence","volume":"1","author":"Costantini","year":"2019","journal-title":"Ann. Math. Artif. Intell. 86,"},{"key":"S1471068420000411_ref11","unstructured":"11. Randell, David A. , Z. C. and Cohn, A. G. 1992. A spatial logic based on regions and connection. In Proc. of KR."},{"key":"S1471068420000411_ref14","doi-asserted-by":"crossref","first-page":"107","DOI":"10.3233\/AIC-2011-0491","article-title":"Potassco: The potsdam answer set solving collection","volume":"2","author":"Gebser","year":"2011","journal-title":"AI Commun. 24"},{"key":"S1471068420000411_ref27","unstructured":"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\u201382."},{"key":"S1471068420000411_ref16","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1007\/BF03037169","article-title":"Classical negation in logic programs and disjunctive databases","author":"Gelfond","year":"1991","journal-title":"New Generation Computing 9"},{"key":"S1471068420000411_ref20","doi-asserted-by":"crossref","unstructured":"20. Izmirlioglu, Y. and Erdem, E. 2020. Reasoning about Cardinal Directions between 3-Dimensional Extended Objects using Answer Set Programming (arXiv).","DOI":"10.1017\/S1471068420000411"},{"key":"S1471068420000411_ref22","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/S0004-3702(02)00186-8","article-title":"Answer set programming and plan generation","author":"Lifschitz","year":"2002","journal-title":"Artificial Intelligence 138"},{"key":"S1471068420000411_ref6","doi-asserted-by":"crossref","first-page":"294","DOI":"10.1017\/S1471068419000450","article-title":"Asp-Core-2 input language format","volume":"2","author":"Calimeri","year":"2020","journal-title":"Theory and Practice of Logic Programming 20"},{"key":"S1471068420000411_ref4","doi-asserted-by":"crossref","unstructured":"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\u201367.","DOI":"10.1201\/b10527-13"},{"key":"S1471068420000411_ref28","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/S0004-3702(03)00137-1","article-title":"Composing cardinal direction relations","volume":"2","author":"Skiadopoulos","year":"2004","journal-title":"Artificial Intelligence 152"},{"key":"S1471068420000411_ref26","doi-asserted-by":"publisher","DOI":"10.1023\/A:1018930122475"},{"key":"S1471068420000411_ref30","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1017\/S1471068416000193","article-title":"Non-monotonic spatial reasoning with answer set programming modulo theories","volume":"2","author":"Walega","year":"2017","journal-title":"Theory and Practice of Logic Programming 17"},{"key":"S1471068420000411_ref9","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1023\/A:1009712514511","article-title":"Qualitative spatial representation and reasoning with the region connection calculus","volume":"3","author":"Cohn","year":"1997","journal-title":"GeoInformatica 1"},{"key":"S1471068420000411_ref7","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1017\/S0269888913000350","article-title":"A survey of qualitative spatial representations","volume":"1","author":"Chen","year":"2015","journal-title":"The Knowledge Engineering Review 30"},{"key":"S1471068420000411_ref13","first-page":"7","article-title":"A survey of qualitative spatial and temporal calculi: algebraic and computational properties","volume":"1","author":"Dylla","year":"2017","journal-title":"ACM Computing Surveys (CSUR) 50"},{"key":"S1471068420000411_ref17","first-page":"95","article-title":"The direction-relation matrix: A representation for directions relations between extended spatial objects","author":"Goyal","year":"1997","journal-title":"The annual assembly and the summer retreat of University Consortium for Geographic Information Systems Science 3"}],"container-title":["Theory and Practice of Logic Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S1471068420000411","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,19]],"date-time":"2022-11-19T11:40:55Z","timestamp":1668858055000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1471068420000411\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9,22]]},"references-count":32,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2020,11]]}},"alternative-id":["S1471068420000411"],"URL":"https:\/\/doi.org\/10.1017\/s1471068420000411","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"value":"1471-0684","type":"print"},{"value":"1475-3081","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,9,22]]},"assertion":[{"value":"\u00a9 The Author(s), 2020. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}