2020/04/24 by Andrea Testa, Giuseppe Notarstefano, Testa, Andrea +1
Computer Science · Engineering · #Distributed Control Multi-Agent Systems #FOS: Mathematics #Modular Robots and Swarm Intelligence #Optimization and Control (math.OC) #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2004.11857
openalex publication_date 2020/04/24 · openalex created_date 2022/10/03 · openalex updated_date 2026/07/28
In this paper, we consider a network of agents that has to self-assign a set\nof tasks while respecting resource constraints. One possible formulation is the\nGeneralized Assignment Problem, where the goal is to find a maximum payoff\nwhile satisfying capability constraints. We propose a purely distributed\nbranch-and-price algorithm to solve this problem in a cooperative fashion.\nInspired by classical (centralized) branch-and-price schemes, in the proposed\nalgorithm each agent locally solves small linear programs, generates columns by\nsolving simple knapsack problems, and communicates to its neighbors a fixed\nnumber of basic columns. We prove finite-time convergence of the algorithm to\nan optimal solution of the problem. Then, we apply the proposed scheme to a\ngeneralized assignment scenario in which a team of robots has to serve a set of\ntasks. We implement the proposed algorithm in a ROS testbed and provide\nexperiments for a team of heterogeneous robots solving the assignment problem.\n