Hierarchical rejection sampling for informed kinodynamic planning in high-dimensional spaces
Hierarchical rejection sampling for informed kinodynamic planning in high-dimensional spaces
复制标题
用于高维空间中知情运动动力学规划的分层拒绝采样
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
H. Christensen
中科院分区：
文献类型：
--
作者：
Tobias Kunz;A. Thomaz;H. Christensen
针对高维微分约束问题，提出了分层拒绝抽样（HRS）方法，以提高渐近最优抽样规划器的效率。修剪节点和拒绝无法改善当前最佳解决方案的样本已被证明可以提高某些问题的性能。我们表明，在高维域中，这种改进可能非常大，以至于拒绝样本成为算法的瓶颈，因为几乎所有样本都被拒绝。这与冲突检查始终是基于采样的规划器的瓶颈的一般智慧相矛盾。只有状态空间的已知子集中的样本才可能改善当前解决方案。对于没有微分约束的系统，信息子集形成一个椭球，可以直接参数化和采样。对于具有微分约束的系统，信息子集更加复杂，并且不存在这样的直接采样方法。HRS提高了在已知子集内查找样本的效率，而无需显式地对其进行参数化。因此，它也可以适用于系统的微分约束，其中的转向方法是可用的。在我们的实验中，我们证明了RRT* 计划的效率提高了两个数量级。
We present hierarchical rejection sampling (HRS) to improve the efficiency of asymptotically optimal sampling-based planners for high-dimensional problems with differential constraints. Pruning nodes and rejecting samples that cannot improve the currently best solution have been shown to improve performance for certain problems. We show that in high-dimensional domains this improvement can be so large that rejecting samples becomes the bottleneck of the algorithm because almost all samples are rejected. This contradicts general wisdom that collision checking is always the bottleneck of sampling-based planners. Only samples in the informed subset of the state space can potentially improve the current solution. For systems without differential constraints the informed subset forms an ellipsoid, which can be parameterized and sampled directly. For systems with differential constraints the informed subset is more complicated and no such direct sampling methods exist. HRS improves the efficiency of finding samples within the informed subset without parameterizing it explicitly. Thus, it can also be applied to systems with differential constraints for which a steering method is available. In our experiments we demonstrate efficiency improvements of an RRT* planner of up to two orders of magnitude.