Source
SoCS
DATE OF PUBLICATION
07/17/2022
Authors
Konstantin Yakovlev Anton Andreychuk David Zahradka Miroslav Kulich
Share

Lower and Upper Bounds for Multi-Agent Multi-Item Pickup and Delivery: When a Decoupled Approach is Good Enough (Extended Abstract)

Abstract

The Multi-agent Multi-item Pickup and Delivery problem (MAMPD) stands for a problem of fnding collision-free trajectories for a feet of mobile agents transporting a set of items from their initial positions to specifed locations. Each agent can carry multiple items up to a given capacity. We study the solution quality of the naive decoupled approach, which decouples the problem into task assignment (TA) and MultiAgent Pathfnding (MAPF). By computing the gap between the lower bound of the MAMPD cost, estimated using the TA cost, and the upper bound, given by the fnal MAMPD cost, we show that the decoupled approach is able to obtain nearoptimal solutions in a wide range of cases.

Join AIRI