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* 还可以在最优化地利用最佳的解析的解算方法, 。