Abstract: When lots of narrow passages are contained in the configuration space, the algorithm of Rapidly-exploring Random Tree (RRT) can hardly get the path. In order to deal with the problem, an improved RRT-Connect algorithm was presented. An improved bridge test algorithm was employed to identify and sample narrow passages, so it could be easy to get the connectivity. Combining RRT-Connect with anytime algorithm, the cost of RRT-Connect could be reduced obviously. Each algorithm was run 100 times. Compared with RRT-Connect, the successes' number of the improved algorithm was increased from 34 to 93, and the path planning time was decreased from 9.3s to 4.2s. The biped robot simulation results demonstrate that the algorithm can get the optimal path inside the narrow passages; meanwhile, it improves the efficiency.

Key words: Rapidly-exploring Random Tree (RRT), bridge test, anytime algorithm, path planning, narrow passage, biped robot

摘要： 针对当组态空间内存在大量的窄道时，快速搜索随机树算法(RRT)难以取得连通路径的问题，提出了一种改进的RRT-Connect算法。该算法利用改进的桥梁检测算法来识别和采样窄道，使得路径规划在窄道内能轻易取得连通性;同时将RRT-Connect算法与任意时间算法相结合，显著地减少了RRT-Connect算法的移动代价。每个算法分别运行100次，与RRT-Connect算法相比，改进后的算法成功次数由34提高到93，规划时间由9.3s减少到4.2s。双足机器人的仿真实验结果表明，该算法能在窄道内取得优化路径，同时可以有效地提高路径规划的效率。

关键词: 快速搜索随机树, 桥梁检测, 任意时间算法, 路径规划, 窄道, 双足机器人