论文标题
多机器人系统通过分布式分支机构和价格的广义分配
Generalized Assignment for Multi-Robot Systems via Distributed Branch-And-Price
论文作者
论文摘要
在本文中，我们考虑了一个必须自我分配一组任务的代理网络，同时尊重资源约束。一种可能的公式是广义分配问题，目标是在满足能力约束的同时找到最大的回报。我们提出了一种纯粹分布的分支机构和价格算法，以合作的方式解决这个问题。受到经典（集中）分支和价格方案的启发，在提出的算法中，每个代理都在本地求解小型线性程序，通过解决简单的背包问题来生成列，并与邻居通信固定数量的基本列。我们证明了算法与问题最佳解决方案的有限时间收敛。然后，我们将提出的方案应用于广义分配方案，其中一组机器人必须执行一组任务。我们在ROS测试中实现了所提出的算法，并为解决分配问题的异质机器人团队提供了实验。
In this paper, 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 ROS testbed and provide experiments for a team of heterogeneous robots solving the assignment problem.
