李华忠，但唐仁，唐强平

（深圳信息职业技术学院软件工程系,广东 深圳 518172 ）

自适应双向快速密集树避碰运动规划算法

李华忠，但唐仁，唐强平

（深圳信息职业技术学院软件工程系,广东 深圳 518172 ）

针对采样运动规划算法效率低，尤其在处理高维空间和复杂障碍环境等问题时，严重依赖于所选采样参数和碰撞检测距离等，提出了一种自适应双向快速密集树(ABiRDT)避碰运动规划方法。首先，深入研究了ABiRDT 算法的基础理论和实现方法，可适应调整碰撞检测距离参数和随机采样扩展步长；其次，重点研究了本算法所采用的C-空间加权均匀采样、最近邻位形查找和基于混合包围盒的并行离散碰撞检测等关键自适应策略；最后，通过三维可视化计算机仿真验证了本文提出算法的有效性。

运动规划；快速密集树；自适应算法；基于采样技术；离散碰撞检测；位形空间

自Lozano-Perez提出位形空间(Configuration Space，C-空间)概念，从而可将各类运动规划问题转化成在C-空间中寻找点的无碰路径问题以来,基于采样的规划技术已被广泛应用于高自由度智能机器人避碰和操控等领域[1-4]，成为国内外普遍关注的研究热点。该方法的显著优点是基于随机采样只需近似构造自由位形空间 ，从而避免了采用骨架网格和栅格分解[5]等方法需完整和精确构造全部有效C-空间模型，以寻找精确解析解所带来的PSPACE难题，规避了高自由度所引起的存储空间和计算量呈指数爆炸增长的NP问题[6]。最典型的两类基于采样的运动规划方法为：快速随机搜索树法（Rapidly exploring Random Tree：RRT）[7-8]和概率地图法（Probabilistic Roadmap：PRM）[9]。……