Multi-Agent Path Finding with Payload Transfers and the Package-Exchange Robot-Routing Problem
説明
<jats:p> We study transportation problems where robots have to deliver packages and can transfer the packages among each other. Specifically, we study the package-exchange robot-routing problem (PERR), where each robot carries one package, any two robots in adjacent locations can exchange their packages, and each package needs to be delivered to a given destination. We prove that exchange operations make all PERR instances solvable. Yet, we also show that PERR is NP-hard to approximate within any factor less than 4/3 for makespan minimization and is NP-hard to solve for flowtime minimization, even when there are only two types of packages. Our proof techniques also generate new insights into other transportation problems, for example, into the hardness of approximating optimal solutions to the standard multi-agent path-finding problem (MAPF). Finally, we present optimal and suboptimal PERR solvers that are inspired by MAPF solvers, namely a flow-based ILP formulation and an adaptation of conflict-based search. Our empirical results demonstrate that these solvers scale well and that PERR instances often have smaller makespans and flowtimes than the corresponding MAPF instances. </jats:p>
収録刊行物
-
- Proceedings of the AAAI Conference on Artificial Intelligence
-
Proceedings of the AAAI Conference on Artificial Intelligence 30 (1), 2016-03-05
Association for the Advancement of Artificial Intelligence (AAAI)
