This paper studies a novel planning problem for multiple agents moving on graphs that we call offline time-independent multi-agent path planning (OTIMAPP). The motivation is to overcome time uncertainties in multi-agent scenarios where we cannot expect agents to act perfectly following timed plans, e.g., executions with mobile robots. For this purpose, OTIMAPP abandons all timing assumptions; it is offline planning that assumes event-driven executions without or less run-time effort. The problem is finding plans to be terminated correctly in any action orders of agents, i.e., guaranteeing that all agents eventually reach their destinations. We address a bunch of questions for this problem: required conditions for feasible solutions, computational complexity, comparison with well-known other multi-agent problems, construction of solvers, effective relaxation of a solution concept, and how to implement the plans by actual robots. Throughout the paper, we establish the foundation of OTIMAPP and demonstrate its utility. A video is available at https://kei18.github.io/otimapp.


翻译:本文研究在图表上移动的多个代理物的新规划问题,我们称之为脱线时间独立多试剂路径规划(OTIMAPP)。目的是克服多试剂情景中的时间不确定性,我们无法期望代理物按照计时计划完美行事,例如使用移动机器人处决。为此,OTIMAP放弃所有时间假设;这是假设不做或少做运行时间执行事件处决的离线计划。问题在于在代理物的任何行动命令中找到正确终止计划,即保证所有代理物最终到达目的地。我们讨论了这一问题的众多问题:可行解决办法的必要条件、计算复杂程度、与其他众所周知的多试剂问题的比较、构建解答器、有效放宽解决方案的概念,以及实际机器人如何执行计划。我们在整个文件中建立了OTIMAP的基础并展示其效用。一个视频可在 https://kei18.github.io/otimapp上查阅。

0
下载
关闭预览

相关内容

专知会员服务
25+阅读 · 2021年4月2日
知识图谱推理,50页ppt,Salesforce首席科学家Richard Socher
专知会员服务
105+阅读 · 2020年6月10日
【Manning新书】现代Java实战,592页pdf
专知会员服务
99+阅读 · 2020年5月22日
深度强化学习策略梯度教程,53页ppt
专知会员服务
178+阅读 · 2020年2月1日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
量化金融强化学习论文集合
专知
13+阅读 · 2019年12月18日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
19篇ICML2019论文摘录选读!
专知
28+阅读 · 2019年4月28日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
RL 真经
CreateAMind
5+阅读 · 2018年12月28日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
强化学习族谱
CreateAMind
26+阅读 · 2017年8月2日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Arxiv
0+阅读 · 2021年7月7日
Arxiv
0+阅读 · 2021年7月3日
Arxiv
0+阅读 · 2021年7月1日
Arxiv
3+阅读 · 2018年1月31日
VIP会员
相关VIP内容
专知会员服务
25+阅读 · 2021年4月2日
知识图谱推理,50页ppt,Salesforce首席科学家Richard Socher
专知会员服务
105+阅读 · 2020年6月10日
【Manning新书】现代Java实战,592页pdf
专知会员服务
99+阅读 · 2020年5月22日
深度强化学习策略梯度教程,53页ppt
专知会员服务
178+阅读 · 2020年2月1日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
相关资讯
量化金融强化学习论文集合
专知
13+阅读 · 2019年12月18日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
19篇ICML2019论文摘录选读!
专知
28+阅读 · 2019年4月28日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
RL 真经
CreateAMind
5+阅读 · 2018年12月28日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
强化学习族谱
CreateAMind
26+阅读 · 2017年8月2日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Top
微信扫码咨询专知VIP会员