改进的RRT-Connect双足机器人路径规划算法

计算机应用 ›› 2013, Vol. 33 ›› Issue (08): 2289-2292.

改进的RRT-Connect双足机器人路径规划算法

莫栋成,刘国栋

江南大学物联网工程学院,江苏无锡 214122

收稿日期:2013-03-07 修回日期:2013-03-28 发布日期:2013-09-11 出版日期:2013-08-01
通讯作者: 莫栋成
作者简介:莫栋成(1990-)，男，江苏盐城人，硕士研究生，主要研究方向：机器人的路径规划、智能控制;
刘国栋(1950-)，男，辽宁沈阳人，教授，博士，主要研究方向：机器人系统、智能控制。

Improved RRT-Connect path planning algorithm for biped robot

MO Dongcheng,LIU Guodong

School of IoT Engineering, Jiangnan University, Wuxi Jiangsu 214122, China

Received:2013-03-07 Revised:2013-03-28 Online:2013-09-11 Published:2013-08-01
Contact: MO Dongcheng

摘要/Abstract

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

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

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

中图分类号:

TP242

莫栋成刘国栋. 改进的RRT-Connect双足机器人路径规划算法[J]. 计算机应用, 2013, 33(08): 2289-2292.

MO Dongcheng LIU Guodong. Improved RRT-Connect path planning algorithm for biped robot[J]. Journal of Computer Applications, 2013, 33(08): 2289-2292.

[1]	田润泽, 周宇龙, 朱洪, 薛岗. 基于局部信息的服务迁移路径选择算法[J]. 《计算机应用》唯一官方网站, 2024, 44(7): 2168-2174.
[2]	马天, 席润韬, 吕佳豪, 曾奕杰, 杨嘉怡, 张杰慧. 基于深度强化学习的移动机器人三维路径规划方法[J]. 《计算机应用》唯一官方网站, 2024, 44(7): 2055-2064.
[3]	李建强, 何舟. 面向多行程取送货车辆路径问题的混合NSGA-Ⅱ[J]. 《计算机应用》唯一官方网站, 2024, 44(4): 1187-1194.
[4]	黄海新, 于广威, 程寿山, 李春明. 基于改进灰狼优化的桥梁检测爬壁机器人全覆盖路径规划[J]. 《计算机应用》唯一官方网站, 2024, 44(3): 966-971.
[5]	宋紫阳, 李军怀, 王怀军, 苏鑫, 于蕾. 基于路径模仿和SAC强化学习的机械臂路径规划算法[J]. 《计算机应用》唯一官方网站, 2024, 44(2): 439-444.
[6]	李源潮, 陶重犇, 王琛. 基于最大熵深度强化学习的双足机器人步态控制方法[J]. 《计算机应用》唯一官方网站, 2024, 44(2): 445-451.
[7]	邓辅秦, 官桧锋, 谭朝恩, 付兰慧, 王宏民, 林天麟, 张建民. 基于请求与应答通信机制和局部注意力机制的多机器人强化学习路径规划方法[J]. 《计算机应用》唯一官方网站, 2024, 44(2): 432-438.
[8]	邓辅秦, 谭朝恩, 黎俊炜, 钟家铭, 付兰慧, 张建民, 王宏民, 李楠楠, 姜炳春, 林天麟. 面向大型仓储环境的基于冲突搜索算法[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3854-3860.
[9]	孙鉴, 马宝全, 吴隹伟, 杨晓焕, 武涛, 陈攀. 地震场景下无人机群路径规划与任务分配均衡联合优化[J]. 《计算机应用》唯一官方网站, 2024, 44(10): 3232-3239.
[10]	李永迪, 李彩虹, 张耀玉, 张国胜. 基于改进SAC算法的移动机器人路径规划[J]. 《计算机应用》唯一官方网站, 2023, 43(2): 654-660.
[11]	王龙宝, 栾茵琪, 徐亮, 曾昕, 张帅, 徐淑芳. 基于动态簇粒子群优化的无人机集群路径规划方法[J]. 《计算机应用》唯一官方网站, 2023, 43(12): 3816-3823.
[12]	黄霖, 符强, 童楠. 基于自适应调整哈里斯鹰优化算法求解机器人路径规划问题[J]. 《计算机应用》唯一官方网站, 2023, 43(12): 3840-3847.
[13]	刘晨, 陈洋, 符浩. 基于值函数迭代的持续监测无人机路径规划[J]. 《计算机应用》唯一官方网站, 2023, 43(10): 3290-3296.
[14]	廖发康, 周亚丽, 张奇志. 变长度柔性双足机器人行走控制及稳定性分析[J]. 《计算机应用》唯一官方网站, 2023, 43(1): 312-320.
[15]	范厚明, 牟爽, 岳丽君. 考虑冲突和拥堵的自动导引车调度与路径规划协同优化[J]. 《计算机应用》唯一官方网站, 2022, 42(7): 2281-2291.