[1]郭利进,李强.基于改进RRT*算法的移动机器人路径规划[J].智能系统学报,2024,19(5):1209-1217.[doi:10.11992/tis.202302010]
GUO Lijin,LI Qiang.Path planning of mobile robots based on improved RRT* algorithm[J].CAAI Transactions on Intelligent Systems,2024,19(5):1209-1217.[doi:10.11992/tis.202302010]
点击复制
GUO Lijin,LI Qiang.Path planning of mobile robots based on improved RRT* algorithm[J].CAAI Transactions on Intelligent Systems,2024,19(5):1209-1217.[doi:10.11992/tis.202302010]
基于改进RRT*算法的移动机器人路径规划
《智能系统学报》[ISSN 1673-4785/CN 23-1538/TP] 卷:
19
期数:
2024年第5期
页码:
1209-1217
栏目:
学术论文—智能系统
出版日期:
2024-09-05
- Title:
- Path planning of mobile robots based on improved RRT* algorithm
- Keywords:
- mobile robot; dynamic environment; optimal path; RRT* algorithm; dynamic window approaches algorithm; redundant node; safety; smoothness
- 分类号:
- TP242.6
- 文献标志码:
- 2024-03-23
- 摘要:
- 针对传统快速随机搜索树*(rapidly-exploring random tree*, RRT*)算法收敛速率较慢，且不适用于动态场景等问题，提出一种基于目标点偏置和冗余节点删除的改进RRT*算法，用于解决移动机器人快速找到无碰撞最优路径的问题。此算法在RRT*算法基础上，首先对采样点进行优化处理，保证路径最优的同时减少搜寻时间；其次引入路径节点最大值概念，删除扩展树冗余节点以提高算法效率；最后结合动态窗口(dynamic window approaches, DWA)算法提高路径的安全性和平滑性，实现对动态障碍物的避障。通过3种不同地图下的仿真验证，改进算法能有效提升路径质量，且大幅降低运行时间。
- Abstract:
- To address the problems associated with the traditional rapidly-exploring random tree* (RRT*) algorithm, including its slow convergence rate and unsuitability for dynamic environments, we propose an improved RRT* algorithm. This new approach biases toward the target point and eliminates redundant nodes to efficiently find collision-free optimal paths for mobile robots. The improved algorithm begins by optimizing the sampling points, which ensures the discovery of the optimal path while reducing search time. Then, it introduces the concept of path maximization to identify and remove redundant nodes from the extended tree, thereby enhancing algorithm efficiency. Additionally, the improved algorithm is integrated with the dynamic window approaches algorithm, which enhances the safety and smoothness of the path and enables effective obstacle avoidance in dynamic environments. Simulations conducted on three different maps demonstrate that the improved algorithm significantly improves path quality and greatly reduces running time.
- 参考文献/References:
-
[1] GUL F, MIR I, ABUALIGAH L, et al. A consolidated review of path planning and optimization techniques: technical perspectives and future directions[J]. Electronics, 2021, 10(18): 2250.
[2] WU Xiaojing, XU Lei, ZHEN Ran, et al. Biased sampling potentially guided intelligent bidirectional RRT algorithm for UAV path planning in 3D environment[J]. Mathematical problems in engineering, 2019, 2019: 5157403.
[3] LYU Desheng, CHEN Ziwei, CAI Zesu, et al. Robot path planning by leveraging the graph-encoded Floyd algorithm[J]. Future generation computer systems, 2021, 122: 204-208.
[4] 张子迎, 宫思远, 徐东, 等. 多机器人任务分配与路径规划算法[J]. 哈尔滨工程大学学报, 2019, 40(10): 1753-1759.
ZHANG Ziying, GONG Siyuan, XU Dong, et al. Research on multi-robot task assignment and path planning algorithm[J]. Journal of Harbin Engineering University, 2019, 40(10): 1753-1759.
[5] 崔永杰, 王寅初, 何智, 等. 基于改进RRT算法的猕猴桃采摘机器人全局路径规划[J]. 农业机械学报, 2022, 53(6): 151-158.
CUI Yongjie, WANG Yinchu, HE Zhi, et al. Global path planning of kiwifruit harvesting robot based on improved RRT algorithm[J]. Transactions of the Chinese society for agricultural machinery, 2022, 53(6): 151-158.
[6] 张飞, 白伟, 乔耀华, 等. 基于改进D*算法的无人机室内路径规划[J]. 智能系统学报, 2019, 14(4): 662-669.
ZHANG Fei, BAI Wei, QIAO Yaohua, et al. UAV indoor path planning based on improved D* algorithm[J]. CAAI transactions on intelligent systems, 2019, 14(4): 662-669.
[7] 李颀, 汪伟. 多全向轮协同分拣平台的路径规划[J]. 系统仿真学报, 2021, 33(3): 698-709.
LI Qi, WANG Wei. Path designing of multi-omnidirectional wheel collaborative sorting platform[J]. Journal of system simulation, 2021, 33(3): 698-709.
[8] 黄鑫, 董红斌. 面向无人机路径规划的双层多目标粒子群算法[J]. 应用科技, 2023, 50(3): 1-10.
HUANG Xin, DONG Hongbin. Double-layer multi-objective particle swarm algorithm for UAV path planning[J]. Applied science and technology, 2023, 50(3): 1-10.
[9] 申铉京, 施英杰, 黄永平, 等. 基于双向蚁群算法的路径规划研究[J]. 哈尔滨工程大学学报, 2023, 44(5): 865-875.
SHEN Xuanjing, SHI Yingjie, HUANG Yongping, et al. Path planning optimization using the bidirectional ant colony algorithm[J]. Journal of Harbin Engineering University, 2023, 44(5): 865-875.
[10] 成怡, 肖宏图. 融合改进A*算法和Morphin算法的移动机器人动态路径规划[J]. 智能系统学报, 2020, 15(3): 546-552.
CHENG Yi, XIAO Hongtu. Mobile-robot dynamic path planning based on improved A* and Morphin algorithms[J]. CAAI transactions on intelligent systems, 2020, 15(3): 546-552.
[11] 邹宇星, 李立君, 高自成. 基于改进PRM的采摘机器人机械臂避障路径规划[J]. 传感器与微系统, 2019, 38(1): 52-56.
ZOU Yuxing, LI Lijun, GAO Zicheng. Obstacle avoidance path planning for harvesting robot arm based on improved PRM[J]. Transducer and microsystem technologies, 2019, 38(1): 52-56.
[12] WANG Hao, LI Guoqing, HOU Jie, et al. A path planning method for underground intelligent vehicles based on an improved RRT* algorithm[J]. Electronics, 2022, 11(3): 294.
[13] 许万, 杨晔, 余磊涛, 等. 一种基于改进RRT*的全局路径规划算法[J]. 控制与决策, 2022, 37(4): 829-838.
XU Wan, YANG Ye, YU Leitao, et al. A global path planning algorithm based on improved RRT*[J]. Control and decision, 2022, 37(4): 829-838.
[14] 夏炎, 隋岩. PRM路径规划算法优化研究[J]. 应用科技, 2010, 37(10): 1-5.
XIA Yan, SUI Yan. Research on optimization of PRM path planning algorithm[J]. Applied science and technology, 2010, 37(10): 1-5.
[15] KARAMAN S, FRAZZOLI E. Sampling-based algorithms for optimal motion planning[J]. International journal of robotics research, 2011, 30(7): 846-894.
[16] GAMMELL J D, SRINIVASA S S, BARFOOT T D. Informed RRT*: Optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic[C]//2014 IEEE/RSJ International Conference on Intelligent Robots and Systems. Chicago: IEEE, 2014: 2997-3004.
[17] 李娟, 张韵, 陈涛. 改进RRT算法在未知三维环境下AUV目标搜索中的应用[J]. 智能系统学报, 2022, 17(2): 368-375.
LI Juan, ZHANG Yun, CHEN Tao. Application of the improved RRT algorithm to AUV target search in an unknown 3D environment[J]. CAAI transactions on intelligent systems, 2022, 17(2): 368-375.
[18] SPANOGIANOPOULOS S, SIRLANTZIS K. Non-holonomic path planning of car-like robot using RRT*FN[C]//2015 12th International Conference on Ubiquitous Robots and Ambient Intelligence. Goyangi: IEEE, 2015: 53-57.
[19] 张腾龙, 李擎. 基于B-RRT*FND算法的移动机器人路径规划[J]. 控制与决策, 2023, 38(11): 3121-3127.
ZHANG Tenglong, LI Qing. Path planning of AGV based on B-RRT*FND algorithm[J]. Control and decision, 2023, 38(11): 3121-3127.
[20] QIN Hongwei, SHAO Shiliang, WANG Ting, et al. Review of autonomous path planning algorithms for mobile robots[J]. Drones, 2023, 7(3): 211.
[21] PEREIRA N, RIBEIRO A F, LOPES G, et al. Path planning towards non-compulsory multiple targets using TWIN-RRT[J]. Industrial robot, 2016, 43(4): 370-379.
[22] 刘成菊, 韩俊强, 安康. 基于改进RRT算法的RoboCup机器人动态路径规划[J]. 机器人, 2017, 39(1): 8-15.
LIU Chengju, HAN Junqiang, AN Kang. Dynamic path planning based on an improved RRT algorithm for RoboCup robot[J]. Robot, 2017, 39(1): 8-15.
[23] CHAI Qisen, WANG Yujun. RJ-RRT: improved RRT for path planning in narrow passages[J]. Applied sciences, 2022, 12(23): 12033.
[24] WANG Jiankun, CHI Wenzheng, LI Chenming, et al. Neural RRT*: learning-based optimal path planning[J]. IEEE transactions on automation science and engineering, 2020, 17(4): 1748-1758.
[25] ZHOU Lintao, WU Nanpeng, CHEN Hu, et al. RRT*-fuzzy dynamic window approach (RRT*-FDWA) for collision-free path planning[J]. Applied sciences, 2023, 13(9): 5234.
[26] DAM T, CHALVATZAKI G, PETERS J, et al. Monte-Carlo robot path planning[J]. IEEE robotics and automation letters, 2022, 7(4): 11213-11220.
[27] FRANSEN K, EEKELEN J V. Efficient path planning for automated guided vehicles using A* (Astar) algorithm incorporating turning costs in search heuristic[J]. International journal of production research, 2021, 61: 707-725.
[28] MENG B H, GODAGE I S, KANJ I. RRT*-based path planning for continuum arms[J]. IEEE robotics and automation letters, 2022, 7(3): 6830-6837.
[29] DING Jun, ZHOU Yinxuan, HUANG Xia, et al. An improved RRT* algorithm for robot path planning based on path expansion heuristic sampling[J]. Journal of computational science, 2023, 67: 101937.
[30] 蒲兴成, 谭令. 基于自适应动态窗口改进细菌算法与移动机器人路径规划[J]. 智能系统学报, 2023, 18(2): 314-324.
PU Xingcheng, TAN Ling. A mobile robot path planning method based on adaptive DWA and an improved bacteria algorithm[J]. CAAI transactions on intelligent systems, 2023, 18(2): 314-324.
- 相似文献/References:
-
[1]蔡自兴,王 勇,王 璐.基于角点聚类的移动机器人自然路标检测与识别[J].智能系统学报,2006,1(1):52.
CAI Zi-xing,WANG Yong,WANG Lu.Corner clustering based detection and recognition of natural landmark for mobile robot[J].CAAI Transactions on Intelligent Systems,2006,1():52.
[2]杨甜甜,刘志远,陈 虹,等.移动机器人编队控制的现状与问题[J].智能系统学报,2007,2(4):21.
YANG Tian-tian,LIU Zhi-yuan,CHEN Hong,et al.Formation control of mobile robots: state and open prob lems[J].CAAI Transactions on Intelligent Systems,2007,2():21.
[3]李润伟,蔡自兴,童宇,等.基于ATM的提高狭窄环境探测精度的改进方法[J].智能系统学报,2008,3(4):283.
LI Run-wei,CAI Zi-xing,TONG Yu.Improving the accuracy of exploring the narrow environment by using ATM[J].CAAI Transactions on Intelligent Systems,2008,3():283.
[4]霍成立,谢 凡,秦世引.面向室内移动机器人的无迹滤波实时导航方法[J].智能系统学报,2009,4(4):295.
HUO Cheng-li,XIE Fan,QIN Shi-yin.A case study in realtime UKFbased navigation for indoor autonomous travel of mobile robots[J].CAAI Transactions on Intelligent Systems,2009,4():295.
[5]海 丹,李 勇,张 辉,等.无线传感器网络环境下基于粒子滤波的移动机器人SLAM算法[J].智能系统学报,2010,5(5):425.[doi:10.3969/j.issn.1673-4785.2010.05.008]
HAI Dan,LI Yong,ZHANG Hui,et al.Simultaneous localization and mapping of a mobile robot in wireless sensor networks based on particle filtering[J].CAAI Transactions on Intelligent Systems,2010,5():425.[doi:10.3969/j.issn.1673-4785.2010.05.008]
[6]房立金,王洪光.架空线移动机器人行走越障特点[J].智能系统学报,2010,5(6):492.
FANG Li-jin,WANG Hong-guang.Research on the characteristics of the movement and obstacleclearing processes of a wiresuspended mobile robot[J].CAAI Transactions on Intelligent Systems,2010,5():492.
[7]任立敏,王伟东,杜志江.移动机器人队形控制关键技术及其进展[J].智能系统学报,2013,8(5):381.[doi:10.3969/j.issn.1673-4785.201302011]
REN Limin,WANG Weidong,DU Zhijiang.Key technologies and development of? formation control of mobile robots[J].CAAI Transactions on Intelligent Systems,2013,8():381.[doi:10.3969/j.issn.1673-4785.201302011]
[8]贺超,刘华平,孙富春,等.采用Kinect的移动机器人目标跟踪与避障[J].智能系统学报,2013,8(5):426.[doi:10.3969/j.issn.1673-4785.201301028]
HE Chao,LIU Huaping,SUN Fuchun,et al.Target tracking and obstacle avoidance of mobile robot using Kinect[J].CAAI Transactions on Intelligent Systems,2013,8():426.[doi:10.3969/j.issn.1673-4785.201301028]
[9]阮晓钢,庞涛,张晓平,等.一种基于情感智能的机器人自主趋光行为研究[J].智能系统学报,2015,10(1):97.[doi:10.3969/j.issn.1673-4785.201312035]
RUAN Xiaogang,PANG Tao,ZHANG Xiaoping,et al.Research on the autonomous phototaxis behavior of a robot based on emotion intelligence[J].CAAI Transactions on Intelligent Systems,2015,10():97.[doi:10.3969/j.issn.1673-4785.201312035]
[10]沈博闻,于宁波,刘景泰.仓储物流机器人集群的智能调度和路径规划[J].智能系统学报,2014,9(6):659.[doi:10.3969/j.issn.1673-4785.201312048]
SHEN Bowen,YU Ningbo,LIU Jingtai.Intelligent scheduling and path planning of warehouse mobile robots[J].CAAI Transactions on Intelligent Systems,2014,9():659.[doi:10.3969/j.issn.1673-4785.201312048]
[11]孙自飞,钱堃,马旭东,等.多传感器的移动机器人可定位性估计与自定位[J].智能系统学报,2017,12(4):443.[doi:10.11992/tis.201607007]
SUN Zifei,QIAN Kun,MA Xudong,et al.Self-localization of mobile robot in dynamic environments based onlocalizability estimation with multi-sensor observation[J].CAAI Transactions on Intelligent Systems,2017,12():443.[doi:10.11992/tis.201607007]
备注/Memo
收稿日期:2023-2-15。
基金项目:国家自然科学基金项目（61973234）.
作者简介:郭利进，教授，博士，主要研究方向为机器人信号获取与处理、移动机器人导航与控制。主持和参与市级以上科研项目20余项，发表学术论文60余篇。E-mail：Doctor_guo@tiangong.edu.cn;李强，硕士研究生，主要研究方向为动态环境下移动机器人路径规划。E-mail：winkli_tgu04@163.com。
通讯作者:郭利进. E-mail：Doctor_guo@tiangong.edu.cn
更新日期/Last Update:
2024-09-05