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

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

摘要/Abstract

摘要：

针对双向快速搜索随机树(bidirectional rapidly-exploring random tree, BI-RRT)算法在全局路径规划时存在搜索效率低、路径拐点较多等问题, 提出一种改进BI-RRT的水面无人艇(unmanned surface vehicle, USV)全局路径规划算法。该算法采取了极度贪心的思想、高斯偏置随机点采样方法以及启发式的节点扩展策略, 同时对节点扩展和搜索树连接进行角度约束, 将生成的路径进行剪枝和3次B样条优化处理。结果表明, 相对于改进前, 改进的BI-RRT在平均时间、随机采样点和平均路径上分别减少了40.5%、65.0%和24.0%。改进后的算法时间、采样点和搜索树扩展大幅度减少, 路径平滑度提高且路径更短。

关键词: 路径规划, 水面无人艇, 双向快速搜索随机树, 高斯偏置随机点, 角度约束

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

中图分类号:

U675.73

赵贵祥, 周健, 李云淼, 王晨旭. 改进双向快速搜索随机树的无人艇路径规划[J]. 系统工程与电子技术, 2024, 46(4): 1364-1371.

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.

图/表 12

图1

图2

图3

图4

图5

图6

图7

图8

图9

表1

图10

表2

参考文献 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]	刘钢, 安志镖, 张茂军, 刘煜, 李武. 基于连续路网环境的实体化主体路径规划算法[J]. 系统工程与电子技术, 2024, 46(4): 1346-1356.
[2]	赵贵祥, 王晨旭, 周健, 李云淼. 基于改进模糊评价法的无人艇碰撞风险计算[J]. 系统工程与电子技术, 2024, 46(3): 1031-1037.
[3]	李广强, 董文超, 朱大庆, 于越, 陈浩, 于双和. 基于改进鲸鱼优化算法的AUV三维路径规划[J]. 系统工程与电子技术, 2023, 45(7): 2170-2182.
[4]	刘瑶, 夏阳升, 石建迈, 陈超, 黄金才. 车载多无人机协同多区域覆盖路径规划方法[J]. 系统工程与电子技术, 2023, 45(5): 1380-1390.
[5]	韩维, 刘子玄, 苏析超, 崔凯凯, 刘洁. 结合启发式与最优控制的舰载机甲板路径规划算法[J]. 系统工程与电子技术, 2023, 45(4): 1098-1110.
[6]	张浩杰, 张玉东, 梁荣敏, 杨甜甜. 改进A^*算法的机器人能耗最优路径规划方法[J]. 系统工程与电子技术, 2023, 45(2): 513-520.
[7]	吴靖宇, 朱世强, 宋伟, 施浩磊, 吴泽南. 基于改进单元分解法的全覆盖路径规划[J]. 系统工程与电子技术, 2023, 45(12): 3949-3957.
[8]	赵贵祥, 王晨旭, 王贺平, 李云淼. 改进速度障碍法的无人艇局部路径规划[J]. 系统工程与电子技术, 2023, 45(12): 3975-3983.
[9]	周梦平, 孟秀云, 刘俊辉. 大落角机动目标逆轨拦截最优滑模制导律设计[J]. 系统工程与电子技术, 2022, 44(9): 2886-2893.
[10]	冯豪博, 胡桥, 赵振轶. 基于精英族系遗传算法的AUV集群路径规划[J]. 系统工程与电子技术, 2022, 44(7): 2251-2262.
[11]	尹洋, 杨全顺, 王征, 刘洋. 通信距离约束下的无人船集群覆盖搜索方法[J]. 系统工程与电子技术, 2022, 44(12): 3821-3828.
[12]	杨清清, 高盈盈, 郭玙, 夏博远, 杨克巍. 基于深度强化学习的海战场目标搜寻路径规划[J]. 系统工程与电子技术, 2022, 44(11): 3486-3495.
[13]	马威强, 高永琪, 赵苗. 基于全局最优和差分变异的头脑风暴优化算法[J]. 系统工程与电子技术, 2022, 44(1): 270-278.
[14]	焦志强, 张杰勇, 姚佩阳, 王勋, 何宜超. 基于分层结构的C4ISR服务部署分布式演化方法[J]. 系统工程与电子技术, 2021, 43(6): 1572-1585.
[15]	郭佳晖, 蒋滨安, 田宗浩. 带有攻击角和视场角约束的制导炮弹导引律设计[J]. 系统工程与电子技术, 2021, 43(4): 1050-1056.