Quality Analysis of Multi-Agent Multi-Item Pickup and Delivery Solutions Using a Decoupled Approach

• Published in: IFAC-PapersOnLine 2022-01, Vol.55 (38), p.61-66
• Main Authors: Zahradka, David, Andreychuk, Anton, Kulich, Miroslav, Yakovlev, Konstantin
• Format: Article
• Language: English
• Subjects: Autonomous Mobile Robots; Delivery Robots; Multi Cooperative Robot Control; Path Planning; Trajectory; Transport
• ISSN: 2405-8963; 2405-8963
• DOI: 10.1016/j.ifacol.2023.01.134

In this article, we study the Multi-agent Multi-item Pickup and Delivery (MAMPD), which 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 the specified goal locations. Each agent can carry multiple items up to a given capacity at the same moment. This requires solving two orthogonal problems concurrently: assigning a sequence of items to pick for every agent and finding a set of collision-free trajectories under this assignment. We decouple the problem into two subproblems: the task assignment (TA) and Multi-Agent Pathfinding (MAPF), to determine the lower and upper bounds of the MAMPD. First, a lower bound is estimated by formulating and solving the TA as a Vehicle Routing Problem (VRP). The collisions, which are not considered during the TA, are consequently resolved using a MAPF solver on the VRP solution. The cost of the MAPF solution forms an upper bound of the MAMPD. We show that on a large class of setups, the gap between the lower and upper bounds is small. This signifies that the decoupled MAMPD solver obtained near-optimal solutions. However, we show that on certain setups, intentionally designed to be difficult, the decoupled solver is unable to find a solution with a small gap even when using a bounded suboptimal MAPF solver. By computing the gap, we can determine whether the solution obtained by the decoupled approach is near-optimal or whether it is beneficial to use a more advanced MAMPD solver.