{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,15]],"date-time":"2026-01-15T00:08:40Z","timestamp":1768435720131,"version":"3.49.0"},"reference-count":36,"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>The multi-agent path finding (MAPF) problem is a combinatorial search problem that aims at finding paths for multiple agents (e.g., robots) in an environment (e.g., an autonomous warehouse) such that no two agents collide with each other, and subject to some constraints on the lengths of paths. We consider a general version of MAPF, called mMAPF, that involves multi-modal transportation modes (e.g., due to velocity constraints) and consumption of different types of resources (e.g., batteries). The real-world applications of mMAPF require flexibility (e.g., solving variations of mMAPF) as well as explainability. Our earlier studies on mMAPF have focused on the former challenge of flexibility. In this study, we focus on the latter challenge of explainability, and introduce a method for generating explanations for queries regarding the feasibility and optimality of solutions, the nonexistence of solutions, and the observations about solutions. Our method is based on answer set programming.<\/jats:p>","DOI":"10.1017\/s1471068420000320","type":"journal-article","created":{"date-parts":[[2020,9,22]],"date-time":"2020-09-22T02:43:15Z","timestamp":1600742595000},"page":"974-989","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":7,"title":["Explanation Generation for Multi-Modal Multi-Agent Path Finding with Optimal Resource Utilization using Answer Set Programming"],"prefix":"10.1017","volume":"20","author":[{"given":"AYSU","family":"BOGATARKAN","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":"S1471068420000320_ref4","unstructured":"4. Brain, M. , Gebser, M. , P\u00fchrer, J. , Schaub, T. , Tompits, H. , and Woltran, S. 2007. \u201cthat is illogical captain!\u201d\u2013the debugging support tool spock for answer-set programs: System description."},{"key":"S1471068420000320_ref25","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068410000256"},{"key":"S1471068420000320_ref7","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 Pract. Log. Program. 20,"},{"key":"S1471068420000320_ref32","unstructured":"32. Smith, D. E. 2012. Planning as an iterative process. In Proc. of AAAI, Hoffmann, J. and Selman, B. , Eds."},{"key":"S1471068420000320_ref9","doi-asserted-by":"crossref","unstructured":"9. Dam\u00e1sio, C. V. , Analyti, A. , and Antoniou, G. 2013. Justifications for logic programming. In Proc. of LPNMR. 530\u2013542.","DOI":"10.1007\/978-3-642-40564-8_53"},{"key":"S1471068420000320_ref23","volume-title":"The Logic Programming Paradigm: a 25-Year Perspective","author":"Marek","year":"1999"},{"key":"S1471068420000320_ref21","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(02)00186-8"},{"key":"S1471068420000320_ref36","doi-asserted-by":"crossref","unstructured":"36. Yu, J. and LaValle, S. M. 2013. Planning optimal paths for multiple robots on graphs. In Proc. of ICRA. 3612\u20133617.","DOI":"10.1109\/ICRA.2013.6631084"},{"key":"S1471068420000320_ref24","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1023\/A:1018930122475","article-title":"Logic programs with stable model semantics as a constraint programming paradigm","author":"Niemel\u00e4","year":"1999","journal-title":"Annals of Mathematics and Artificial Intelligence 25"},{"key":"S1471068420000320_ref35","unstructured":"35. Wang, K.-H. C. and Botea, A. 2008. Fast and memory-efficient multi-agent pathfinding. In Proc. of ICAPS. 380\u2013387."},{"key":"S1471068420000320_ref14","doi-asserted-by":"crossref","unstructured":"14. Erdem, E. , Kisa, D. G. , Oztok, U. , and Schueller, P. 2013. A general formal framework for pathfinding problems with multiple agents. In Proc. of AAAI.","DOI":"10.1609\/aaai.v27i1.8592"},{"key":"S1471068420000320_ref12","doi-asserted-by":"crossref","first-page":"591","DOI":"10.1613\/jair.2502","article-title":"A multiagent approach to autonomous intersection management","author":"Dresner","year":"2008","journal-title":"J. Artif. Intell. Res. (JAIR) 31"},{"key":"S1471068420000320_ref1","unstructured":"1. Almagor, S. and Lahijanian, M. 2020. Explainable multi agent path finding. In Proc. of AAMAS. 34\u201342."},{"key":"S1471068420000320_ref33","unstructured":"33. Stern, R. , Sturtevant, N. R. , Felner, A. , Koenig, S. , Ma, H. , Walker, T. T. , Li, J. , Atzmon, D. , Cohen, L. , Kumar, T. K. S. , Bart\u00e1k, R. , and Boyarski, E. 2019. Multi-agent pathfinding: Definitions, variants, and benchmarks. In Proc. of SOCS. 151\u2013159."},{"key":"S1471068420000320_ref5","doi-asserted-by":"crossref","first-page":"587","DOI":"10.1017\/S1471068416000454","article-title":"Justifications for programs with disjunctive and causal-choice rules","volume":"5","author":"Cabalar","year":"2016","journal-title":"Theory Pract. Log. Program. 16,"},{"key":"S1471068420000320_ref30","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2014.11.006"},{"key":"S1471068420000320_ref26","first-page":"1","article-title":"Justifications for logic programs under answer set semantics","volume":"1","author":"Pontelli","year":"2009","journal-title":"Theory Pract. Log. Program. 9,"},{"key":"S1471068420000320_ref28","unstructured":"28. Schulz, C. and Toni, F. 2013. Aba-based answer set justification. Theory Pract. Log. Program. 13, 4-5-Online-Supplement."},{"key":"S1471068420000320_ref2","doi-asserted-by":"crossref","unstructured":"2. Bogatarkan, A. , Erdem, E. , Kleiner, A. , and Patoglu, V. 2020. Multi-modal multi-agent path finding with optimal resource utilization. In Proceedings of 5th International Conference on the Industry 4.0 Model for Advanced Manufacturing. 313\u2013324.","DOI":"10.1007\/978-3-030-46212-3_24"},{"key":"S1471068420000320_ref29","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1017\/S1471068414000702","article-title":"Justifying answer sets using argumentation","volume":"1","author":"Schulz","year":"2016","journal-title":"Theory Pract. Log. Program. 16,"},{"key":"S1471068420000320_ref8","doi-asserted-by":"crossref","unstructured":"8. Chouhan, S. S. and Niyogi, R. 2015. DMAPP: A distributed multi-agent path planning algorithm. In Proc. of AI. 123\u2013135.","DOI":"10.1007\/978-3-319-26350-2_11"},{"key":"S1471068420000320_ref31","doi-asserted-by":"crossref","unstructured":"31. Silver, D. 2005. Cooperative pathfinding. In Proc. of AIIDE. 117\u2013122.","DOI":"10.1609\/aiide.v1i1.18726"},{"key":"S1471068420000320_ref27","unstructured":"27. Ratner, D. and Warmuth, M. K. 1986. Finding a shortest solution for the n \\[ \\times \\] n extension of the 15-puzzle is intractable. In Proc. of AAAI. 168\u2013172."},{"key":"S1471068420000320_ref3","unstructured":"3. Bogatarkan, A. , Patoglu, V. , and Erdem, E. 2019. A declarative method for dynamic multi-agent path finding. In Proceedings of the 5th Global Conference on Artificial Intelligence. 54\u201367."},{"key":"S1471068420000320_ref20","unstructured":"20. Jansen, R. and Sturtevant, N. 2008. A new approach to cooperative pathfinding. In Proc. of AAMAS. 1401\u20131404."},{"key":"S1471068420000320_ref34","doi-asserted-by":"crossref","unstructured":"34. Surynek, P. 2012. On propositional encodings of cooperative path-finding. In Proc. of ICTAI. 524\u2013531.","DOI":"10.1109\/ICTAI.2012.77"},{"key":"S1471068420000320_ref15","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1017\/S1471068413000598","article-title":"Generating explanations for biomedical queries","volume":"1","author":"Erdem","year":"2015","journal-title":"Theory Pract. Log. Program. 15,"},{"key":"S1471068420000320_ref22","doi-asserted-by":"crossref","unstructured":"22. Luna, R. and Bekris, K. E. 2011. Efficient and complete centralized multi-robot path planning. In Proc. of IROS. 3268\u20133275.","DOI":"10.1109\/IROS.2011.6095085"},{"key":"S1471068420000320_ref6","doi-asserted-by":"crossref","first-page":"603","DOI":"10.1017\/S1471068414000234","article-title":"Causal graph justifications of logic programs","volume":"4","author":"Cabalar","year":"2014","journal-title":"Theory Pract. Log. Program. 14,"},{"key":"S1471068420000320_ref17","unstructured":"17. Gebser, M. , P\u00fchrer, J. , Schaub, T. , and Tompits, H. 2008. A meta-programming technique for debugging answer-set programs. In Proc. of AAAI. 448\u2013453."},{"key":"S1471068420000320_ref10","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"S1471068420000320_ref18","unstructured":"18. Gelfond, M. and Lifschitz, V. 1988. The stable model semantics for logic programming. In Proceedings of International Logic Programming Conference and Symposium. 1070\u20131080."},{"key":"S1471068420000320_ref13","doi-asserted-by":"crossref","unstructured":"13. Eifler, R. , Cashmore, M. , Hoffmann, J. , Magazzeni, D. , and Steinmetz, M. 2020. A new approach to plan-space explanation: Analyzing plan-property dependencies in oversubscription planning. In Proc. of AAAI. 9818\u20139826.","DOI":"10.1609\/aaai.v34i06.6534"},{"key":"S1471068420000320_ref11","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068418000492"},{"key":"S1471068420000320_ref16","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1017\/S1471068418000534","article-title":"Answering the \u201cwhy\u201d in answer set programming - A survey of explanation approaches","volume":"2","author":"Fandinno","year":"2019","journal-title":"Theory Pract. Log. Program. 19,"},{"key":"S1471068420000320_ref19","doi-asserted-by":"publisher","DOI":"10.1007\/BF03037169"}],"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\/S1471068420000320","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,19]],"date-time":"2022-11-19T11:42:39Z","timestamp":1668858159000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1471068420000320\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9,22]]},"references-count":36,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2020,11]]}},"alternative-id":["S1471068420000320"],"URL":"https:\/\/doi.org\/10.1017\/s1471068420000320","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"}}]}}