Hit-and-Run for Sampling and Planning in Non-Convex Spaces
Hit-and-Run for Sampling and Planning in Non-Convex Spaces
复制标题
非凸空间中的“肇事逃逸”采样和规划
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Alan Malek
中科院分区：
文献类型：
--
作者：
Yasin Abbasi;P. Bartlett;Victor Gabillon;Alan Malek
我们针对非凸空间中的规划和采样问题提出了“撞了就跑”（Hit-and-Run）算法。对于采样，我们给出了在非凸空间中对“撞了就跑”算法的首次分析，并表明只要满足某些平滑性条件，它就能快速混合。特别是，我们的分析揭示了快速混合与从凸空间到非凸空间的保测平滑映射的存在之间的一种有趣联系。对于规划，我们展示了“撞了就跑”算法相较于诸如快速扩展随机树等最先进的规划方法的优势。
We propose the Hit-and-Run algorithm for planning and sampling problems in non- convex spaces. For sampling, we show the first analysis of the Hit-and-Run algorithm in non-convex spaces and show that it mixes fast as long as certain smoothness conditions are satisfied. In particular, our analysis reveals an intriguing connection between fast mixing and the existence of smooth measure-preserving mappings from a convex space to the non-convex space. For planning, we show advantages of Hit-and- Run compared to state-of-the-art planning methods such as Rapidly-Exploring Random Trees.