[1]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]
Copy
Path planning of mobile robots based on improved RRT* algorithm
CAAI Transactions on Intelligent Systems[ISSN 1673-4785/CN 23-1538/TP] Volume:
19
Number of periods:
2024 5
Page number:
1209-1217
Column:
学术论文—智能系统
Public date:
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
- CLC:
- TP242.6
- DOI:
- 10.11992/tis.202302010
- 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.
- Similar References:
Memo
-
Last Update:
2024-09-05