Please wait a minute...
工程设计学报  2023, Vol. 30 Issue (6): 707-716    DOI: 10.3785/j.issn.1006-754X.2024.03.141
机器人与机构设计     
基于改进RRT算法的避障路径规划
冯垚1(),周志峰1(),沈亦纯2,王立端3
1.上海工程技术大学 机械与汽车工程学院,上海 201620
2.上海卫星工程研究所,上海 200240
3.上海司南卫星导航技术股份有限公司,上海 201801
Obstacle avoidance path planning based on improved RRT algorithm
Yao FENG1(),Zhifeng ZHOU1(),Yichun SHEN2,Liduan WANG3
1.School of Mechanical and Automotive Engineering, Shanghai University of Engineering Science, Shanghai 201620, China
2.Shanghai Institute of Satellite Engineering, Shanghai 200240, China
3.ComNav Technology Ltd. , Shanghai 201801, China
 全文: PDF(3761 KB)   HTML
摘要:

针对快速搜索随机树(rapidly-exploring random tree, RRT)算法在避障路径规划中存在的对地图适应性弱、采样质量差、无效节点多、规划时间长及路径质量差等问题,提出了一种改进RRT算法。首先,在传统RRT算法的基础上,基于地图复杂程度评估策略计算得到合适的步长及偏置概率,以实现对不同地图的自适应。然后,通过采样区域动态更新策略,使随机树在有效区域内进行采样,以确保随机树的正向生长;在确定采样区域后,利用采样点优化策略来提高采样点的有效性,使得随机树朝目标点附近生长。最后,采用节点重连策略对规划的初始避障路径进行优化,以获得一条弯折次数较少的避障路径。在Python及MATLAB环境中对改进RRT算法的可行性进行验证。结果表明,在面向复杂程度不同的地图和应用于机械臂时,改进RRT算法均能快速规划出一条无碰撞的高质量路径。研究结果可为提高机器人避障路径的规划效率提供参考。

关键词: 路径规划快速搜索随机树算法采样区域动态更新采样点优化节点重连    
Abstract:

Aiming at the problems of rapidly-exploring random tree (RRT) algorithm in obstacle avoidance path planning, such as weak adaptability to maps, poor sampling quality, many invalid nodes, long planning time and poor path quality, an improved RRT algorithm was proposed. Firstly, on the basis of the traditional RRT algorithm, the map complexity evaluation strategy was used to calculate the appropriate step size and bias probability, so as to realize the self-adaptation to different maps. Then, through the dynamic update strategy of sampling area, the random tree was sampled in the effective area to ensure the positive growth. After the sampling area was determined, the sampling point optimization strategy was adopted to improve the effectiveness of sampling points and make the random tree grow near the target points. Finally, the node reconnection strategy was used to optimize the planned initial obstacle avoidance path, and an obstacle avoidance path with fewer bending times was obtained. The feasibility of the improved RRT algorithm was verified in Python and MATLAB environments. The results showed that the improved RRT algorithm could quickly plan a collision-free high-quality path for maps with different complexity and when applied to robotic arms. The research results can provide reference for improving efficiency of robot obstacle avoidance path planning.

Key words: path planning    rapidly-exploring random tree algorithm    dynamic update of sampling area    sampling point optimization    node reconnection
收稿日期: 2023-03-30 出版日期: 2024-01-02
CLC:  TH 113.2  
基金资助: 上海市2022年度“科技创新行动计划”优秀学术/技术带头人计划项目(22XD1433500)
通讯作者: 周志峰     E-mail: fyao1998@163.com;zhousjtu@126.com
作者简介: 冯 垚(1998—),男,贵州遵义人,硕士生,从事路径规划与机械臂控制研究,E-mail: fyao1998@163.com
服务  
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章  
冯垚
周志峰
沈亦纯
王立端

引用本文:

冯垚,周志峰,沈亦纯,王立端. 基于改进RRT算法的避障路径规划[J]. 工程设计学报, 2023, 30(6): 707-716.

Yao FENG,Zhifeng ZHOU,Yichun SHEN,Liduan WANG. Obstacle avoidance path planning based on improved RRT algorithm[J]. Chinese Journal of Engineering Design, 2023, 30(6): 707-716.

链接本文:

https://www.zjujournals.com/gcsjxb/CN/10.3785/j.issn.1006-754X.2024.03.141        https://www.zjujournals.com/gcsjxb/CN/Y2023/V30/I6/707

图1  RRT算法原理
算法偏置概率耗时/s路径长度/cm
传统RRT124.65828.932
改进RRT1-?C1规划失败
1-?C1225.60433.839
1-?C1310.68726.154
1-?C1440.40127.407
表1  引入不同偏置概率时RRT算法的路径规划结果对比
图2  采样区域动态更新示意
图3  采样点优化过程示意
图4  节点重连示意
图5  二维地图1中4种RRT算法的路径规划效果对比
图6  二维地图2中4种RRT算法的路径规划效果对比
图7  二维地图3中4种RRT算法的路径规划效果对比
算法耗时/s节点数/个路径长度/cm
传统RRT59.2186127.859
Bias-RRT22.4423426.194
RRT-Connect12.3191926.940
改进RRT2.226422.596
表2  二维地图1中4种RRT算法的路径规划数据对比
算法耗时/s节点数/个路径长度/cm
传统RRT61.0335729.699
Bias-RRT35.7173827.810
RRT-Connect10.8751825.170
改进RRT4.101521.787
表3  二维地图2中4种RRT算法的路径规划数据对比
算法耗时/s节点数/个路径长度/cm
传统RRT235.0417929.623
Bias-RRT215.6046929.162
RRT-Connect60.8522128.461
改进RRT16.183722.439
表4  二维地图3中4种RRT算法的路径规划数据对比
图8  三维地图中4种RRT算法的路径规划效果对比
算法耗时/s节点数/个路径长度/cm
传统RRT19.19148243.178
Bias-RRT0.53141208.276
RRT-Connect0.42526205.316
改进RRT0.0494178.229
表5  三维地图中4种RRT算法的路径规划数据对比
图9  基于改进RRT算法的机械臂避障路径规划结果
算法耗时/s节点数/个路径长度/cm
传统RRT53.38742133.268
Bias-RRT26.94338117.674
RRT-Connect21.6512695.892
改进RRT2.624578.018
表6  基于4种RRT算法的机械臂避障路径规划数据对比
1 FAN X J, GUO Y J, LIU H, et al. Improved artificial potential field method applied for AUV path planning[J]. Mathematical Problems in Engineering, 2020, 2020: 6523158.
2 DOLGOV D, THRUN S, MONTEMERLO M, et al. Path planning for autonomous vehicles in unknown semi-structured environments[J]. The International Journal of Robotics Research, 2010, 29(5): 485-501.
3 杨明亮,李宁.改进A*算法的移动机器人路径规划[J]. 机械科学与技术,2022,41(5):795-800.
YANG M L, LI N. Study on mobile robot path planning based on improved A* algorithm[J]. Mechanical Science and Technology for Aerospace Engineering, 2022, 41(5): 795-800.
4 王殿君.基于改进A*算法的室内移动机器人路径规划[J].清华大学学报(自然科学版),2012,52(8):1085-1089.
WANG D J. Indoor mobile-robot path planning based on an improved A* algorithm [J]. Journal of Tsinghua University (Science & Technology), 2012, 52(8): 1085-1089.
5 LaVALLE S M, KUFFNER J J. Randomized kinodynamic planning[J]. The International Journal of Robotics Research, 2001, 20(5): 378-400.
6 陈志梅,李敏,邵雪卷,等.基于改进RRT算法的桥式起重机避障路径规划[J].系统仿真学报,2021,33(8):1832-1838.
CHEN Z M, LI M, SHAO X J, et al. Obstacle avoidance path planning of bridge crane based on improved RRT algorithm[J]. Journal of System Simulation, 2021, 33(8): 1832-1838.
7 HSU D, LATOMBE J C, KURNIAWATI H. On the probabilistic foundations of probabilistic roadmap planning[J]. The International Journal of Robotics Research, 2006, 25(7): 83-97.
8 刘亚秋,赵汉琛,刘勋,等.一种基于改进的快速扩展随机树的工业机器人路径避障规划算法[J].信息与控制,2021,50(2):235-246.
LIU Y Q, ZHAO H C, LIU X, et al. An improved RRT based obstacle avoidance path planning algorithm for industrial robot[J]. Information and Control, 2021, 50(2): 235-246.
9 阮晓钢,周静,张晶晶,等.基于子目标搜索的机器人目标导向RRT路径规划算法[J].控制与决策,2020,35(10):2543-2548.
RUAN X G, ZHOU J, ZHANG J J, et al. Robot goal guide RRT path planning based on sub-target search[J]. Control and Decision, 2020, 35(10): 2543-2548.
10 余敏,罗建军,王明明,等.一种改进RRT*结合四次样条的协调路径规划方法[J].力学学报,2020,52(4):1024-1034.
YU M, LUO J J, WANG M M, et al. Coordinated path planning by integrating improved RRT* and quartic spline[J]. Chinese Journal of Theoretical and Applied Mechanics, 2020, 52(4): 1024-1034.
11 YUAN C R, ZHANG W Q, LIU G F, et al. A heuristic rapidly-exploring random trees method for manipulator motion planning[J]. IEEE Access, 2020, 8: 900-910.
12 徐娜,陈雄,孔庆生,等.非完整约束下的机器人运动规划算法[J].机器人,2011,33(6):666-672. doi:10.3724/SP.J.1218.2011.00666
XU N, CHEN X, KONG Q S, et al. Motion planning for robot with nonholonomic constraints[J]. Robot, 2011, 33(6): 666-672.
doi: 10.3724/SP.J.1218.2011.00666
13 杜明博,梅涛,陈佳佳,等.复杂环境下基于RRT的智能车辆运动规划算法[J].机器人,2015,37(4):443-450.
DU M B, MEI T, CHEN J J, et al. RRT-based motion planning algorithm for intelligent vehicle in complex environments[J]. Robot, 2015, 37(4): 443-450.
14 KARAMAN S, FRAZZOLI E. Sampling-based algorithms for optimal motion planning[J]. The International Journal of Robotics Research, 2011, 30(7): 846-894.
15 LUO S Y, LIU S R, ZHANG B T, et al. Path planning algorithm based on Gb informed RRT* with heuristic bias[C]//2017 36th Chinese Control Conference (CCC), Dalian, Jul. 26-28, 2017.
16 张玉伟,左云波,吴国新,等.基于改进Informed-RRT*算法的路径规划研究[J].组合机床与自动化加工技术,2020(7):21-25.
ZHANG Y W, ZUO Y B, WU G X, et al. Research on path planning based on improved Informed-RRT* algorithm[J]. Modular Machine Tool & Automatic Manufacturing Technique, 2020(7): 21-25.
17 KUFFNER J J, LaVALLE S M. RRT-Connect: an efficient approach to single-query path planning[C]//Proceedings of the IEEE International Conference on Robotics and Automation, San Francisco, Apr. 24-28, 2000.
18 韩康,程卫东.基于改进RRT-Connect算法的机械臂路径规划[J].计算机应用与软件,2022,39(3):260-265. doi:10.3969/j.issn.1000-386x.2022.03.042
HAN K, CHENG W D. Path planning of robot arm based on improved RRT algorithm[J]. Computer Applications and Software, 2022, 39(3): 260-265.
doi: 10.3969/j.issn.1000-386x.2022.03.042
19 张丹萌,甄子洋,陈棪.基于改进RRT-Connect的协同航迹规划[J].电光与控制,2021,28(9):25-29. doi:10.3969/j.issn.1671-637X.2021.09.006
ZHANG D M, ZHEN Z Y, CHEN Y. Collaborative path planning based on improved RRT-Connect algorithm[J]. Electronics Optics & Control, 2021, 28(9): 25-29.
doi: 10.3969/j.issn.1671-637X.2021.09.006
20 王坤,黄勃,曾国辉,等.基于改进RRT-Connect的快速路径规划算法[J].武汉大学学报(理学版),2019,65(3):283-289.
WANG K, HUANG B, ZENG G H, et al. Faster path planning based on improved RRT-Connect algorithm[J]. Journal of Wuhan University (Natural Science Edition), 2019, 65(3): 283-289.
21 黄壹凡,胡立坤,薛文超.基于改进RRT-Connect算法的移动机器人路径规划[J].计算机工程,2021,47(8):22-28.
HUANG Y F, HU L K, XUE W C. Mobile robot path planning based on improved RRT-Connect algorithm[J]. Computer Engineering, 2021, 47(8): 22-28.
[1] 田雅琴,胡梦辉,刘文涛,侯寅智. 基于跳点搜索-遗传算法的自主移动机器人路径规划[J]. 工程设计学报, 2023, 30(6): 697-706.
[2] 唐东林, 龙再勇, 汤炎锦, 潘峰, 游传坤. 储罐检测爬壁机器人全遍历路径规划[J]. 工程设计学报, 2020, 27(2): 162-171.
[3] 周结华, 代冀阳, 周继强, 张孝勇. 面向大型机场草坪的割草机器人路径规划及轨迹跟踪控制研究[J]. 工程设计学报, 2019, 26(2): 146-152.
[4] 唐东林, 袁波, 胡琳, 李茂扬, 魏子兵. 储罐探伤爬壁机器人全遍历路径规划方法[J]. 工程设计学报, 2018, 25(3): 253-261.
[5] 梁承姬, 沈珊珊, 胡文辉. 基于路段时间窗考虑备选路径的AGV路径规划[J]. 工程设计学报, 2018, 25(2): 200-208.
[6] 朱龙彪, 王辉, 王景良, 邵小江, 朱志慧. 基于动态时间窗的泊车系统路径规划研究[J]. 工程设计学报, 2017, 24(4): 440-448.
[7] 李保坤, 韩迎鸽, 郭永存, 曹毅, 王成军. Gough-Stewart并联机构无奇异位置路径规划[J]. 工程设计学报, 2016, 23(6): 544-552.
[8] 王辉, 朱龙彪, 王景良, 陈红艳, 邵小江, 朱志慧. 基于Dijkstra-蚁群算法的泊车系统路径规划研究[J]. 工程设计学报, 2016, 23(5): 489-496.
[9] 王辉, 朱龙彪, 朱天成, 陈红艳, 邵小江, 朱志慧. 基于粒子群遗传算法的泊车系统路径规划研究[J]. 工程设计学报, 2016, 23(2): 195-200.
[10] 肖浩, 宋晓琳, 曹昊天. 基于危险斥力场的自动驾驶汽车主动避撞局部路径规划[J]. 工程设计学报, 2012, 19(5): 379-384.