Multi-Robot Pickup and Delivery via Distributed Resource Allocation

In this paper, we consider a large-scale instance of the classical Pickup-and-Delivery Vehicle Routing Problem (PDVRP) that must be solved by a network of mobile cooperating robots. Robots must self-coordinate and self-allocate a set of pickup/delivery tasks while minimizing a given cost figure. This results in a large, challenging Mixed-Integer Linear Problem that must be cooperatively solved without a central coordinator. We propose a distributed algorithm based on a primal decomposition approach that provides a feasible solution to the problem in finite time. An interesting feature of the proposed scheme is that each robot computes only its portion of solution, thereby preserving privacy of sensible information. The algorithm also exhibits attractive scalability properties that guarantee solvability of the problem even in large networks. To the best of our knowledge, this is the first attempt to provide a scalable distributed solution to the problem. The algorithm is first tested through Gazebo simulations on a ROS 2 platform, highlighting the effectiveness of the proposed solution. Finally, experiments on a real testbed with a team of ground and aerial robots are provided.

Automated summary

This paper discusses a large-scale instance of the Pickup-and-Delivery Vehicle Routing Problem (PDVRP) solved by a network of mobile cooperating robots. A distributed algorithm based on primal decomposition is proposed, which ensures privacy of sensitive information and exhibits good scalability. The effectiveness of the algorithm is demonstrated through Gazebo simulations and experiments on a real testbed with ground and aerial robots.