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.
Generalized Assignment for Multirobot Systems via Distributed Branch-and-Price
2022-01-01
Article (Journal)
Electronic Resource
English
DDC: | 629 |
Distributed Motion Coordination for Multirobot Systems Under LTL Specifications
BASE | 2022
|Distributed Cooperative Outdoor Multirobot Localization and Mapping
British Library Online Contents | 2004
|Distributed Multirobot Control for Non-cooperative Herding
Springer Verlag | 2024
|Spatially targeted communication in decentralized multirobot systems
British Library Online Contents | 2015
|