改进的快速探索随机树双足机器人路径规划算法

doi:10.3724/SP.J.1087.2013.00199

计算机应用 ›› 2013, Vol. 33 ›› Issue (01): 199-201.DOI: 10.3724/SP.J.1087.2013.00199

改进的快速探索随机树双足机器人路径规划算法

莫栋成,刘国栋

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

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

Improved path planning algorithm of rapidly-exploring random tree for biped robot

MO Dongcheng,LIU Guodong

School of Internet of Things Engineering, Jiangnan University, Wuxi Jiangsu 214122, China

Received:2012-07-09 Revised:2012-08-12 Online:2013-01-01 Published:2013-01-09
Contact: MO Dongcheng

摘要/Abstract

摘要： 针对快速探索随机树(RRT)算法进行路径规划时随机性大且未考虑移动代价的问题，提出了任意时间快速探索随机树算法。生成一组快速探索随机树，之后每个树都重新使用上个树的信息来不断改进树的延伸。为进一步优化算法，使用节点缓存来生成一个引力函数来减少移动代价。最终的算法能够快速地生成初始路径，在规划时间内不断地改进路径且通过使用阈值来确保后面路径都比上次的移动代价更小。双足机器人仿真实验中，改进后的算法与初始的算法相比，搜索的节点数由883减少到704，效率提高了近25%。实验结果表明了改进算法的有效性。

关键词: 快速搜索随机树, 路径规划, 双足机器人, 任意时间算法, 移动代价

Abstract: To solve the problems that the Rapidly-exploring Random Tree (RRT) path planning is unstable and not taking cost into consideration, an anytime RRT Algorithm was proposed. The algorithm produced an initial solution very quickly, and then improved its growth by reusing information from the previous trees. Besides, to improve the algorithm, a biased distribution was produced to save the cost by using a waypoint cache. The resulted approach produced an initial solution very quickly, and then improved the quality of this solution within given time. It was guaranteed that subsequent solution would be less costly than all previous ones by using the bound. In the biped robot's simulation experiment, compared to the initial algorithm, the number of search nodes created by the improved algorithm decreases from 883 to 704 and the efficiency increases approximately 25%. The simulation result demonstrates the effectiveness of the improved algorithm.

Key words: Rapidly-exploring Random Tree (RRT), path planning, biped robot, anytime algorithm, cost

中图分类号:

TP24
TP18

莫栋成刘国栋. 改进的快速探索随机树双足机器人路径规划算法[J]. 计算机应用, 2013, 33(01): 199-201.

MO Dongcheng LIU Guodong. Improved path planning algorithm of rapidly-exploring random tree for biped robot[J]. Journal of Computer Applications, 2013, 33(01): 199-201.

参考文献

［1］夏泽洋,陈恳,熊璟,等.仿人机器人运动规划研究进展［J］.高技术通讯,2007,17(10):1092-1099.

［2］FU C L, CHEN K. Gait synthesis and sensory control of stair climbing for a humanoid robot ［J］. IEEE Transactions on Industrial Electronics, 2008, 55(5): 2111-2120.

［3］石为人，黄兴华，周伟.基于改进人工势场法的移动机器人路径规划［J］.计算机应用,2010,30(8):2021-2023.

［4］JEAN F. Complexity of nonholonomic motion planning ［J］. International Journal of Control, 2001, 74(8): 776-782.

［5］LaVALLE S M. Motion planning: the essentials ［J］. IEEE Robotics and Automation Society Magazine, 2011, 18(1): 79-89.

［6］康亮，赵春霞，郭剑辉.未知环境下改进的基于RRT算法的移动机器人路径规划［J］.模式识别与人工智能,2009,22(3):337-343.

［7］LAVALLE S M, KUFFNER Jr, J J. Rapidly-exploring random trees: progress and prospects ［C］// Proceedings of the Fourth Workshop on the Algorithmic Foundations of Robotics. Natick, MA: A K Peters, 2000: 45-59.

［8］张振荣，刘惊雷，张伟.一种生成最优联盟结构的任意时间算法［J］.计算机工程,2011,37(2)：185-187.

［9］郭亚军，鲁汉榕.任意时间算法的性能描述［J］.武汉交通科技大学学报:交通科学与工程版,2000,24(5):562-565.

［10］URMSON C, SIMMONS R. Approaches for heuristically biasing RRT growth ［C］// IROS 2003: Proceedings of the 2003 IEEE/RSJ International Conference on Intelligent Robots and Systems. Piscataway: IEEE Press, 2003: 1178-1183.

［11］夏泽洋，陈恳.仿人机器人足迹规划建模及算法实现［J］.机器人,2008,30(3):231-237.

［12］胡金东，刘国栋.双足机器人步行模式的在线全身修正［J］.计算机应用，2011,31(1):286-288,292.

［13］梶田秀司.仿人机器人［M］.管贻生，译.北京：清华大学出版社，2007.

[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): 3499-3507.
[11]	徐小强, 王明勇, 冒燕. 基于改进人工势场法的移动机器人路径规划[J]. 计算机应用, 2020, 40(12): 3508-3512.
[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.

改进的快速探索随机树双足机器人路径规划算法

Improved path planning algorithm of rapidly-exploring random tree for biped robot

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics