Multi-robot task allocation is one of the most fundamental classes of problems in robotics and is crucial for various real-world robotic applications such as search, rescue and area exploration. We consider the Single-Task robots and Multi-Robot tasks Instantaneous Assignment (ST-MR-IA) setting where each task requires at least a certain number of robots and each robot can work on at most one task and incurs an operational cost for each task. Our aim is to consider a natural computational problem of allocating robots to complete the maximum number of tasks subject to budget constraints. We consider budget constraints of three different kinds: (1) total budget, (2) task budget, and (3) robot budget. We provide a detailed complexity analysis including results on approximations as well as polynomial-time algorithms for the general setting and important restricted settings.


翻译:多机器人任务分配是机器人问题的最根本类别之一,对于搜索、救援和地区勘探等各种现实世界机器人应用至关重要。我们考虑单任务机器人和多机器人任务即时分配(ST-MR-IA)设置,其中每个任务至少需要一定数量的机器人,每个机器人最多可以完成一项任务并承担每项任务的运作费用。我们的目的是考虑分配机器人完成受预算限制的最多任务数量的自然计算问题。我们考虑三种不同的预算限制:(1)总预算,(2)任务预算,(3)机器人预算。我们提供了详细的复杂程度分析,包括近似结果以及一般环境和重要限制环境的多时算法。

0
下载
关闭预览

相关内容

自然计算(Natural Computing)是指在自然中观察到的计算过程,以及受自然启发而设计的人类计算。当我们从计算过程的角度分析复杂的自然现象时,我们对自然和计算本质的理解都得到了增强。灵感来自自然的人工设计计算的特点是隐喻性地使用自然系统下的概念、原理和机制。自然计算包括进化算法、神经网络、分子计算和量子计算。 官网地址:http://dblp.uni-trier.de/db/journals/nc/
专知会员服务
42+阅读 · 2020年12月18日
【2020新书】概率机器学习,附212页pdf与slides
专知会员服务
108+阅读 · 2020年11月12日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
已删除
将门创投
5+阅读 · 2018年11月15日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
1+阅读 · 2021年5月16日
VIP会员
相关资讯
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
已删除
将门创投
5+阅读 · 2018年11月15日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员