In this article, we consider a network of agents that has to self-assign a set of tasks while respecting resource constraints. One possible formulation is the generalized assignment problem, where the goal is to find a maximum payoff while satisfying capability constraints. We propose a purely distributed branch-and-price algorithm to solve this problem in a cooperative fashion. Inspired by classical (centralized) branch-and-price schemes, in the proposed algorithm, each agent locally solves small linear programs, generates columns by solving simple knapsack problems, and communicates to its neighbors a fixed number of basic columns. We prove finite-time convergence of the algorithm to an optimal solution of the problem. Then, we apply the proposed scheme to a generalized assignment scenario, in which a team of robots has to serve a set of tasks. We implement the proposed algorithm in a Robot Operating System testbed and provide experiments for a team of heterogeneous robots solving the assignment problem.


    Access

    Download


    Export, share and cite



    Title :

    Generalized Assignment for Multirobot Systems via Distributed Branch-and-Price



    Publication date :

    2022-01-01



    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English



    Classification :

    DDC:    629



    Distributed Motion Coordination for Multirobot Systems Under LTL Specifications

    Yu, Pian / Dimarogonas, Dimos V. | BASE | 2022

    Free access

    Distributed Cooperative Outdoor Multirobot Localization and Mapping

    Madhavan, R. / Fregene, K. / Parker, L. E. | British Library Online Contents | 2004


    Distributed Multirobot Control for Non-cooperative Herding

    Mohanty, Nishant / Grover, Jaskaran / Liu, Changliu et al. | Springer Verlag | 2024


    Congestion-aware policy synthesis for multirobot systems

    Street, C / Puetz, S / Muehlig, M et al. | BASE | 2022

    Free access

    Spatially targeted communication in decentralized multirobot systems

    Mathews, N. | British Library Online Contents | 2015