Decentralized matroid optimization for topology constraints in multi-robot allocation problems
Decentralized matroid optimization for topology constraints in multi-robot allocation problems
复制标题
DOI：
10.1109/icra.2017.7989038
复制
发表时间：
2017-05
期刊：
影响因子：
--
通讯作者：
Ryan K. Williams;A. Gasparri;G. Ulivi
中科院分区：
文献类型：
--
作者：
Ryan K. Williams;A. Gasparri;G. Ulivi
本文运用拟阵的组合理论，证明了拓扑约束以及其他抽象约束是如何集成到任务分配中的。通过将问题建模为矩阵约束的交集，可以在任务分配空间中实现任意的组合关系。为了说明该框架的可表达性，我们建立了一个新的任务分配问题模型，该问题将抽象的每个机器人约束与通信生成树约束耦合在一起。由于我们的问题是一个矩阵交点，用简单的贪心算法可证明的最优性边界从理论上立即得到。接下来，我们提出了一种分散的算法，将拍卖方法应用于具有矩阵交叉点的任务分配。对城市环境中监控任务分配的模拟验证了我们的结果。最后，给出了蒙特卡罗结果，表明贪婪任务分配在实践中即使具有接近最优的解决方案也具有很高的竞争力。
In this paper, we demonstrate how topological constraints, as well as other abstract constraints, can be integrated into task allocation by applying the combinatorial theory of matroids. By modeling problems as an intersection of matroid constraints, arbitrary combinatorial relationships can be achieved in the task allocation space. To illustrate the expressiveness of the framework, we model a novel task allocation problem that couples abstract per-robot constraints with a communication spanning tree constraint. As our problem is cast as a matroid intersection, provable optimality bounds with simple greedy algorithms follows immediately from theory. Next, we present a decentralized algorithm that applies auction methods to task allocation with matroid intersections. Simulations of task allocation for surveillance in urban environments demonstrate our results. Finally, Monte Carlo results are provided that indicate greedy task allocations can be highly competitive even with near-optimal solutions in practice.