In this article, we consider a large-scale instance of the classical pickup-and-delivery vehicle routing problem 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 own block 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.


    Access

    Download


    Export, share and cite



    Title :

    Multi-Robot Pickup and Delivery via Distributed Resource Allocation



    Publication date :

    2022-01-01



    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English



    Classification :

    DDC:    629 / 000



    ROBOT PICKUP OR DELIVERY SYSTEM AND PICKUP OR DELIVERY ROBOT

    SONG WEI / WATARI KATSUYOSHI | European Patent Office | 2024

    Free access

    Multi-Depot Pickup and Delivery Problem with Resource Sharing

    Yong Wang / Lingyu Ran / Xiangyang Guan et al. | DOAJ | 2021

    Free access

    Dynamic Task Allocation Using Distributed Resource Arbitration for Multi-robot Coordination

    Judkins, T. / Endo, Y. / Bachrach, B. et al. | British Library Conference Proceedings | 2010


    PICKUP ROBOT

    MOON SUNG JIN | European Patent Office | 2023

    Free access

    ROBOT PICKUP METHOD

    SIBLEY GABRIEL T | European Patent Office | 2018

    Free access