Print Email Facebook Twitter Integrated Task Assignment and Path Planning for Capacitated Multi-Agent Pickup and Delivery Title Integrated Task Assignment and Path Planning for Capacitated Multi-Agent Pickup and Delivery Author Chen, Zhe (Monash University) Alonso-Mora, J. (TU Delft Learning & Autonomous Control) Bai, X. (TU Delft Learning & Autonomous Control; Shenzhen University) Harabor, Daniel Damir (Monash University) Stuckey, Peter James (Monash University) Date 2021 Abstract Multi-agent Pickup and Delivery (MAPD) is a challenging industrial problem where a team of robots is tasked with transporting a set of tasks, each from an initial location and each to a specified target location. Appearing in the context of automated warehouse logistics and automated mail sortation, MAPD requires first deciding which robot is assigned what task (i.e., Task Assignment or TA) followed by a subsequent coordination problem where each robot must be assigned collision-free paths so as to successfully complete its assignment (i.e., Multi-Agent Path Finding or MAPF). Leading methods in this area solve MAPD sequentially: first assigning tasks, then assigning paths. In this work we propose a new coupled method where task assignment choices are informed by actual delivery costs instead of by lower-bound estimates. The main ingredients of our approach are a marginal-cost assignment heuristic and a meta-heuristic improvement strategy based on Large Neighbourhood Search. As a further contribution, we also consider a variant of the MAPD problem where each robot can carry multiple tasks instead of just one. Numerical simulations show that our approach yields efficient and timely solutions and we report significant improvement compared with other recent methods from the literature. Subject Collision avoidanceMotion and Path PlanningPath planningPath Planning for Multiple Mobile Robots or AgentsPlanningRobotsScalabilitySearch problemsTask analysisTask and Motion Planning To reference this document use: http://resolver.tudelft.nl/uuid:9e5cc563-580e-43b8-8874-40f96f4f0537 DOI https://doi.org/10.1109/LRA.2021.3074883 Embargo date 2021-10-21 ISSN 2377-3766 Source IEEE Robotics and Automation Letters, 6 (3), 5816-5823 Bibliographical note Green Open Access added to TU Delft Institutional Repository 'You share, we take care!' - Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public. Part of collection Institutional Repository Document type journal article Rights © 2021 Zhe Chen, J. Alonso-Mora, X. Bai, Daniel Damir Harabor, Peter James Stuckey Files PDF Integrated_Task_Assignmen ... livery.pdf 1.63 MB Close viewer /islandora/object/uuid:9e5cc563-580e-43b8-8874-40f96f4f0537/datastream/OBJ/view