We propose a novel algorithm to solve multi-robot motion planning (MRMP) rapidly, called Simultaneous Sampling-and-Search Planning (SSSP). Conventional MRMP studies mostly take the form of two-phase planning that constructs roadmaps and then finds inter-robot collision-free paths on those roadmaps. In contrast, SSSP simultaneously performs roadmap construction and collision-free pathfinding. This is realized by uniting techniques of single-robot sampling-based motion planning and search techniques of multi-agent pathfinding on discretized spaces. Doing so builds the small search space, leading to quick MRMP. SSSP ensures finding a solution eventually if exists. Our empirical evaluations in various scenarios demonstrate that SSSP significantly outperforms standard approaches to MRMP, i.e., solving more problem instances much faster. We also applied SSSP to planning for 32 ground robots in a dense situation.


翻译:我们提出了一种快速解决多机器人运动规划问题的新算法,称为“同时采样和搜索规划”(SSSP)。传统的多机器人运动规划主要采用两阶段规划的形式,即构建路线图,然后在这些路线图上查找机器人之间无冲突的路径。相比之下,SSSP同时进行路线图构建和无冲突路径规划。这是通过将单机器人采样式运动规划技术和离散空间上多智能体路径查找的搜索技术结合起来实现的。这样做可以建立较小的搜索空间,从而实现快速多机器人运动规划。SSSP确保最终找到解决方案,如果存在的话。我们在各种场景下进行了实证评估,证明SSSP显著优于标准的多机器人运动规划方法,即更快地解决更多的问题实例。我们还将SSSP应用于32个地面机器人在密集情况下的规划。

0
下载
关闭预览

相关内容

148页最新《深度强化学习》教程,148页ppt
专知会员服务
76+阅读 · 2023年4月29日
Meta最新WWW2022《联邦计算导论》教程,附77页ppt
专知会员服务
59+阅读 · 2022年5月5日
【ETH、Stanford】基于博弈论的运动规划,Tutorial ICRA '21
专知会员服务
55+阅读 · 2022年3月7日
机器学习组合优化
专知会员服务
108+阅读 · 2021年2月16日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
《元强化学习》最新,70页ppt
专知
2+阅读 · 2022年9月16日
17种深度强化学习算法用Pytorch实现
新智元
30+阅读 · 2019年9月16日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
LibRec 精选:基于LSTM的序列推荐实现(PyTorch)
LibRec智能推荐
50+阅读 · 2018年8月27日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
【推荐】深度学习目标检测全面综述
机器学习研究会
21+阅读 · 2017年9月13日
强化学习族谱
CreateAMind
26+阅读 · 2017年8月2日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
1+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Arxiv
0+阅读 · 2023年5月25日
Arxiv
0+阅读 · 2023年5月25日
Arxiv
0+阅读 · 2023年5月24日
Arxiv
0+阅读 · 2023年5月24日
VIP会员
相关VIP内容
相关资讯
《元强化学习》最新,70页ppt
专知
2+阅读 · 2022年9月16日
17种深度强化学习算法用Pytorch实现
新智元
30+阅读 · 2019年9月16日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
LibRec 精选:基于LSTM的序列推荐实现(PyTorch)
LibRec智能推荐
50+阅读 · 2018年8月27日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
【推荐】深度学习目标检测全面综述
机器学习研究会
21+阅读 · 2017年9月13日
强化学习族谱
CreateAMind
26+阅读 · 2017年8月2日
相关基金
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
1+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Top
微信扫码咨询专知VIP会员