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

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

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

莫栋成,刘国栋

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

收稿日期:2013-03-07 修回日期:2013-03-28 出版日期:2013-08-01 发布日期:2013-09-11
通讯作者: 莫栋成
作者简介:莫栋成(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]. 计算机应用, 2021, 41(9): 2560-2568.
[2]	魏博, 杨茸, 舒思豪, 万勇, 苗建国. 基于离子运动-人工蜂群算法的移动机器人路径规划[J]. 计算机应用, 2021, 41(2): 379-383.
[3]	黄书召, 田军委, 乔路, 王沁, 苏宇. 基于改进遗传算法的无人机路径规划[J]. 计算机应用, 2021, 41(2): 390-397.
[4]	王家亮, 李树华, 张海涛. 基于贝叶斯估计与区域划分遍历的四轴飞行器避障路径规划算法[J]. 计算机应用, 2021, 41(2): 384-389.
[5]	李伟, 金世俊. 基于人工势场法和启发式采样的最优路径收敛方法[J]. 计算机应用, 2021, 41(10): 2912-2918.
[6]	刘思嘉, 童向荣. 基于强化学习的城市交通路径规划[J]. 计算机应用, 2021, 41(1): 185-190.
[7]	祁玄玄, 黄家骏, 曹建安. 基于改进A^*算法的无人车路径规划[J]. 计算机应用, 2020, 40(7): 2021-2027.
[8]	徐晓强, 秦品乐, 曾建朝. 基于改进粒子群优化算法的牙齿正畸路径规划方法[J]. 计算机应用, 2020, 40(7): 1938-1943.
[9]	韩雨涝, 房鼎益. 联合无线充电与数据收集的移动充电装置多目标路径规划算法[J]. 计算机应用, 2020, 40(6): 1745-1750.
[10]	徐小强, 王明勇, 冒燕. 基于改进人工势场法的移动机器人路径规划[J]. 计算机应用, 2020, 40(12): 3508-3512.
[11]	屈立成, 吕娇, 赵明, 王海飞, 屈艺华. 基于三维时空地图和运动分解的多机器人路径规划算法[J]. 计算机应用, 2020, 40(12): 3499-3507.
[12]	童心赤, 张华军, 郭航. 多方向无人水面艇路径规划算法[J]. 计算机应用, 2020, 40(11): 3373-3378.
[13]	刘昂, 蒋近, 徐克锋. 改进蚁群和鸽群算法的机器人路径规划[J]. 计算机应用, 2020, 40(11): 3366-3372.
[14]	梅伟, 赵云涛, 毛雪松, 李维刚. 基于离散灰狼算法的喷涂机器人路径规划方法[J]. 计算机应用, 2020, 40(11): 3379-3384.
[15]	袁蒙恩, 陈立家, 冯子凯. 基于单目视觉的多种群粒子群机械臂路径规划算法[J]. 计算机应用, 2020, 40(10): 2863-2871.