Multi-agent Pickup and Delivery (MAPD) is a challenging industrial problem where a team of robots is tasked with transporting a set of tasks, each from an initial location and each to a specified target location. Appearing in the context of automated warehouse logistics and automated mail sortation, MAPD requires first deciding which robot is assigned what task (i.e., Task Assignment or TA) followed by a subsequent coordination problem where each robot must be assigned collision-free paths so as to successfully complete its assignment (i.e., Multi-Agent Path Finding or MAPF). Leading methods in this area solve MAPD sequentially: first assigning tasks, then assigning paths. In this work we propose a new coupled method where task assignment choices are informed by actual delivery costs instead of by lower-bound estimates. The main ingredients of our approach are a marginal-cost assignment heuristic and a meta-heuristic improvement strategy based on Large Neighbourhood Search. As a further contribution, we also consider a variant of the MAPD problem where each robot can carry multiple tasks instead of just one. Numerical simulations show that our approach yields efficient and timely solutions and we report significant improvement compared with other recent methods from the literature.


翻译:多试剂装配和交付(MAPD)是一个具有挑战性的工业问题,即由一组机器人负责将一组任务从最初的地点和每个地点运送到指定的目标地点。在自动仓储物流和自动邮件分类的背景下,MAPD要求首先决定给哪些机器人分配什么任务(即任务任务任务任务或TA),然后是随后的协调问题,即每个机器人必须指定无碰撞路径,以便顺利完成分配任务(即多代理人路径发现或MAPF)。该领域的主要方法依次解决MAPD:首先分配任务,然后分配路径。在这项工作中,我们提出了一个新的配套方法,根据实际交付费用而不是较低范围的估计数来选择任务任务任务任务选择。我们的方法的主要内容是边际成本任务任务任务任务任务和基于大型邻里搜索的超重力战略。作为进一步的贡献,我们还考虑了MAPD问题的一个变式,即每个机器人可以承担多项任务,而不是仅仅一个任务。数字模拟显示我们的方法产生了高效和及时的解决办法,我们报告与其他方法相比,我们从最近的文献中作了重大改进。

0
下载
关闭预览

相关内容

Automator是苹果公司为他们的Mac OS X系统开发的一款软件。 只要通过点击拖拽鼠标等操作就可以将一系列动作组合成一个工作流,从而帮助你自动的(可重复的)完成一些复杂的工作。Automator还能横跨很多不同种类的程序,包括:查找器、Safari网络浏览器、iCal、地址簿或者其他的一些程序。它还能和一些第三方的程序一起工作,如微软的Office、Adobe公司的Photoshop或者Pixelmator等。
【Manning新书】现代Java实战,592页pdf
专知会员服务
99+阅读 · 2020年5月22日
100+篇《自监督学习(Self-Supervised Learning)》论文最新合集
专知会员服务
164+阅读 · 2020年3月18日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
151+阅读 · 2019年10月12日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
深度自进化聚类:Deep Self-Evolution Clustering
我爱读PAMI
15+阅读 · 2019年4月13日
【TED】生命中的每一年的智慧
英语演讲视频每日一推
9+阅读 · 2019年1月29日
【TED】什么让我们生病
英语演讲视频每日一推
7+阅读 · 2019年1月23日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
最佳实践:深度学习用于自然语言处理(三)
待字闺中
3+阅读 · 2017年8月20日
【推荐】SLAM相关资源大列表
机器学习研究会
10+阅读 · 2017年8月18日
强化学习族谱
CreateAMind
26+阅读 · 2017年8月2日
Arxiv
4+阅读 · 2021年4月13日
VIP会员
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
深度自进化聚类:Deep Self-Evolution Clustering
我爱读PAMI
15+阅读 · 2019年4月13日
【TED】生命中的每一年的智慧
英语演讲视频每日一推
9+阅读 · 2019年1月29日
【TED】什么让我们生病
英语演讲视频每日一推
7+阅读 · 2019年1月23日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
最佳实践:深度学习用于自然语言处理(三)
待字闺中
3+阅读 · 2017年8月20日
【推荐】SLAM相关资源大列表
机器学习研究会
10+阅读 · 2017年8月18日
强化学习族谱
CreateAMind
26+阅读 · 2017年8月2日
Top
微信扫码咨询专知VIP会员