Heuristic search-based motion planning algorithms typically discretise the search space in order to solve the shortest path problem. Their performance is closely related to this discretisation. A fine discretisation allows for better approximations of the continuous search space, but makes the search for a solution more computationally costly. A coarser resolution might allow the algorithms to find solutions quickly at the expense of quality. For large state spaces, it can be beneficial to search for solutions across multiple resolutions even though defining the discretisations is challenging. The recently proposed algorithm Multi-Resolution A* (MRA*) searches over multiple resolutions. It traverses large areas of obstacle-free space and escapes local minima at a coarse resolution. It can also navigate so-called narrow passageways at a finer resolution. In this work, we develop AMRA*, an anytime version of MRA*. AMRA* tries to find a solution quickly using the coarse resolution as much as possible. It then refines the solution by relying on the fine resolution to discover better paths that may not have been available at the coarse resolution. In addition to being anytime, AMRA* can also leverage information sharing between multiple heuristics. We prove that AMRA* is complete and optimal (in-the-limit of time) with respect to the finest resolution. We show its performance on 2D grid navigation and 4D kinodynamic planning problems.


翻译:偏差的搜索动态规划算法通常使搜索空间离散,以解决最短的路程问题。它们的性能与这种离散问题密切相关。 细细的离散使得能够更接近连续搜索空间, 但也使得寻找解决办法的成本更高。 粗糙的解析方法可能使算法能够以质量为代价迅速找到解决办法。 对于大型国家空间, 即便界定离散问题, 也有可能在多个分辨率之间寻找解决办法。 最近提出的多分辨率A* (MRA*) 的算法对多个分辨率的搜索颇具挑战性。 它横跨了无障碍空间的大片区域,并且以粗略的分辨率逃离了当地的迷你马。 它还可以以更细的分辨率浏览所谓的狭窄的通道。 在这项工作中,我们开发了AMRA*,这是一个随时可能以质量为代价的版本的MRA* 。 AMRA* 试图尽可能快速地利用粗糙的解析方法找到解决办法。 然后,它改进了解决办法, 依靠精细的解析的解析分辨率来找到可能无法找到的更好路径。 此外, AMD* 还可以在最优化地利用最佳的解析的解算方法, 。

0
下载
关闭预览

相关内容

专知会员服务
31+阅读 · 2021年6月12日
如何构建你的推荐系统?这份21页ppt教程为你讲解
专知会员服务
64+阅读 · 2021年2月12日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
强化学习三篇论文 避免遗忘等
CreateAMind
19+阅读 · 2019年5月24日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
学术会议 | 知识图谱顶会 ISWC 征稿:Poster/Demo
开放知识图谱
5+阅读 · 2019年4月16日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【推荐】深度学习目标检测概览
机器学习研究会
10+阅读 · 2017年9月1日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
6+阅读 · 2019年11月14日
Pluralistic Image Completion
Arxiv
8+阅读 · 2019年3月11日
VIP会员
相关资讯
强化学习三篇论文 避免遗忘等
CreateAMind
19+阅读 · 2019年5月24日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
学术会议 | 知识图谱顶会 ISWC 征稿:Poster/Demo
开放知识图谱
5+阅读 · 2019年4月16日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【推荐】深度学习目标检测概览
机器学习研究会
10+阅读 · 2017年9月1日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员