论文标题
具有任务变体的多机器人任务的分配
Allocation of Multi-Robot Tasks with Task Variants
论文作者
论文摘要
任务分配是一个很好的研究问题。在大多数先前的问题公式中，假定每个任务都与一组唯一的资源需求相关联。在多机器人任务分配问题的范围内，机器人联盟可以满足这些要求。在本文中，我们介绍了多机器人任务分配问题的更一般的公式，允许多个选项指定一组任务要求 - 满足任何一个选项都可以满足任务。我们将这个新问题称为任务变体的多机器人任务分配问题。首先，我们从理论上表明，幸运的是，这种扩展并不影响NP完整的复杂性类别。对于解决方案方法，我们将两种先前的贪婪方法用于任务分配问题，而没有任务变体来解决这个新问题并分析其有效性。特别是，我们在没有任务变体的情况下将新问题“弄平”了问题，修改了以前的方法来解决扁平问题，并证明了界限仍然存在。最后，我们彻底评估了这两种方法以及随机基线，以证明它们对新问题的功效。
Task allocation has been a well studied problem. In most prior problem formulations, it is assumed that each task is associated with a unique set of resource requirements. In the scope of multi-robot task allocation problem, these requirements can be satisfied by a coalition of robots. In this paper, we introduce a more general formulation of multi-robot task allocation problem that allows more than one option for specifying the set of task requirements--satisfying any one of the options will satisfy the task. We referred to this new problem as the multi-robot task allocation problem with task variants. First, we theoretically show that this extension fortunately does not impact the complexity class, which is still NP-complete. For solution methods, we adapt two previous greedy methods for the task allocation problem without task variants to solve this new problem and analyze their effectiveness. In particular, we "flatten" the new problem to the problem without task variants, modify the previous methods to solve the flattened problem, and prove that the bounds still hold. Finally, we thoroughly evaluate these two methods along with a random baseline to demonstrate their efficacy for the new problem.
