Path Planning Rapid Algorithm Based on Modified RRT* for Unmanned Surface Vessel

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

Abstract

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

CLC Number:

TP391.9

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.

Figures/Tables 19

Fig. 1

Fig. 2

Fig. 3

Fig. 4

Fig. 5

Fig. 6

Fig. 7

Fig. 8

Fig. 9

Fig. 10

Table 1

Fig. 11

Fig. 12

Fig. 13

Fig. 14

Fig. 15

Table 2

Fig. 16

Table 3

References 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]	Zhang Rui, Zhou Li, Liu Zhengyang. Dynamic Path Planning for Mobile Robot Based on RRT* and Dynamic Window Approach [J]. Journal of System Simulation, 2024, 36(4): 957-968.
[2]	Li Gaoyang, Li Xiangfeng, Zhao Kang, Jin Yuchao, Yi Zhidong, Zuo Dunwen. Three-Dimensional Path Planning of UAV Based on All Particles Driving Wild Horse Optimizer Algorithm [J]. Journal of System Simulation, 2024, 36(3): 595-607.
[3]	Yu Xiang, Jiang Chen, Duan Sirui, Deng Qianrui. Path Planning for Improvement of A* Algorithm and Artificial Potential Field Method [J]. Journal of System Simulation, 2024, 36(3): 782-794.
[4]	Tang Yunchao, Qi Shaojun, Zhu Lixue, Zhuo Xianrong, Zhang Yunqi, Meng Fan. Obstacle Avoidance Motion in Mobile Robotics [J]. Journal of System Simulation, 2024, 36(1): 1-26.
[5]	Chen Dejun, Fang Zihao, Zeng Yunxiu, Xu Kai. Deceptive Path Planning in Fog of War [J]. Journal of System Simulation, 2023, 35(9): 1895-1908.
[6]	Li Wenjing, Luo Yanlin, Wang Yuhui, Zhu Li. Virtual Navigation Path Planning Based on Octree Potential Field for Endonasal Endoscope [J]. Journal of System Simulation, 2023, 35(9): 2054-2063.
[7]	Junqiang Lin, Hongjun Wang, Xiangjun Zou, Po Zhang, Chengen Li, Yipeng Zhou, Shujie Yao. Obstacle Avoidance Path Planning and Simulation of Mobile Picking Robot Based on DPPO [J]. Journal of System Simulation, 2023, 35(8): 1692-1704.
[8]	Laiyi Yang, Jing Bi, Haitao Yuan. Intelligent Path Planning for Mobile Robots Based on SAC Algorithm [J]. Journal of System Simulation, 2023, 35(8): 1726-1736.
[9]	Menglong Cao, Wenbin Zhao, Zhiqiang Chen. Robot Path Planning by Fusing Particle Swarm Algorithm and Improved Grey Wolf Algorithm [J]. Journal of System Simulation, 2023, 35(8): 1768-1775.
[10]	Hailan Yang, Yongqiang Qi, Baolei Wu, Dan Rong, Miaoying Hong, Jun Wang. Path Planning of Mobile Robots Based on Memristor Reinforcement Learning in Dynamic Environment [J]. Journal of System Simulation, 2023, 35(7): 1619-1633.
[11]	Dalei Song, Wenhao Gan, Yingzhi Xu, Xiuqing Qu, Jiangli Cao. Simulation of Real-Time Path Planning and Formation Control for Unmanned Surface Vessel [J]. Journal of System Simulation, 2023, 35(5): 957-970.
[12]	Yuwen Wu, Zhiyue Niu, Zhenping Li. Picking Path Planning of Container Robots Based on Improved Genetic Algorithm [J]. Journal of System Simulation, 2023, 35(5): 1086-1097.
[13]	Junxiao Xue, Xiangyan Kong, Bowei Dong, Hao Tao, Haiyang Guan, Lei Shi, Mingliang Xu. Obstacle Avoidance and Simulation of Carrier-Based Aircraft on the Deck of Aircraft Carrier [J]. Journal of System Simulation, 2023, 35(3): 592-603.
[14]	Guohui Zhang, Xuan Wang, Yanan Zhang, Ang Gao. Research on Cooperative Path Planning Model of Multiple Unmanned Vehicles in Real Environment [J]. Journal of System Simulation, 2023, 35(2): 408-422.
[15]	Yang Qingqing, Deng Minyi, Peng Yi. Urban UAV Path Planning Based on Improved Beetle Search Algorithm [J]. Journal of System Simulation, 2023, 35(12): 2527-2536.