{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,28]],"date-time":"2026-01-28T11:13:08Z","timestamp":1769598788102,"version":"3.49.0"},"reference-count":49,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2023,4,21]],"date-time":"2023-04-21T00:00:00Z","timestamp":1682035200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Dorabot","award":["SCHA 550\/11 and 15"],"award-info":[{"award-number":["SCHA 550\/11 and 15"]}]},{"name":"Potassco Solutions","award":["SCHA 550\/11 and 15"],"award-info":[{"award-number":["SCHA 550\/11 and 15"]}]},{"name":"DFG","award":["SCHA 550\/11 and 15"],"award-info":[{"award-number":["SCHA 550\/11 and 15"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>A warehouse delivery problem consists of a set of robots that undertake delivery jobs within a warehouse. Items are moved around the warehouse in response to events. A solution to a warehouse delivery problem is a collision-free schedule of robot movements and actions that ensures that all delivery jobs are completed and each robot is returned to its docking station. While the warehouse delivery problem is related to existing research, such as the study of multi-agent path finding (MAPF), the specific industrial requirements necessitated a novel approach that diverges from these other approaches. For example, our problem description was more suited to formalizing the warehouse in terms of a weighted directed graph rather than the more common grid-based formalization. We formalize and encode the warehouse delivery problem in Answer Set Programming (ASP) extended with difference constraints. We systematically develop and study different encoding variants, with a view to computing good quality solutions in near real-time. In particular, application specific criteria are contrasted against the traditional notion of makespan minimization as a measure of solution quality. The encoding is tested against both crafted and industry data and experiments run using the Hybrid ASP solver clingo[dl].<\/jats:p>","DOI":"10.3390\/a16040216","type":"journal-article","created":{"date-parts":[[2023,4,24]],"date-time":"2023-04-24T02:06:11Z","timestamp":1682301971000},"page":"216","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Solving an Industrial-Scale Warehouse Delivery Problem with Answer Set Programming Modulo Difference Constraints"],"prefix":"10.3390","volume":"16","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4919-7997","authenticated-orcid":false,"given":"David","family":"Rajaratnam","sequence":"first","affiliation":[{"name":"Potassco Solutions, 14467 Potsdam, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7456-041X","authenticated-orcid":false,"given":"Torsten","family":"Schaub","sequence":"additional","affiliation":[{"name":"Potassco Solutions, 14467 Potsdam, Germany"},{"name":"Institute of Computer Science, University of Potsdam, 14469 Potsdam, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4986-4881","authenticated-orcid":false,"given":"Philipp","family":"Wanko","sequence":"additional","affiliation":[{"name":"Potassco Solutions, 14467 Potsdam, Germany"},{"name":"Institute of Computer Science, University of Potsdam, 14469 Potsdam, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kai","family":"Chen","sequence":"additional","affiliation":[{"name":"Dorabot, Nanshan District, Shenzhen 518068, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sirui","family":"Liu","sequence":"additional","affiliation":[{"name":"Dorabot, Nanshan District, Shenzhen 518068, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3689-8433","authenticated-orcid":false,"given":"Tran Cao","family":"Son","sequence":"additional","affiliation":[{"name":"Department of Computer Science, New Mexico State University, Las Cruces, NM 88003, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2023,4,21]]},"reference":[{"key":"ref_1","unstructured":"de Schreye, D. (December, January 29). Answer set planning. Proceedings of the International Conference on Logic Programming (ICLP\u201999), Las Cruses, NM, USA."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/978-3-030-20528-7_1","article-title":"Train scheduling with hybrid ASP","volume":"Volume 11481","author":"Balduccini","year":"2019","journal-title":"Logic Programming and Nonmonotonic Reasoning (LPNMR\u201919)"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1017\/S1471068420000046","article-title":"Train scheduling with hybrid ASP","volume":"21","author":"Abels","year":"2021","journal-title":"Theory Pract. Log. Program."},{"key":"ref_4","unstructured":"Andr\u00e9, E., Koenig, S., Dastani, M., and Sukthankar, G. (2018, January 10\u201315). A Scheduling-Based Approach to Multi-Agent Path Finding with Weighted and Capacitated Arcs. Proceedings of the Seventeenth International Conference on Autonomous Agents and Multiagent Systems (AAMAS\u201918), Stockholm, Sweden."},{"key":"ref_5","unstructured":"Warren, D., and Szeredi, P. (1990, January 18\u201320). Logic Programs with Classical Negation. Proceedings of the Seventh International Conference on Logic Programming (ICLP\u201990), Jerusalem, Israel."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/S0004-3702(02)00187-X","article-title":"Extending and implementing the stable model semantics","volume":"138","author":"Simons","year":"2002","journal-title":"Artif. Intell."},{"key":"ref_7","unstructured":"Gebser, M., Kaminski, R., Kaufmann, B., Lindauer, M., Ostrowski, M., Romero, J., Schaub, T., and Thiele, S. (2015). Potassco User Guide, University of Potsdam. [2nd ed.]. Available online: https:\/\/potassco.sourceforge.net\/."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Gebser, M., Kaufmann, B., Otero, R., Romero, J., Schaub, T., and Wanko, P. (2013, January 14\u201318). Domain-specific Heuristics in Answer Set Programming. Proceedings of the Twenty-Seventh Conference on Artificial Intelligence, Bellevue, WA, USA.","DOI":"10.1609\/aaai.v27i1.8585"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"63","DOI":"10.3233\/FI-2016-1398","article-title":"Answer Set Programming Modulo Acyclicity","volume":"147","author":"Bomanson","year":"2016","journal-title":"Fundam. Informaticae"},{"key":"ref_10","first-page":"2:1","article-title":"Theory Solving Made Easy with Clingo 5","volume":"Volume 52","author":"Carro","year":"2016","journal-title":"Technical Communications of the Thirty-second International Conference on Logic Programming (ICLP\u201916)"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"872","DOI":"10.1017\/S1471068417000242","article-title":"Clingo goes Linear Constraints over Reals and Integers","volume":"17","author":"Janhunen","year":"2017","journal-title":"Theory Pract. Log. Program."},{"key":"ref_12","unstructured":"Surynek, P., and Yeoh, W. (2019, January 16\u201317). Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks. Proceedings of the Twelfth International Symposium on Combinatorial Search (SOCS\u201919), Napa, CA, USA."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/S0004-3702(02)00186-8","article-title":"Answer set programming and plan generation","volume":"138","author":"Lifschitz","year":"2002","journal-title":"Artif. Intell."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1007\/978-3-031-15707-3_31","article-title":"clingraph: ASP-based Visualization","volume":"Volume 13416","author":"Gottlob","year":"2022","journal-title":"Logic Programming and Nonmonotonic Reasoning (LPNMR\u201922)"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1145\/367766.368168","article-title":"Algorithm 97: Shortest Path","volume":"5","author":"Floyd","year":"1962","journal-title":"Commun. ACM"},{"key":"ref_16","first-page":"175","article-title":"Multi-agent path finding on real robots","volume":"32","author":"Svancara","year":"2019","journal-title":"AI Mag."},{"key":"ref_17","unstructured":"El Fallah Seghrouchni, A., Sukthankar, G., An, B., and Yorke-Smith, N. (2020, January 9\u201313). Research Challenges and Opportunities in Multi-Agent Path Finding and Multi-Agent Pickup and Delivery Problems. Proceedings of the Nineteenth International Conference on Autonomous Agents and Multiagent Systems (AAMAS\u201920), Auckland, New Zealand."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1613\/jair.4171","article-title":"Enhanced Partial Expansion A*","volume":"50","author":"Goldenberg","year":"2014","journal-title":"J. Artif. Intell. Res."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"103574","DOI":"10.1016\/j.artint.2021.103574","article-title":"Pairwise symmetry reasoning for multi-agent path finding search","volume":"301","author":"Li","year":"2021","journal-title":"Artif. Intell."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.artint.2014.11.001","article-title":"Subdimensional expansion for multirobot path planning","volume":"219","author":"Wagner","year":"2015","journal-title":"Artif. Intell."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1016\/j.artint.2014.11.006","article-title":"Conflict-based search for optimal multi-agent pathfinding","volume":"219","author":"Sharon","year":"2015","journal-title":"Artif. Intell."},{"key":"ref_22","unstructured":"Yang, Q., and Wooldridge, M. (2015, January 25\u201331). ICBS: Improved Conflict-Based Search Algorithm for Multi-Agent Pathfinding. Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence (IJCAI\u201915), Buenos Aires, Argentina."},{"key":"ref_23","unstructured":"Kambhampati, R. (2016, January 9\u201315). Improved Solvers for Bounded-Suboptimal Multi-Agent Path Finding. Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence (IJCAI\u201916), New York, NY, USA."},{"key":"ref_24","first-page":"55","article-title":"MAPP a Scalable Multi-Agent Path Planning Algorithm with Tractability and Completeness Guarantees","volume":"42","author":"Wang","year":"2011","journal-title":"J. Artif. Intell. Res."},{"key":"ref_25","unstructured":"Walsh, T. (2011, January 16\u201322). Push and Swap: Fast Cooperative Path-Finding with Completeness Guarantees. Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence (IJCAI\u201911), Barcelona, Spain."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1613\/jair.4447","article-title":"Push and Rotate: A Complete Multi-agent Pathfinding Algorithm","volume":"51","author":"Witteveen","year":"2014","journal-title":"J. Artif. Intell. Res."},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Li, J., Ruml, W., and Koenig, S. (2021, January 2\u20139). EECBS: A bounded-suboptimal search for multi-agent path finding. Proceedings of the Thirty-Fifth AAAI Conference on Artificial Intelligence, Virtual Event.","DOI":"10.1609\/aaai.v35i14.17466"},{"key":"ref_28","unstructured":"Barer, M., Sharon, G., Stern, R., and Felner, A. (2014, January 15\u201317). Suboptimal variants of the conflict-based search algorithm for the multi-agent pathfinding problem. Proceedings of the Seventh Annual Symposium on Combinatorial Search, Prague, Czech Republic."},{"key":"ref_29","unstructured":"Walsh, T. (, January 16\u201322). Bounded suboptimal search: A direct approach using inadmissible estimates. Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, Barcelona, Spain."},{"key":"ref_30","unstructured":"Ma, H., Harabor, D., Stuckey, P.J., Li, J., and Koenig, S. (February, January 27). Searching with consistent prioritization for multi-agent path finding. Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence, Honolulu, HI, USA."},{"key":"ref_31","unstructured":"Silver, D. (2005, January 1\u20135). Cooperative pathfinding. Proceedings of the First Artificial Intelligence and Interactive Digital Entertainment Conference, Marina Del Rey, CA, USA."},{"key":"ref_32","unstructured":"Jonker, C., Marsella, S., Thangarajah, J., and Tuyls, K. (2016, January 9\u201313). Optimal Target Assignment and Path Finding for Teams of Agents. Proceedings of the Fifteenth International Conference on Autonomous Agents and Multiagent Systems (AAMAS\u201916), Singapore."},{"key":"ref_33","unstructured":"Lang, J. (2018, January 13\u201319). Multi-Agent Path Finding with Deadlines. Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI\u201918), Stockholm, Sweden."},{"key":"ref_34","unstructured":"Satinder, P., and Markovitch, S. (2017, January 4\u20139). Multi-Agent Path Finding with Delay Probabilities. Proceedings of the Thirty-First National Conference on Artificial Intelligence (AAAI\u201917), San Francisco, CA, USA."},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Li, J., Tinka, A., Kiesel, S., Durham, J.W., Kumar, T.S., and Koenig, S. (2021, January 2\u20139). Lifelong multi-agent path finding in large-scale warehouses. Proceedings of the Thirty-Fifth AAAI Conference on Artificial Intelligence, Virtual Event.","DOI":"10.1609\/aaai.v35i13.17344"},{"key":"ref_36","unstructured":"Kraus, S. (2019, January 10\u201316). Multi-Agent Pathfinding with Continuous Time. Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI\u201919), Macao, China."},{"key":"ref_37","unstructured":"Surynek, P., and Yeoh, W. (2019, January 16\u201317). On SAT-Based Approaches for Multi-Agent Path Finding with the Sum-of-Costs Objective. Proceedings of the Twelfth International Symposium on Combinatorial Search (SOCS\u201919), Napa, CA, USA."},{"key":"ref_38","unstructured":"Surynek, P., and Yeoh, W. (2019, January 16\u201317). Multi-Agent Path Finding with Continuous Time and Geometric Agents Viewed through Satisfiability Modulo Theories (SMT). Proceedings of the Twelfth International Symposium on Combinatorial Search (SOCS\u201919), Napa, CA, USA."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1613\/jair.1.11734","article-title":"Robust Multi-Agent Path Finding and Executing","volume":"67","author":"Atzmon","year":"2020","journal-title":"J. Artif. Intell. Res."},{"key":"ref_40","unstructured":"Schuurmans, D., and Wellman, M. (2016, January 12\u201317). Multi-Agent Path Finding with Payload Transfers and the Package-Exchange Robot-Routing Problem. Proceedings of the Thirtieth National Conference on Artificial Intelligence (AAAI\u201916), Phoenix, AZ, USA."},{"key":"ref_41","unstructured":"Coles, A., Coles, A., Edelkamp, S., Magazzeni, D., and Sanner,, S. (2016, January 12\u201317). Multi-Agent Path Finding with Kinematic Constraints. Proceedings of the Twenty-Sixth International Conference on Automated Planning and Scheduling (ICAPS\u201916), London, UK."},{"key":"ref_42","unstructured":"Erdem, E., Kisa, D., \u00d6ztok, U., and Sch\u00fcller, P. (2013, January 14\u201318). A General Formal Framework for Pathfinding Problems with Multiple Agents. Proceedings of the Twenty-Seventh Conference on Artificial Intelligence, Bellevue, WA, USA."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"502","DOI":"10.1017\/S1471068418000200","article-title":"Experimenting with robotic intra-logistics domains","volume":"18","author":"Gebser","year":"2018","journal-title":"Theory Pract. Log. Program."},{"key":"ref_44","unstructured":"Sierra, C. (2017, January 19\u201325). Generalized Target Assignment and Path Finding Using Answer Set Programming. Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI\u201917), Melbourne, Australia."},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"26886","DOI":"10.1109\/ACCESS.2021.3053547","article-title":"A Compact Answer Set Programming Encoding of Multi-Agent Pathfinding","volume":"9","author":"Baier","year":"2021","journal-title":"IEEE Access"},{"key":"ref_46","doi-asserted-by":"crossref","unstructured":"Pianpak, P., Son, T., Toups, Z., and Yeoh, W. (2019, January 13\u201315). A distributed solver for multi-agent path finding problems. Proceedings of the First International Conference on Distributed Artificial Intelligence (DAI\u201919), Beijing, China.","DOI":"10.1145\/3356464.3357702"},{"key":"ref_47","unstructured":"Leet, C., Li, J., and Koenig, S. (March, January 22). Shard Systems: Scalable, Robust and Persistent Multi-Agent Path Finding with Performance Guarantees. Proceedings of the Thirty-Sixth AAAI Conference on Artificial Intelligence, Virtual Event."},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"99","DOI":"10.4204\/EPTCS.345.24","article-title":"DMAPF: A Decentralized and Distributed Solver for Multi-Agent Path Finding Problem with Obstacles","volume":"345","author":"Pianpak","year":"2021","journal-title":"Electron. Proc. Theor. Comput. Sci. (EPTCS)"},{"key":"ref_49","doi-asserted-by":"crossref","unstructured":"Pianpak, P., and Son, T.C. (2022, January 16\u201318). Improving Problem Decomposition and Regulation in Distributed Multi-Agent Path Finder (DMAPF). Proceedings of the PRIMA 2022: Principles and Practice of Multi-Agent Systems, Valencia, Spain.","DOI":"10.1007\/978-3-031-21203-1_10"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/16\/4\/216\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T19:21:01Z","timestamp":1760124061000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/16\/4\/216"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,4,21]]},"references-count":49,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2023,4]]}},"alternative-id":["a16040216"],"URL":"https:\/\/doi.org\/10.3390\/a16040216","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,4,21]]}}}