基于改进RRT*算法的无人艇路径规划快速求解算法

doi:10.16182/j.issn1004731x.joss.22-1381

摘要/Abstract

摘要：

针对快速扩展随机树(RRT)算法在无人艇路径规划工作中目的性较弱的问题，提出一种改进的无人艇路径规划快速求解算法。对人工势场法进行改进，额外添加4个方向的受力分析，综合计算无人艇所受合力；重新定义转向角度的计算 方法，避免其进入局部最优陷阱，使其可以顺利抵达目标点，得到一条初始路径；利用该初始路径来设定快速扩展随机树算法的随机点采样区域，通过降低随机采样点生成在无价值区域的概率，以提高算法的目的性和时效性，得到二次规划路径；对二次规划路径进行冗余点去除操作，减少路径节点的同时可以进一步降低路径代价，得到最终的规划路径。实验结果表明：改进算法在取得相近代价的路径时，运行时间最多降低了84.14%，采样点数量最多减少了70.09%，算法质量更好，运行效率更高。

关键词: 无人艇, 路径规划, RRT*算法, APF算法, APF-RRT*算法

Abstract:

Aiming at the weak purposiveness of rapidly exploring random tree algorithm in USV path planning, a modified rapid algorithm is proposed. The artificial potential field method is improved and theforce analysis in four directions is added to comprehensively calculate the resultant force on USV. The calculation method of steering angle is redefined to avoid entering the local optimal trap and can reach the target point smoothly to obtain an initial path. The initial path is used to set the random point sampling area of rapidly exploring random tree algorithm. By reducing the probability of random points generated in worthless area during sampling, the purpose and timeliness of the algorithm are improved, and the quadratic programming path is obtained. Theredundant points of thepath planned by rapidly exploring random tree algorithm is removed, in which the path cost can be further reduced while the path nodes are reduced, and the final planned path is obtained. Experimental results show that, compared with the original rapidly exploring random tree algorithm, the modified algorithm can lower the running time and the number of sampling nodes by 84.14% and 70.09%, respectively, when obtaining a path with a similar cost. The proposed algorithm has better quality and higher running efficiency.

Key words: USV, path planning, RRT* algorithm, APF algorithm, APF-RRT* algorithm

中图分类号:

TP391.9

姜兆祯,王文龙,孙文祺 . 基于改进RRT^*算法的无人艇路径规划快速求解算法[J]. 系统仿真学报, 2024, 36(4): 888-900.

Jiang Zhaozhen,Wang Wenlong,Sun Wenqi . Path Planning Rapid Algorithm Based on Modified RRT* for Unmanned Surface Vessel[J]. Journal of System Simulation, 2024, 36(4): 888-900.

图/表 19

图1

图2

图3

图4

图5

图6

图7

图8

图9

图10

表1

图11

图12

图13

图14

图15

表2

图16

表3

参考文献 38

1	Huang Yamin, Chen Linying, Chen Pengfei, et al. Ship Collision Avoidance Methods: State-of-the-art[J]. Safety Science, 2020, 121: 451-473.
2	Vagale Anete, Oucheikh Rachid, Bye Robin T, et al. Path Planning and Collision Avoidance for Autonomous Surface Vehicles I: A Review[J]. Journal of Marine Science and Technology, 2021, 26(4): 1292-1306.
3	Vagale Anete, Bye Robin T, Oucheikh Rachid, et al. Path Planning and Collision Avoidance for Autonomous Surface Vehicles II: A Comparative Study of Algorithms[J]. Journal of Marine Science and Technology, 2021, 26(4): 1307-1323.
4	Khatib O. Real-time Obstacle Avoidance for Manipulators and Mobile Robots[J]. The International Journal of Robotics Research, 1986, 5(1): 90-98.
5	Naeem W, Henrique S C, Hu Liang. A Reactive COLREGs-compliant Navigation Strategy for Autonomous Maritime Navigation[J]. IFAC-PapersOnLine, 2016, 49(23): 207-213.
6	Yaguchi Yuichi, Tamagawa Kyota. A Waypoint Navigation Method with Collision Avoidance Using an Artificial Potential Method on Random Priority[J]. Artificial Life and Robotics, 2020, 25(2): 278-285.
7	Hongguang Lü, Yin Yong. COLREGS-constrained Real-time Path Planning for Autonomous Ships Using Modified Artificial Potential Fields[J]. Journal of Navigation, 2019, 72(3), 72: 588-608.
8	Zhang Liang, Mou Junmin, Chen Pengfei, et al. Path Planning for Autonomous Ships: A Hybrid Approach Based on Improved APF and Modified VO Methods[J]. Journal of Marine Science and Engineering, 2021, 9(7): 761.
9	Li Lingyu, Wu Defeng, Huang Youqiang, et al. A Path Planning Strategy Unified with a COLREGS Collision Avoidance Function Based on Deep Reinforcement Learning and Artificial Potential Field[J]. Applied Ocean Research, 2021, 113: 102759.
10	LaValle S M. Rapidly-exploring Random Trees: A New Tool for Path Planning[J]. Research Report 9811, 1998.
11	Karaman S, Frazzoli E. Sampling-based Algorithms for Optimal Motion Planning[J]. The International Journal of Robotics Research, 2011, 30(7): 846-894.
12	LaValle S M. James J Kuffner Jr. Randomized Kinodynamic Planning[J]. The International Journal of Robotics Research, 2001, 20(5): 378-400.
13	J J Ir Kuffner, LaValle S M. RRT-connect: An Efficient Approach to Single-query Path Planning[C]//Proceedings 2000 ICRA. Millennium Conference. IEEE International Conference on Robotics and Automation. Symposia Proceedings. Piscataway, NJ, USA: IEEE, 2000: 995-1001.
14	Gammell Jonathan D, Srinivasa S S, Barfoot Timothy 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. Piscataway, NJ, USA: IEEE, 2014: 2997-3004.
15	Chiang H T L, Tapia L. COLREG-RRT: An RRT-based COLREGS-compliant Motion Planner for Surface Vehicle Navigation[J]. IEEE Robotics and Automation Letters, 2018, 3(3): 2024-2031.
16	Enevoldsen Thomas T, Galeazzi Roberto. Grounding-aware RRT^⁎ for Path Planning and Safe Navigation of Marine Crafts in Confined Waters[J]. IFAC-PapersOnLine, 2021, 54(16): 195-201.
17	Zaccone Raphael, Martelli Michele. A Collision Avoidance Algorithm for Ship Guidance Applications[J]. Journal of Marine Engineering & Technology, 2020, 19(S1): 62-75.
18	Chen Xinjia, Liu Yanxia, Hong Xiaobin, et al. Unmanned Ship Path Planning Based on RRT[C]//Intelligent Computing Theories and Application. Cham: Springer International Publishing, 2018: 102-110.
19	Yuan Chengren, Liu Guifeng, Zhang Wenqun, et al. An Efficient RRT Cache Method in Dynamic Environments for Path Planning[J]. Robotics and Autonomous Systems, 2020, 131: 103595.
20	Taheri Ehsan, Mohammad Hossein Ferdowsi, Danesh Mohammad. Closed-loop Randomized Kinodynamic Path Planning for an Autonomous Underwater Vehicle[J]. Applied Ocean Research, 2019, 83: 48-64.
21	Tahir Zaid, Qureshi A H, Ayaz Yasar, et al. Potentially Guided Bidirectionalized RRT^* for Fast Optimal Path Planning in Cluttered Environments[J]. Robotics and Autonomous Systems, 2018, 108: 13-27.
22	裴以建, 杨超杰, 杨亮亮. 基于改进RRT^*的移动机器人路径规划算法[J]. 计算机工程, 2019, 45(5): 285-290, 297.
	Pei Yijian, Yang Chaojie, Yang Liangliang. Path Planning Algorithm for Mobile Robot Based on Improved RRT^* [J]. Computer Engineering, 2019, 45(5): 285-290, 297.
23	Wang Xinyu, Li Xiaojuan, Yong Guan, et al. Bidirectional Potential Guided RRT^* for Motion Planning[J]. IEEE Access, 2019, 7: 95046-95057.
24	Xi Yingqi, Shen Wei, Zhang Wen, et al. A Real-time Dynamic Path Planning Method Combining Artificial Potential Field Method and Biased Target RRT Algorithm[J]. Journal of Physics: Conference Series, 2021, 1905(1): 012015.
25	Zhu Jia, Zhao Shili, Zhao Ran. Path Planning for Autonomous Underwater Vehicle Based on Artificial Potential Field and Modified RRT[C]//2021 International Conference on Computer, Control and Robotics (ICCCR). Piscataway, NJ, USA: IEEE, 2021: 21-25.
26	Huang Shunyu. Path Planning Based on Mixed Algorithm of RRT and Artificial Potential Field Method[C]//2021 4th International Conference on Intelligent Robotics and Control Engineering (IRCE). Piscataway, NJ, USA: IEEE, 2021: 149-155.
27	Tang Xiaoya, Chen Feng. Robot Path Planning Algorithm Based on Bi-RRT and Potential Field[C]//2020 IEEE International Conference on Mechatronics and Automation (ICMA). Piscataway, NJ, USA: IEEE, 2020: 1251-1256.
28	Lu Yafei, Wu Anping, Chen Qingyang, et al. An Improved UAV Path Planning Method Based on RRT-APF Hybrid Strategy[C]//2020 5th International Conference on Automation, Control and Robotics Engineering (CACRE). Piscataway, NJ, USA: IEEE, 2020: 81-86.
29	An Hongrui, Hu Jiwei, Lou Ping. Obstacle Avoidance Path Planning Based on Improved APF and RRT[C]//2021 4th International Conference on Advanced Electronic Materials, Computers and Software Engineering (AEMCSE). Piscataway, NJ, USA: IEEE, 2021: 1028-1032.
30	Yuan Qingni, Yi Junhui, Sun Ruitong, et al. Path Planning of a Mechanical Arm Based on an Improved Artificial Potential Field and a Rapid Expansion Random Tree Hybrid Algorithm[J]. Algorithms, 2021, 14(11): 321.
31	Gammell Jonathan D, Srinivasa S S, Barfoot Timothy D. Batch Informed Trees (BIT^*): Sampling-based Optimal Planning Via the Heuristically Guided Search of Implicit Random Geometric Graphs[C]//2015 IEEE International Conference on Robotics and Automation (ICRA). Piscataway, NJ, USA: IEEE, 2015: 3067-3074.
32	Choudhury S, Gammell Jonathan D, Barfoot Timothy D, et al. Regionally Accelerated Batch Informed Trees (RABIT^*): A Framework to Integrate Local Information into Optimal Path Planning[C]//2016 IEEE International Conference on Robotics and Automation (ICRA). Piscataway, NJ, USA: IEEE, 2016: 4207-4214.
33	Sagar Suhas Joshi, Panagiotis Tsiotras. Non-parametric Informed Exploration for Sampling-based Motion Planning[C]//2019 International Conference on Robotics and Automation (ICRA). Piscataway, NJ, USA: IEEE, 2019: 5915-5921.
34	Thomas Thuesen Enevoldsen, Reinartz Christopher, Galeazzi Roberto. COLREGs-informed RRT^* for Collision Avoidance of Marine Crafts[C]//2021 IEEE International Conference on Robotics and Automation (ICRA). Piscataway, NJ, USA: IEEE, 2021: 8083-8089.
35	Li Chenming, Wang Chaoqun, Wang Jiankun, et al. Sliding-window Informed RRT^*: A Method for Speeding up the Optimization and Path Smoothing[C]//2021 IEEE International Conference on Real-time Computing and Robotics (RCAR). Piscataway, NJ, USA: IEEE, 2021: 141-146.
36	Yi Daqing, Thakker R, Gulino C, et al. Generalizing Informed Sampling for Asymptotically-optimal Sampling-based Kinodynamic Planning Via Markov Chain Monte Carlo[C]//2018 IEEE International Conference on Robotics and Automation (ICRA). Piscataway, NJ, USA: IEEE, 2018: 7063-7070.
37	Gustavo D O Véras Luiz, L L Medeiros Felipe, N F Guimaráes Lamartine. Systematic Literature Review of Sampling Process in Rapidly-exploring Random Trees[J]. IEEE Access, 2019, 7: 50933-50953.
38	曹凯, 陈阳泉, 高嵩, 等. 涡流人工势场引导下的RRT^*移动机器人路径规划[J]. 计算机科学与探索, 2021, 15(4): 723-732.
	Cao Kai, Chen Yangquan, Gao Song, et al. Vortex Artificial-potential-field Guided RRT^* for Path Planning of Mobile Robot[J]. Journal of Frontiers of Computer Science & Technology, 2021, 15(4): 723-732.

算法	时间/s			采样点数			路径代价			首次发现路径迭代次数
算法	最大	最小	平均	最大	最小	平均	最大	最小	平均	最大	最小	平均
RRT*	54.07	50.91	53.18	1 166	1 097	1 082	1 071.6	1 060.8	1 065.3	1 026	521	788
改进RRT*	22.83	20.53	21.60	559	540	552	1 070.5	1 063.3	1 067.2	648	347	493

算法	迭代次数	首次发现路径迭代次数			采样点数			时间/s			路径代价
算法	迭代次数	最大	最小	平均	最大	最小	平均	最大	最小	平均	最大	最小	平均
改进APF	/	/	/	/	/	/	/	1.27	1.04	1.17	1 322.43	1 322.43	1 322.43
RRT*	1 000	634	349	472	852	817	834	28.40	24.40	26.47	1 136.75	1 014.58	1 050.35
	1 500	1 089	433	728	1 279	1 195	1 250	68.90	55.70	63.95	1 018.83	1 003.37	1 012.56
	2 000	1 170	348	626	1 711	1 628	1 670	117.80	109.30	113.88	1 115.69	1 006.74	1 010.29
APF-RRT^*	1 000	239	395	320	739	678	704	26.80	34.60	30.61	1 005.69	1 002.84	1 003.78
	1 500	569	277	384	1 102	983	1 060	68.79	50.50	57.81	1 003.00	1 002.35	1 002.78
	2 000	432	225	326	1 477	1 433	1 457	112.60	108.10	110.91	1 004.05	1 001.32	1 002.42

地图	算法	迭代次数	时间/s	采样点数	路径点数	路径代价
实景I	改进APF	/	3.89	/	/	1 144.32
	RRT*	2 000	41.13	1 019	22	1 085.62
	APF-RRT*	1 000	14.81	451	6	1 051.68
实景II	改进APF	/	5.19	/	/	870.01
	RRT*	2 000	81.17	1 197	16	768.04
	APF-RRT*	1 000	12.87	358	4	760.27
实景III	改进APF	/	4.32	/	/	1 105.52
	RRT*	2 000	95.03	1 309	21	1 046.20
	APF-RRT*	1 000	24.19	536	5	1 038.10

[1]	张瑞, 周丽, 刘正洋. 融合RRT*与DWA算法的移动机器人动态路径规划[J]. 系统仿真学报, 2024, 36(4): 957-968.
[2]	李高扬, 黎向锋, 赵康, 金玉超, 易志东, 左敦稳. 全粒子推动野马优化算法的无人机三维路径规划[J]. 系统仿真学报, 2024, 36(3): 595-607.
[3]	闫星宇, 李大焱, 王妮娅, 张凯翔, 毛剑琳. 带障碍物惩罚因子的多机器人路径规划[J]. 系统仿真学报, 2024, 36(3): 673-685.
[4]	余翔, 姜陈, 段思睿, 邓千锐. 改进A*算法和人工势场法的路径规划[J]. 系统仿真学报, 2024, 36(3): 782-794.
[5]	庄鹤林, 夏小云, 李康顺, 陈泽丰, 张先超. 电动汽车路径规划模型与算法研究进展[J]. 系统仿真学报, 2024, 36(2): 320-337.
[6]	唐昀超, 祁少军, 朱立学, 卓献荣, 张芸齐, 孟繁. 移动机器人避障运动研究[J]. 系统仿真学报, 2024, 36(1): 1-26.
[7]	陈德峻, 方子豪, 曾云秀, 许凯. 战场迷雾中的欺骗路径规划[J]. 系统仿真学报, 2023, 35(9): 1895-1908.
[8]	李文静, 骆岩林, 王玉辉, 朱丽. 基于八叉树势场的鼻内镜虚拟导航路径规划[J]. 系统仿真学报, 2023, 35(9): 2054-2063.
[9]	林俊强, 王红军, 邹湘军, 张坡, 李承恩, 周益鹏, 姚书杰. 基于DPPO的移动采摘机器人避障路径规划及仿真[J]. 系统仿真学报, 2023, 35(8): 1692-1704.
[10]	杨来义, 毕敬, 苑海涛. 基于SAC算法的移动机器人智能路径规划[J]. 系统仿真学报, 2023, 35(8): 1726-1736.
[11]	曹梦龙, 赵文彬, 陈志强. 融合粒子群算法与改进灰狼算法的机器人路径规划[J]. 系统仿真学报, 2023, 35(8): 1768-1775.
[12]	杨海兰, 祁永强, 吴保磊, 荣丹, 洪妙英, 王军. 动态环境下基于忆阻强化学习的移动机器人路径规划[J]. 系统仿真学报, 2023, 35(7): 1619-1633.
[13]	宋大雷, 干文浩, 许嘤枝, 曲秀青, 曹江丽. 无人船实时路径规划与编队控制仿真研究[J]. 系统仿真学报, 2023, 35(5): 957-970.
[14]	吴玉文, 牛智越, 李珍萍. 基于改进遗传算法的货箱机器人拣选路径规划[J]. 系统仿真学报, 2023, 35(5): 1086-1097.
[15]	薛均晓, 孔祥燕, 董博威, 陶浩, 管海洋, 石磊, 徐明亮. 航母甲板上舰载机的混合避障和仿真[J]. 系统仿真学报, 2023, 35(3): 592-603.