Multi-Agent Path Finding with Payload Transfers and the Package-Exchange Robot-Routing Problem


  • Hang Ma University of Southern California
  • Craig Tovey Georgia Institute of Technology
  • Guni Sharon Ben-Gurion University of the Negev
  • T. K. Kumar University of Southern California
  • Sven Koenig University of Southern California



path planning, multi-agent pathfinding, complexity of planning


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.




How to Cite

Ma, H., Tovey, C., Sharon, G., Kumar, T. K., & Koenig, S. (2016). Multi-Agent Path Finding with Payload Transfers and the Package-Exchange Robot-Routing Problem. Proceedings of the AAAI Conference on Artificial Intelligence, 30(1).



Technical Papers: Planning and Scheduling