{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T23:46:01Z","timestamp":1740181561131,"version":"3.37.3"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,12,8]],"date-time":"2022-12-08T00:00:00Z","timestamp":1670457600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,12,8]],"date-time":"2022-12-08T00:00:00Z","timestamp":1670457600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"crossref","award":["20H04245"],"award-info":[{"award-number":["20H04245"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["17KT0044"],"award-info":[{"award-number":["17KT0044"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["SN COMPUT. SCI."],"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We propose a method called <jats:italic>path and action planning with orientation<\/jats:italic> (PAPO) that efficiently generates collision-free paths to satisfy environmental constraints, such as restricted path width and node size, for the <jats:italic>multi-agent pickup and delivery in non-uniform environment<\/jats:italic> (N-MAPD) problem. The MAPD problem, wherein multiple agents repeatedly pick up and carry materials without collisions, has attracted considerable attention; however, conventional MAPD algorithms assume a specially designed environment and thus use simple, uniform models with few environmental constraints. Such conventional algorithms cannot be applied to realistic applications where agents need to move in more complex and restricted environments. For example, the actions and orientations of agents are strictly restricted by the sizes of agents and carrying materials and the width of the passages at a construction site and a disaster area. In our N-MAPD formulation, which is an extension of the MAPD problem to apply to non-uniform environments with constraints, PAPO considers not only the path to the destination but also the agents\u2019 direction, orientation, and timing of rotation. It is costly to consider all these factors, especially when the number of nodes is large. Our method can efficiently generate acceptable plans by exploring the search space via path planning, action planning, and conflict resolution in a phased manner. We experimentally evaluated the performance of PAPO by comparing it with our previous method, which is the preliminary version of PAPO, the baseline method in a centralized approach, and fundamental meta-heuristic algorithms. Finally, we demonstrate that PAPO can efficiently generate sub-optimal paths for N-MAPD instances.<\/jats:p>","DOI":"10.1007\/s42979-022-01475-5","type":"journal-article","created":{"date-parts":[[2022,12,8]],"date-time":"2022-12-08T17:03:36Z","timestamp":1670519016000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Efficient Path and Action Planning Method for Multi-Agent Pickup and Delivery Tasks under Environmental Constraints"],"prefix":"10.1007","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5577-3703","authenticated-orcid":false,"given":"Tomoki","family":"Yamauchi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuki","family":"Miyashita","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Toshiharu","family":"Sugawara","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,12,8]]},"reference":[{"issue":"2","key":"1475_CR1","doi-asserted-by":"publisher","first-page":"404","DOI":"10.1109\/TRO.2018.2793890","volume":"34","author":"J Alonso-Mora","year":"2018","unstructured":"Alonso-Mora J, Beardsley P, Siegwart R. Cooperative Collision Avoidance for Nonholonomic Robots. IEEE Trans Rob. 2018;34(2):404\u201320. https:\/\/doi.org\/10.1109\/TRO.2018.2793890.","journal-title":"IEEE Trans Rob"},{"issue":"12","key":"1475_CR2","doi-asserted-by":"publisher","first-page":"1501","DOI":"10.1177\/0278364915576234","volume":"34","author":"D Bareiss","year":"2015","unstructured":"Bareiss D, van den Berg J. Generalized reciprocal collision avoidance. Int J Robot Res. 2015;34(12):1501\u201314. https:\/\/doi.org\/10.1177\/0278364915576234.","journal-title":"Int J Robot Res"},{"issue":"3","key":"1475_CR3","doi-asserted-by":"publisher","first-page":"175","DOI":"10.3233\/AIC-190621","volume":"32","author":"R Bart\u00e1k","year":"2019","unstructured":"Bart\u00e1k R, \u0160vancara J, \u0160kopkov\u00e1 V, et al. Multi-agent path finding on real robots. AI Commun. 2019;32(3):175\u201389. https:\/\/doi.org\/10.3233\/AIC-190621.","journal-title":"AI Commun"},{"key":"1475_CR4","unstructured":"Bellusci M, Basilico N, Amigoni F. Multi-Agent Path Finding in Configurable Environments. In: Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems, 2020;pp 159\u2013167."},{"key":"1475_CR5","unstructured":"Boyarski E, Felner A, Stern R, et al. ICBS: improved conflict-based search algorithm for multi-agent pathfinding. In: Twenty-Fourth International Joint Conference on Artificial Intelligence 2015."},{"key":"1475_CR6","doi-asserted-by":"crossref","unstructured":"Boyrasky E, Felner A, Sharon G, et al. Don\u2019t split, try to work it out: bypassing conflicts in multi-agent pathfinding. In: Twenty-Fifth International Conference on Automated Planning and Scheduling 2015.","DOI":"10.1609\/icaps.v25i1.13725"},{"key":"1475_CR7","unstructured":"Felner A, Stern R, Shimony SE, et al. Search-based optimal solvers for the multi-agent pathfinding problem: Summary and challenges. In: Tenth Annual Symposium on Combinatorial Search 2017."},{"key":"1475_CR8","unstructured":"Ho F, Salta A, Geraldes R, et al. Multi-agent path finding for UAV traffic management. In: Proceedings of the 18th international conference on autonomous agents and multiagent systems, international foundation for autonomous agents and multiagent systems, 2019;pp 131\u2013139."},{"key":"1475_CR9","doi-asserted-by":"crossref","unstructured":"H\u00f6nig W, Kumar TS, Cohen L, et al. Multi-agent path finding with kinematic constraints. In: Twenty-sixth international conference on automated planning and scheduling 2016.","DOI":"10.24963\/ijcai.2017\/684"},{"key":"1475_CR10","unstructured":"Huang T, Dilkina B, Koenig S. Learning Node-Selection Strategies in Bounded-Suboptimal Conflict-Based Search for Multi-Agent Path Finding. In: Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems, 2021;pp 611\u2013619."},{"key":"1475_CR11","unstructured":"Kou NM, Peng C, Yan X, et al. Multi-agent Path Planning with Non-constant Velocity Motion. In: Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, International Foundation for Autonomous Agents and Multiagent Systems, 2019;pp. 2069\u20132071."},{"key":"1475_CR12","doi-asserted-by":"crossref","unstructured":"Krakowczyk D, Wolff J, Ciobanu A, et al. Developing a distributed drone delivery system with a hybrid behavior planning system. In: Joint German\/Austrian Conference on Artificial Intelligence (K\u00fcnstliche Intelligenz), Springer, 2018;pp 107\u2013114.","DOI":"10.1007\/978-3-030-00111-7_10"},{"issue":"01","key":"1475_CR13","doi-asserted-by":"publisher","first-page":"7627","DOI":"10.1609\/aaai.v33i01.33017627","volume":"33","author":"J Li","year":"2019","unstructured":"Li J, Surynek P, Felner A, et al. Multi-agent path finding for large agents. Proc AAAI Conf Artif Intell. 2019;33(01):7627\u201334. https:\/\/doi.org\/10.1609\/aaai.v33i01.33017627.","journal-title":"Proc AAAI Conf Artif Intell"},{"issue":"2","key":"1475_CR14","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1109\/LRA.2020.3044834","volume":"6","author":"J Li","year":"2021","unstructured":"Li J, Ran M, Xie L. Efficient trajectory planning for multiple non-holonomic mobile robots via prioritized trajectory optimization. IEEE Robot Autom Lett. 2021;6(2):405\u201312. https:\/\/doi.org\/10.1109\/LRA.2020.3044834.","journal-title":"IEEE Robot Autom Lett"},{"key":"1475_CR15","doi-asserted-by":"publisher","unstructured":"Li M, Qin Z, Jiao Y, et al. Efficient Ridesharing Order Dispatching with Mean Field Multi-Agent Reinforcement Learning. In: The World Wide Web Conference, ACM, 2019b;pp 983\u2013994, https:\/\/doi.org\/10.1145\/3308558.3313433.","DOI":"10.1145\/3308558.3313433"},{"key":"1475_CR16","unstructured":"Liu M, Ma H, Li J, et al. Task and Path Planning for Multi-Agent Pickup and Delivery. In: Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, International Foundation for Autonomous Agents and Multiagent Systems, 2019;pp 1152\u20131160"},{"key":"1475_CR17","doi-asserted-by":"crossref","unstructured":"Ma H, Tovey C, Sharon G, et al. Multi-agent path finding with payload transfers and the package-exchange robot-routing problem. In: Thirtieth AAAI Conference on Artificial Intelligence 2016.","DOI":"10.1609\/aaai.v30i1.10409"},{"key":"1475_CR18","unstructured":"Ma H, Koenig S, Ayanian N, et al. Overview: Generalizations of multi-agent path finding to real-world scenarios. arXiv preprint 2017a arXiv:1702.05515."},{"key":"1475_CR19","unstructured":"Ma H, Li J, Kumar T, et al. Lifelong multi-agent path finding for online pickup and delivery tasks. In: Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems, International Foundation for Autonomous Agents and Multiagent Systems, 2017b;pp 837\u2013845."},{"key":"1475_CR20","doi-asserted-by":"publisher","unstructured":"Ma H, H\u00f6nig W, Kumar TS, et al. Lifelong Path Planning with Kinematic Constraints for Multi-Agent Pickup and Delivery. In: Proceedings of the AAAI Conference on Artificial Intelligence, 2019;pp 7651\u20137658, https:\/\/doi.org\/10.1609\/aaai.v33i01.33017651.","DOI":"10.1609\/aaai.v33i01.33017651"},{"key":"1475_CR21","unstructured":"Machida M. Polynomial-Time Multi-Agent Pathfinding with Heterogeneous and Self-Interested Agents. In: Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, International Foundation for Autonomous Agents and Multiagent Systems, 2019;pp 2105\u20132107."},{"key":"1475_CR22","unstructured":"Morris R, Pasareanu CS, Luckow K, et al. Planning, scheduling and monitoring for airport surface operations. In: Workshops at the Thirtieth AAAI Conference on Artificial Intelligence 2016."},{"key":"1475_CR23","doi-asserted-by":"publisher","unstructured":"Okumura K, Machida M, D\u00e9fago X, et al. Priority Inheritance with Backtracking for Iterative Multi-agent Path Finding. In: Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI-19. International Joint Conferences on Artificial Intelligence Organization, 2019;pp 535\u2013542, https:\/\/doi.org\/10.24963\/ijcai.2019\/76.","DOI":"10.24963\/ijcai.2019\/76"},{"key":"1475_CR24","unstructured":"Okumura K, Tamura Y, D\u00e9fago X. Time-Independent Planning for Multiple Moving Agents. In: Proceedings of the AAAI Conference on Artificial Intelligence, 2021;pp 11,299\u201311,307."},{"key":"1475_CR25","unstructured":"Salzman O, Stern R. Research Challenges and Opportunities in Multi-Agent Path Finding and Multi-Agent Pickup and Delivery Problems. In: Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems, 2020;pp 1711\u20131715."},{"key":"1475_CR26","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1016\/j.artint.2014.11.006","volume":"219","author":"G Sharon","year":"2015","unstructured":"Sharon G, Stern R, Felner A, et al. Conflict-based search for optimal multi-agent pathfinding. Artif Intell. 2015;219:40\u201366. https:\/\/doi.org\/10.1016\/j.artint.2014.11.006.","journal-title":"Artif Intell"},{"key":"1475_CR27","doi-asserted-by":"crossref","unstructured":"Silver D. Cooperative Pathfinding. In: Proceedings of the First AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment. AAAI Press, AIIDE\u201905, 2005;pp 117\u2013122.","DOI":"10.1609\/aiide.v1i1.18726"},{"issue":"3","key":"1475_CR28","doi-asserted-by":"publisher","first-page":"1587","DOI":"10.1007\/s10115-018-1285-8","volume":"60","author":"A Sugiyama","year":"2019","unstructured":"Sugiyama A, Sea V, Sugawara T. Emergence of divisional cooperation with negotiation and re-learning and evaluation of flexibility in continuous cooperative patrol problem. Knowl Inf Syst. 2019;60(3):1587\u2013609. https:\/\/doi.org\/10.1007\/s10115-018-1285-8.","journal-title":"Knowl Inf Syst"},{"key":"1475_CR29","doi-asserted-by":"publisher","unstructured":"Surynek P. On Satisfisfiability Modulo Theories in Continuous Multi-Agent Path Finding: Compilation-based and Search-based Approaches Compared. In: Proceedings of the 12th International Conference on Agents and Artificial Intelligence - Volume 2: ICAART, INSTICC. SciTePress, 2020;pp 182\u2013193, https:\/\/doi.org\/10.5220\/0008980101820193.","DOI":"10.5220\/0008980101820193"},{"key":"1475_CR30","doi-asserted-by":"publisher","unstructured":"Tang S, Kumar V. Safe and complete trajectory generation for robot teams with higher-order dynamics. In: 2016 IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS), 2016;pp 1894\u20131901, https:\/\/doi.org\/10.1109\/IROS.2016.7759300.","DOI":"10.1109\/IROS.2016.7759300"},{"key":"1475_CR31","doi-asserted-by":"publisher","unstructured":"Tsuzuki MdSG, de Castro Martins T, Takase FK. ROBOT PATH PLANNING USING SIMULATED ANNEALING. IFAC Proceedings Volumes. 2006;39(3):175\u201380. https:\/\/doi.org\/10.3182\/20060517-3-FR-2903.00105, https:\/\/www.sciencedirect.com\/science\/article\/pii\/S1474667015358250, 12th IFAC Symposium on Information Control Problems in Manufacturing.","DOI":"10.3182\/20060517-3-FR-2903.00105"},{"key":"1475_CR32","unstructured":"Veloso M, Biswas J, Coltin B, et al. CoBots: Robust Symbiotic Autonomous Mobile Service Robots. In: Proceedings of the 24th International Conference on Artificial Intelligence. AAAI Press, IJCAI\u201915, 2015;pp 4423\u20134429."},{"issue":"2","key":"1475_CR33","doi-asserted-by":"publisher","first-page":"1119","DOI":"10.1109\/LRA.2020.2967317","volume":"5","author":"H Wang","year":"2020","unstructured":"Wang H, Rubenstein M. Walk, Stop, Count, and Swap: Decentralized Multi-Agent Path Finding With Theoretical Guarantees. IEEE Robotics and Automation Letters. 2020;5(2):1119\u201326. https:\/\/doi.org\/10.1109\/LRA.2020.2967317.","journal-title":"IEEE Robotics and Automation Letters"},{"key":"1475_CR34","first-page":"55","volume":"42","author":"KHC Wang","year":"2011","unstructured":"Wang KHC, Botea A. MAPP: a scalable multi-agent path planning algorithm with tractability and completeness guarantees. J Artif Intell Res. 2011;42:55\u201390.","journal-title":"J Artif Intell Res"},{"issue":"1","key":"1475_CR35","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1609\/aimag.v29i1.2082","volume":"29","author":"PR Wurman","year":"2008","unstructured":"Wurman PR, D\u2019Andrea R, Mountz M. Coordinating hundreds of cooperative, autonomous vehicles in warehouses. AI Magn. 2008;29(1):9\u20139. https:\/\/doi.org\/10.1609\/aimag.v29i1.2082.","journal-title":"AI Magn"},{"key":"1475_CR36","doi-asserted-by":"publisher","unstructured":"Yakovlev. K, Andreychuk. A, Rybeck\u00fd. T, et al. On the Application of Safe-Interval Path Planning to a Variant of the Pickup and Delivery Problem. In: Proceedings of the 17th International Conference on Informatics in Control, Automation and Robotics - Volume 1: ICINCO, INSTICC. SciTePress, 2020;pp 521\u2013528, https:\/\/doi.org\/10.5220\/0009888905210528.","DOI":"10.5220\/0009888905210528"},{"key":"1475_CR37","doi-asserted-by":"publisher","unstructured":"Yamauchi T, Miyashita Y, Sugawara T. Path and Action Planning in Non-uniform Environments for Multi-agent Pickup and Delivery Tasks. In: European Conference on Multi-Agent Systems, Springer, 2021;pp 37\u201354, https:\/\/doi.org\/10.1007\/978-3-030-82254-5_3.","DOI":"10.1007\/978-3-030-82254-5_3"},{"issue":"11","key":"1475_CR38","doi-asserted-by":"publisher","first-page":"712","DOI":"10.1287\/mnsc.17.11.712","volume":"17","author":"JY Yen","year":"1971","unstructured":"Yen JY. Finding the k shortest loopless paths in a network. Manag Sci. 1971;17(11):712\u20136. https:\/\/doi.org\/10.1287\/mnsc.17.11.712.","journal-title":"Manag Sci"},{"issue":"4","key":"1475_CR39","doi-asserted-by":"publisher","first-page":"279","DOI":"10.3233\/WEB-150326","volume":"13","author":"K Yoneda","year":"2015","unstructured":"Yoneda K, Sugiyama A, Kato C, et al. Learning and relearning of target decision strategies in continuous coordinated cleaning tasks with shallow coordination1. Web Intell. 2015;13(4):279\u201394. https:\/\/doi.org\/10.3233\/WEB-150326.","journal-title":"Web Intell"},{"key":"1475_CR40","doi-asserted-by":"publisher","unstructured":"Yoshida N, Noda I, Sugawara T. Multi-agent Service Area Adaptation for Ride-Sharing Using Deep Reinforcement Learning. In: International Conference on Practical Applications of Agents and Multi-Agent Systems, Springer, 2020;pp 363\u2013375, https:\/\/doi.org\/10.1007\/978-3-030-49778-1_29.","DOI":"10.1007\/978-3-030-49778-1_29"},{"key":"1475_CR41","doi-asserted-by":"crossref","unstructured":"Zhang H, Li J, Surynek P, et al. Multi-Agent Path Finding with Mutex Propagation. In: Proceedings of the International Conference on Automated Planning and Scheduling, 2020;pp. 323\u2013332.","DOI":"10.1609\/icaps.v30i1.6677"}],"container-title":["SN Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42979-022-01475-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s42979-022-01475-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42979-022-01475-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,7]],"date-time":"2023-01-07T22:30:00Z","timestamp":1673130600000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s42979-022-01475-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,8]]},"references-count":41,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2023,1]]}},"alternative-id":["1475"],"URL":"https:\/\/doi.org\/10.1007\/s42979-022-01475-5","relation":{},"ISSN":["2661-8907"],"issn-type":[{"type":"electronic","value":"2661-8907"}],"subject":[],"published":{"date-parts":[[2022,12,8]]},"assertion":[{"value":"31 January 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 October 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 December 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"On behalf of all authors, the corresponding author states that there is no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"83"}}