Multi-robot systems are uniquely well-suited to performing complex tasks such as patrolling and tracking, information gathering, and pick-up and delivery problems, offering significantly higher performance than single-robot systems. A fundamental building block in most multi-robot systems is task allocation: assigning robots to tasks (e.g., patrolling an area, or servicing a transportation request) as they appear based on the robots' states to maximize reward. In many practical situations, the allocation must account for heterogeneous capabilities (e.g., availability of appropriate sensors or actuators) to ensure the feasibility of execution, and to promote a higher reward, over a long time horizon. To this end, we present the FlowDec algorithm for efficient heterogeneous task-allocation achieving an approximation factor of at least 1/2 of the optimal reward. Our approach decomposes the heterogeneous problem into several homogeneous subproblems that can be solved efficiently using min-cost flow. Through simulation experiments, we show that our algorithm is faster by several orders of magnitude than a MILP approach.
翻译:多机器人系统与众不同,适合于执行巡逻和跟踪、信息收集、采集和交付等复杂任务,其性能比单一机器人系统高得多。大多数多机器人系统的一个基本组成部分是任务分配:根据机器人的状态,将机器人分配任务(例如对某一地区进行巡逻,或为运输请求提供服务),以获得最大限度的奖励。在许多实际情况下,分配必须顾及各种能力(例如提供适当的传感器或动因器),以确保执行的可行性,并在很长的时期内促进更高的奖励。为此,我们介绍了高效混合任务配置的流程算法,以达到至少1/2的最佳奖励的近似系数。我们的方法将混杂问题分解成若干单一的子问题,而这些问题可以通过低成本流有效解决。通过模拟实验,我们显示我们的算法比MILP方法要快几个数量级。