《多个机器人实时组建联盟编队》34页论文

军事和灾难响应应用中的机器人集体需要联盟组建算法将机器人划分为适当的任务小组。机器人集体的任务往往包含需要多种高级机器人行为或服务的任务，而联盟组建必须满足这些要求。此外，高度动态和非结构化的应用领域还要求联盟组建算法能在接近实时的时间内（即 < 5 分钟）为超大型集体（即数百个机器人）提供接近最优的解决方案（即 > 95% 的效用）。以前的联盟组建算法都无法满足这些要求。初步评估发现，传统的基于拍卖的算法运行时间太长，即使集中式模拟器包含了现实世界部署中不太可能出现的理想条件（即机器人之间的同步和完美的即时通信）。基于享乐博弈的 GRAPE 算法可以近乎实时地生成解决方案，但无法应用于多个服务集体。本手稿整合了 GRAPE 和服务模型，产生了 GRAPE-S 和 PairGRAPE-S。这些算法和两个拍卖基线分别通过使用多达 1000 个机器人的集中式模拟器和使用多达 500 个机器人的迄今为止最大的分布式联盟形成模拟评估进行了评估。评估结果表明，拍卖无法很好地转移到分布式集体中，导致运行时间过长和解决方案效用较低。GRAPE-S 满足了目标领域的联盟组建要求，能在接近实时的情况下生成接近最优的解决方案，而 Pair-GRAPE-S 则更能满足领域要求，能在接近实时的情况下生成最优的解决方案。GRAPE-S 和 Pair-GRAPE-S 是首批支持超大型分布式多服务集体近实时联盟组建的算法。