摘 要：针对当组态空间内存在大量的窄道时，快速搜索随机树算法（RRT）难以取得连通路径的问题，提出了一种改进的RRTConnect算法。该算法利用改进的桥梁检测（Bridge Test）算法来识别和采样窄道，使得路径规划在窄道内能轻易取得连通性；同时将RRTConnect算法与任意时间算法相结合，显著地减少了RRTConnect算法的移动代价。每个算法分别运行100次，与RRTConnect算法相比，改进后的算法成功次数由34提高到93，规划时间由9.3s减少到4.2s。双足机器人的仿真实验结果表明，该算法能在窄道内取得优化路径，同时可以有效地提高路径规划的效率。
关键词：快速搜索随机树；桥梁检测；任意时间算法；路径规划；窄道；双足机器人
中图分类号： TP242
文献标志码：A
0 引言
在过去的十年里，路径规划[1-3]在机器人学、制造业、计算机动画等领域得到了广泛的研究。由于传统的确定性路径规划算法在高维组态空间里性能会急剧下降，使得以随机采样为基础的算法不断得到应用和改进。快速搜索随机树（Rapidlyexploring Random Tree，RRT）采用随机采样的规划方法，不需要预处理且搜索速度快（其在高维空间中速度优势尤为明显），因此得到了很多研究者的青睐。早期主要采用单棵RRT树进行搜索，为了进一步提高搜索速度，出现了许多改进的RRT算法，如：Kuffer等提出的偏向RRT、双向RRT和RRTConnect[4-5]，Jim Brucet提出的ERRT（Extend RRT）算法[6]，Dave Ferguson提出的DRRT（Dynamic RRT）算法[7]，Zucker Matt提出的MPRRT（Multipartite RRT）算法[8]等。改进后的算法在路径规划方面的性能得到了显著的提升，其中Kuffner等提出的RRTConnect算法性能尤为突出。该方法基于两个基本思想：1）连接采样点的延伸函数试图移动更长的距离；2）RRT从初始组态和目标组态同时延伸。但当组态空间内存在大量窄道，且路径规划必须通过窄道时，其性能会显著下降。由于RRTConnect算法采用的是均匀的随机采样策略，其显著缺点是在识别到狭窄的通道前浪费了大量的计算时间在开阔的地带，且相对于整个组态空间而言窄道的通道面积很小，即使是两个很近的节点但由于属于不同的部分，RRTConnect算法也很难将它们连接取得连通性。
为解决上述问题，提出了一种改进的RRTConnect算法。将RRTConnect算法与桥梁检测（Bridge Test）[9]算法相结合。Bridge Test算法易于推广到高维空间，不需要复杂的几何处理就能很容易地提高窄道内的采样密度，将其与RRTConnect算法结合可以解决RRTConnect算法在窄道内采样难的问题。同时任意时间（anytime）算法[10-11]是一种解的质量随着时间的增加而逐步提高的算法，在规定的时间内可不断减少RRTConnect的移动代价。实验的结果表明算法的有效性。
1 双足机器人模型与步行
6 结语
本文提出了一种改进的RRTConnect算法，将RRTConnect算法和桥梁检测算法结合起来，解决了RRTConnect算法在狭窄的通道内采样规划路径难的问题；并用任意时间算法进一步改进RRTConnect算法，减少了路径规划的移动代价。但该算法还有一些问题未能得到很好的解决，如桥梁检测算法采样窄道时会产生一些不必要的探索树，这样就降低了算法的性能。这些问题将是下个阶段努力的方向。
参考文献：
[1]夏泽洋，陈恳，熊璟，等.仿人机器人运动规划研究进展[J].高技术通讯，2007，17（10）：1092-1099.
[2]郑慧杰，刘弘，郑向伟.基于改进群搜索优化算法的群体路径规划方法[J].计算机应用，2012，32（8）：2223-2226.
[3]张彤，肖南峰.仿人机器人实时路径规划方法研究[J].计算机工程与应用，2009，45（27）：4-6.
[4]LAVALLE S M， KUFFNER J J， Jr. Rapidlyexploring random trees： progress and prospects [C]// Proceedings of the 4th International Workshop on the Algorithmic Foundations of Robotics： Algorithmic and Computational Robotics： New Directions. Natick， MA， USA： A. K. Peters， 2000： 293-308.
[5]LAVALLE S M， KUFFNER J. RRTConnect： an efficient approach to singlequery path planning [C]// Proceedings of the 2000 IEEE International Conference on Robotics & Automation. Piscataway： IEEE，2000，4：995-1001.
[6]BRUCE J， VELOSO M.Realtime randomized path planning for robot navigation [C]// Proceedings of the 2002 IEEE/RSJ International Conference on Intelligent Robots and Systems. Piscataway： IEEE， 2002：2383-2388. [7]FEGUSON D.Replanning with RRTs [C]// Proceeding of the 2006 IEEE International Conference on Robotics & Automation. Piscataway： IEEE，2006，5：1243-1248.
[8]ZUCKER M，KUFFNER J J， Jr.Multipartite RRTs for rapid replanning in dynamic environments [C]// Proceeding of the 2007 IEEE International Conference on Robotics & Automation. Piscataway： IEEE，2007，4：1603-1609.
[9]KALA R， WARWICK K. Multivehicle planning using RRTConnect[J].Journal of Behavioral Robotics，2011，2（3）：134-144.
[9]ZHEN S， DVAID H， JIANG T T， et al. Narrow passage sampling for probabilistic roadmap planning[J].IEEE Transactions on Robotics，2005，21（6）：1105-1115.
[10]JEON J H， KARAMAN S，FRAZZOLI E. Anytime computation of timeoptimal offroad vehicle maneuvers using the RRT* [C]// Proceedings of the 50th IEEE Conference on Decision and Control and European Control Conference. Piscataway： IEEE，2011： 3276-3282.
[11]FERGUSON D， STENTZ A. Anytime RRTs [C]// Proceedings of the 2006 IEEE/RSJ International Conference on Intelligent Robots and Systems. Piscataway： IEEE， 2006：5369-5375.
[12]夏泽洋，陈恳.仿人机器人足迹规划建模及算法实现[J].机器人，2008，30（3）：231-237.
[13]（日）梶田秀司.仿人机器人[M].管贻生，译.北京：清华大学出版社，2007.
[14]于国晨，刘永信，李晓红.基于三维线性倒立摆的仿人机器人步态规划[J].计算机应用，2012，32（9）：2643-2647.
[15]李龙澍，王唯翔，王凡.基于三维线性倒立摆的双足机器人步态规划[J].计算机技术与发展，2011，21（6）：66-69.