论文标题
多分辨率A*
Multi-Resolution A*
论文作者
论文摘要
基于启发式搜索的计划技术通常用于离散空间的运动计划。这些算法的性能受到离散搜索空间的分辨率的严重影响。通常，为给定域选择固定分辨率。尽管更精细的分辨率可以更好地可操作性，但它大大增加了状态空间的规模，因此需要更多的搜索工作。相反，更粗的分辨率给出了快速的探索行为，但妥协了可操作性和搜索的完整性。为了有效利用高分辨率离散化的优势，我们提出了多分辨率A*（MRA*）算法，该算法运行了多个加权-A*（WA*）搜索具有不同分辨率水平的搜索，并结合了所有这些级别的强度。除这些搜索外，MRA*使用一个锚搜索来控制这些搜索的扩展。我们表明，相对于锚分辨率搜索空间和分辨率完成，MRA*是界定的。我们对几个运动计划域进行了实验，包括2D，3D网格计划和7 DOF操纵计划，并将我们的方法与几种基于搜索和采样的基线进行了比较。
Heuristic search-based planning techniques are commonly used for motion planning on discretized spaces. The performance of these algorithms is heavily affected by the resolution at which the search space is discretized. Typically a fixed resolution is chosen for a given domain. While a finer resolution allows for better maneuverability, it significantly increases the size of the state space, and hence demands more search efforts. On the contrary, a coarser resolution gives a fast exploratory behavior but compromises on maneuverability and the completeness of the search. To effectively leverage the advantages of both high and low resolution discretizations, we propose Multi-Resolution A* (MRA*) algorithm, that runs multiple weighted-A*(WA*) searches having different resolution levels simultaneously and combines the strengths of all of them. In addition to these searches, MRA* uses one anchor search to control expansions from these searches. We show that MRA* is bounded suboptimal with respect to the anchor resolution search space and resolution complete. We performed experiments on several motion planning domains including 2D, 3D grid planning and 7 DOF manipulation planning and compared our approach with several search-based and sampling-based baselines.
