改进双向快速搜索随机树的无人艇路径规划

doi:10.12305/j.issn.1001-506X.2024.04.25

Abstract

Abstract:

Aiming at the problems of bi-directional rapidly-exploring random tree (BI-RRT) algorithm in global path planning, such as low search efficiency and many turning points, an improved BI-RRT algorithm for global path planning of unmanned surface vehicle (USV) is proposed. The proposed algorithm adopts the idea of extreme greed, a Gaussian biased random point sampling method and a heuristic node expansion strategy. The node expansion and search tree connection are also angularly constrained, and the generated paths are cut and optimized with three B-samples. The results show that the improved BI-RRT reduces the average time, random sampling points, and average path by 40.5%, 65.0%, and 24.0%, respectively, compared to the previous BI-RRT. The improved algorithm has a significant reduction in time consumption, sampling points and search tree expansion, with improved path smoothing and shorter paths.

Key words: path planning, unmanned surface vehicles (USV), bi-directional rapidly-exploring random tree (BI-RRT), Gaussian biased random points, angular constraints

CLC Number:

U675.73

Guixiang ZHAO, Jian ZHOU, Yunmiao LI, Chenxu WANG. Improved bi-directional rapidly-exploring random tree path planning for USV[J]. Systems Engineering and Electronics, 2024, 46(4): 1364-1371.

Figures/Tables 12

Fig.1

Fig.2

Fig.3

Fig.4

Fig.5

Fig.6

Fig.7

Fig.8

Fig.9

Table 1

Fig.10

Table 2

References 22

1	YIN L L , ZHANG R B , GU H W , et al. Research on cooperative perception of MUSVs in complex ocean conditions[J]. Sensors, 2021, 21 (5): 1657. doi: 10.3390/s21051657
2	HAN S , WANG L , WANG Y T , et al. An efficient motion planning based on grid map: predicted trajectory approach with global path guiding[J]. Ocean Engineering, 2021, 238, 109696. doi: 10.1016/j.oceaneng.2021.109696
3	WANG J , WANG R T , LU D H , et al. USV dynamic accurate obstacle avoidance based on improved velocity obstacle method[J]. Electronics, 2022, 11 (17): 2720. doi: 10.3390/electronics11172720
4	WU M Y , ZHANG A M , GAO M , et al. Ship motion planning for MASS based on a multi-objective optimization HA * algorithm in complex navigation conditions[J]. Journal of Marine Science and Engineering, 2021, 9 (10): 1126. doi: 10.3390/jmse9101126
5	PARK J A , KIM S A , NOH G A , et al. Mission planning and performance verification of an unmanned surface vehicle using a genetic algorithm[J]. International Journal of Naval Architecture and Ocean Engineering, 2021, 13, 575- 584. doi: 10.1016/j.ijnaoe.2021.07.002
6	GUO X H , JI M J , ZHAO Z W , et al. Global path planning and multi-objective path control for unmanned surface vehicle based on modified particle swarm optimization (PSO) algorithm[J]. Ocean Engineering, 2020, 216 (1): 107693.
7	程谦, 高嵩, 曹凯, 等. 基于PRM优化算法的移动机器人路径规划[J]. 计算机应用与软件, 2020, 37 (12): 254-259, 296. doi: 10.3969/j.issn.1000-386x.2020.12.040
	CHENG Q , GAO S , CAO K , et al. Path planning of mobile robot based on PRM optimization algotithm[J]. Computer Applications and Software, 2020, 37 (12): 254-259, 296. doi: 10.3969/j.issn.1000-386x.2020.12.040
8	WANG W , ZUO L , XU X . A learning-based multi-RRT approach for robot path planning in narrow passages[J]. Journal of Intelligent & Robotic Systems, 2018, 90 (1): 81- 100.
9	JEOONG I B , LEE S J , KIM J H . Quick-RRTA * : triangular inequality-based implementation of RRT * with improved initial solution and convergence rate[J]. Expert Systems with Applications, 2019, 123, 82- 90. doi: 10.1016/j.eswa.2019.01.032
10	高升, 艾剑良, 王之豪. 混合种群RRT无人机航迹规划方法[J]. 系统工程与电子技术, 2020, 42 (1): 101- 107.
	GAO S , AI J L , WANG Z H . Mixed population RRT algorithm for UAV path pianning[J]. Systems Engineering and Electronics, 2020, 42 (1): 101- 107.
11	LAVALLE S M , KUFFNER J J . Rapidly-exploring random trees: progress and prospects[J]. Algorithmic & Computational Robotics New Directions, 2001, 5, 303- 307.
12	XIN P , WANG X M , LIU X L , et al. Improved bidirectional RRT * algorithm for robot path planning[J]. Sensors, 2023, 23 (2): 1041. doi: 10.3390/s23021041
13	文龙贻彬, 刘友, 穆京京, 等. 无人艇航行规则及运动学约束下的改进RRT轨迹规划方法[J]. 导航与控制, 2020, 19 (1): 105-115, 124. doi: 10.3969/j.issn.1674-5558.2020.01.012
	WENGLONG Y B , LIU Y , MU J J , et al. Improved RRT trajectory planning methed under unmanned surface vehicle rules and kinematic constraints[J]. Navigation and Control, 2020, 19 (1): 105-115, 124. doi: 10.3969/j.issn.1674-5558.2020.01.012
14	向金林, 王鸿东, 欧阳子路, 等. 基于改进双向RRT的无人艇局部路径规划算法研究[J]. 中国造船, 2020, 61 (1): 157- 166. doi: 10.3969/j.issn.1000-4882.2020.01.016
	XIANG J L , WANG H D , OUYANG Z L , et al. Algorithm of local path planning for unmanned surface vehicles based on improved Bi-RRT[J]. Shipbuilding of China, 2020, 61 (1): 157- 166. doi: 10.3969/j.issn.1000-4882.2020.01.016
15	徐秉超, 严华. 一种改进的双向快速搜索随机树算法[J]. 科学技术与工程, 2020, 20 (19): 7765- 7771.
	XU B C , YAN H . An improved bidirectional rapid-exploring random tree algorithm[J]. Science Technology and Engineering, 2020, 20 (19): 7765- 7771.
16	MA G J , DUAN Y L , LI M E , et al. A probability smoothing Bi-RRT path planning algorithm for indoor robot[J]. Future Generation Computer Systems, 2023, 143, 349- 360. doi: 10.1016/j.future.2023.02.004
17	MASEKO B B , VAN DAALEN C E , TREURNICHT J . Optimised informed RRTs for mobile robot path planning[J]. IFAC-PapersOnLine, 2021, 54 (21): 157- 162. doi: 10.1016/j.ifacol.2021.12.027
18	KARAMAN S , FRAZZOLI E . Sampling-based algorithms for optimal motion planning[J]. The International Journal of Robotics Research, 2011, 30 (7): 846- 894. doi: 10.1177/0278364911406761
19	QURESHI A H , AYAZ Y . Potential functions based sampling heuristic for optimal path planning[J]. Autonomous Robots, 2016, 40 (6): 1079- 1093. doi: 10.1007/s10514-015-9518-0
20	AKGUN B, STILMAN M. Sampling heuristics for optimal motion planning in high dimensions[C]//Proc. of the IEEE/RSJ International Conference on Intelligent Robots and Systems, 2011: 2640-2645.
21	QURESHI A H , AYAZ Y . Intelligent bidirectional rapidly-exploring random trees for optimal motion planning in complex cluttered environments[J]. Robotics and Autonomous Systems, 2015, 68, 1- 11. doi: 10.1016/j.robot.2015.02.007
22	LIU H Y , ZHANG X B , WEN J , et al. Goal-biased bidirectional RRT based on curve-smoothing[J]. IFAC-PapersOnLine, 2019, 52 (24): 255- 260. doi: 10.1016/j.ifacol.2019.12.417

参数	BI-RRT	BI-RRTstar	IB-RRTstar	改进BI-RRT
平均时间/s	0.44	2.17	1.72	0.28
平均采样点数/个	83	1 500	1 500	38
平均拐点数/个	30	18	6	0
平均路径长度/m	898.60	642.54	637.70	640.45

参数	BI-RRT	BI-RRTstar	IB-RRTstar	改进BI-RRT
平均时间/s	0.43	0.72	0.97	0.24
平均采样点数/个	370	1 500	1 500	88
平均拐点数/个	55	19	13	0
平均路径长度/m	1 054.50	860.90	847.41	850.21

[1]	Gang LIU, Zhibiao AN, Maojun ZHANG, Yu LIU, Wu LI. Subject objective path planning algorithm based on continuous road network environment [J]. Systems Engineering and Electronics, 2024, 46(4): 1346-1356.
[2]	Zihao CHEN, Juan LI, Chang LIU, Jie LI, Xiaoyu LIU. Task planning method for coordinated attacks on ground targets under time constraints [J]. Systems Engineering and Electronics, 2023, 45(8): 2353-2360.
[3]	Guangqiang LI, Wenchao DONG, Daqing ZHU, Yue YU, Hao CHEN, Shuanghe YU. 3D path planning for AUV based on improved whaleoptimization algorithm [J]. Systems Engineering and Electronics, 2023, 45(7): 2170-2182.
[4]	Liyao WU, Xichao SU, Lei WANG, Zishuang PAN. Research of formation rendezvous control for manned/unmanned aerial vehicles formation [J]. Systems Engineering and Electronics, 2023, 45(7): 2192-2202.
[5]	Yao LIU, Yangsheng XIA, Jianmai SHI, Chao CHEN, Jincai HUANG. Path planning method for multi-area coverage by cooperated ground vehicle multi-drone [J]. Systems Engineering and Electronics, 2023, 45(5): 1380-1390.
[6]	Qinglu WANG, Fengguo WU, Chengchen ZHENG, Hui LI. UAV path planning based on optimized artificial potential field method [J]. Systems Engineering and Electronics, 2023, 45(5): 1461-1468.
[7]	Wei HAN, Zixuan LIU, Xichao SU, Kaikai CUI, Jie LIU. Deck path planning algorithm of carrier-based aircraft based on heuristic and optimal control [J]. Systems Engineering and Electronics, 2023, 45(4): 1098-1110.
[8]	Haojie ZHANG, Yudong ZHANG, Rongmin LIANG, Tiantian YANG. Energy-efficient path planning method for robots based on improved A^* algorithm [J]. Systems Engineering and Electronics, 2023, 45(2): 513-520.
[9]	Jingyu WU, Shiqiang ZHU, Wei SONG, Haolei SHI, Zenan WU. Coverage path planning based on improved cellular decomposition [J]. Systems Engineering and Electronics, 2023, 45(12): 3949-3957.
[10]	Guixiang ZHAO, Chenxu WANG, Heping WANG, Yunmiao LI. Local path planning for unmanned surface vehicle using improved velocity obstacle method [J]. Systems Engineering and Electronics, 2023, 45(12): 3975-3983.
[11]	Zhi REN, Dong ZHANG, Shuo TANG. Improved three-dimensional A^* algorithm of real-time path planning based on reinforcement learning [J]. Systems Engineering and Electronics, 2023, 45(1): 193-201.
[12]	Haobo FENG, Qiao HU, Zhenyi ZHAO. AUV swarm path planning based on elite family genetic algorithm [J]. Systems Engineering and Electronics, 2022, 44(7): 2251-2262.
[13]	Dou CHEN, Xiuyun MENG. UAV offline path planning based on self-adaptive coyote optimization algorithm [J]. Systems Engineering and Electronics, 2022, 44(2): 603-611.
[14]	Yang YIN, Quanshun YANG, Zheng WANG, Yang LIU. USV cluster coverage search method with communication distance constraint [J]. Systems Engineering and Electronics, 2022, 44(12): 3821-3828.
[15]	Qingqing YANG, Yingying GAO, Yu GUO, Boyuan XIA, Kewei YANG. Target search path planning for naval battle field based on deep reinforcement learning [J]. Systems Engineering and Electronics, 2022, 44(11): 3486-3495.

Improved bi-directional rapidly-exploring random tree path planning for USV

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 12

References 22

Related Articles 15

Recommended Articles

Metrics

Comments