Task and Path Planning for Multi-Agent Pickup and Delivery

May 2019

Task and Path Planning for Multi-Agent Pickup and Delivery

Authors:

Minghua Liu, Hang Ma, Jiaoyang Li, and Sven Koenig

Abstract:

We study the offline Multi-Agent Pickup-and-Delivery (MAPD) problem, where a team of agents has to execute a batch of tasks with release times in a known environment. To execute a task, an agent has to move first from its current location to the pickup location of the task and then to the delivery location of the task. The MAPD problem is to assign tasks to agents and plan collision-free paths for them to execute their tasks. Online MAPD algorithms can be applied to the offline MAPD problem, but do not utilize all of the available information and may thus not be effective. Therefore, we present two novel offline MAPD algorithms that improve a state-of-the-art online MAPD algorithm with respect to task planning, path planning, and deadlock avoidance for the offline MAPD problem. Our MAPD algorithms first compute one task sequence for each agent by solving a special traveling salesman problem and then plan paths according to these task sequences. We also introduce an effective deadlock avoidance method, called "reserving dummy paths.'' Theoretically, our MAPD algorithms are complete for well-formed MAPD instances, a realistic subclass of all MAPD instances. Experimentally, they produce solutions of smaller makespans and scale better than the online MAPD algorithm in simulated warehouses with hundreds of robots and thousands of tasks.
@conference{Liu-2019-131432,
author = {Minghua Liu And Hang Ma And Jiaoyang Li And Sven Koenig},
title = {Task and Path Planning for Multi-Agent Pickup and Delivery},
booktitle = {Proceedings of 18th International Joint Conference on Autonomous Agents and MultiAgent Systems (AAMAS '19)},
year = {2019},
month = {May},
pages = {1152 - 1160},
}
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.