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

Authors

  • 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

DOI:

https://doi.org/10.1609/aaai.v30i1.10409

Keywords:

path planning, multi-agent pathfinding, complexity of planning

Abstract

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.

Downloads

Published

2016-03-05

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). https://doi.org/10.1609/aaai.v30i1.10409

Issue

Section

Technical Papers: Planning and Scheduling