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

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.

Automated summary

The article presents a branch-and-price algorithm for self-assignment of tasks in a network of agents, where each agent locally solves small problems and communicates with neighbors to converge to the optimal solution. By implementing the proposed algorithm in a robot operating system testbed, the team of heterogeneous robots successfully solved the task assignment problem.