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.
Similar publications
You can ask us a question or suggest a joint project in the field of AI
partner@airi.net
For scientific cooperation and
partnership
partnership
pr@airi.net
For journalists and media