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


  • David Zahradka Czech Technical University in Prague Czech Institute of Informatics, Robotics and Cybernetics
  • Anton Andreychuk AIRI
  • Miroslav Kulich Czech Institute of Informatics, Robotics and Cybernetics
  • Konstantin Yakovlev Federal Research Center "Computer Science and Control" of Russian Academy of Sciencies AIRI




Analysis Of Search Algorithms, Search In Robotics, Real-life Applications


The Multi-agent Multi-item Pickup and Delivery problem (MAMPD) stands for a problem of finding collision-free trajectories for a fleet of mobile agents transporting a set of items from their initial positions to specified 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 Multi-Agent Pathfinding (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 final MAMPD cost, we show that the decoupled approach is able to obtain near-optimal solutions in a wide range of cases.