Adapting the sampling distribution in PRM planners based on an approximated medial axis
Adapting the sampling distribution in PRM planners based on an approximated medial axis
复制标题
基于近似中轴调整 PRM 规划器中的采样分布
DOI：
10.1109/robot.2004.1302411
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
O. Brock
中科院分区：
文献类型：
--
作者：
Yuandong Yang;O. Brock
概率 roadmap规划器已被证明在解决复杂路径规划问题方面是有效的。这些规划器对配置空间进行采样以计算其自由空间连通性的表示。这种方法的主要困难之一是规划通过狭窄配置空间通道的路径，因为样本只有很小的概率被放置在狭窄通道内。为了解决这个问题，人们设计了一些方法，依靠工作空间的中轴来使配置空间中的采样产生偏差，从而增加在狭窄通道内生成样本的概率。本文介绍了一种计算中轴近似值的新算法，该算法比精确的或离散化的中轴能更高效地计算。我们证明，与真实中轴相比，这种近似同样适用于使概率roadmap规划器中的采样产生偏差。此外，我们提出了一种基于近似中轴的新采样策略。这种策略导致在狭窄通道内有高采样密度，而在开阔空间内稀疏采样。实验证明了中轴近似的有效性及其在基于所提出采样方案的运动规划中的应用。
Probabilistic roadmap planners have proven to be effective in solving complex path planning problems. These planners sample the configuration space to compute a representation of its free space connectivity. One of the major difficulties for this approach is the planning of a path through narrow configuration space passages, since samples are placed inside narrow passages only with small probability. To address this problem, approaches have been devised that rely on the medial axis of the workspace to bias sampling in configuration space such that the probability of generating samples inside narrow passages is increased. This paper introduces a novel algorithm for computing an approximation to the medial axis, which can be computed more efficiently than the exact or discretized medial axis. We demonstrate that, compared to the true medial axis, this approximation is equally well suited to bias the sampling in probabilistic roadmap planners. Furthermore, we present a novel sampling strategy based on the approximated medial axis. This strategy results in high sampling density in narrow passages, while sampling open spaces sparsely. Experiments demonstrate the effectiveness of the medial axis approximation and its application to motion planning based on the proposed sampling scheme.