Lower and Upper Bounds for Multi-Agent Multi-Item Pickup and Delivery: When a Decoupled Approach is Good Enough (Extended 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.