基于CB-RRT*算法的滩涂履带车路径规划

doi:10.12382/bgxb.2022.1089

摘要/Abstract

摘要：

针对滩涂履带车在受潮汐影响的滩涂环境中进行长时间勘测作业的需求,提出柯西贝塞尔快速搜索随机树星(Cauchy Bessel Rapidly-exploring Random Tree Star,CB-RRT^*)算法进行路径规划。为规划出安全路径,基于全局地图和潮汐数据,并通过滩涂履带车到分界区的距离构建出滩涂预测模型;为提高滩涂履带车移动到目标点需进行多次路径规划的速度,对初始路径的关键树节点使用柯西概率密度函数进行采样缩小采样范围来提高节点的利用率,进而提高算法的收敛性;在重选父节点过程中考虑最大转角约束设定相应系数,并使用连续二次贝塞尔曲线进行拼接的方式来生成路径,达到提高路径平滑度的目的和解决平滑后路径与原路径偏差过大造成的安全性问题。仿真实验结果表明,CB-RRT^*算法在静态滩涂环境和动态滩涂环境中,能大大提高算法的收敛性和路径的平滑性,且保证路径长度最优,研究内容可以保证滩涂履带车在各种滩涂环境中进行长时间安全作业。

关键词: 滩涂履带车, 路径规划, 柯西概率密度函数, 最大转角约束, 贝塞尔曲线

Abstract:

Cauchy Bessel rapidly-exploring random tree star (CB-RRT^*) algorithm is proposed for the path planning of tracked vehicle for long-term surveying operations in tidal flat environments. In order to plan a safe path, a tidal flat prediction model is constructed based on the global map. The tidal data and the distance from the tidal flat tracked vehicle to the demarcation area. Using the Cauchy probability density function to sample the key tree nodes of the initial path can reduce the sampling range and improve the utilization of nodes, which increases the speed of multiple path planning of tidal flat tracked vehicle moving to a target point. Considering the maximum corner constraint to set the corresponding coefficient in the process of reselecting the parent node and using the continuous quadratic Bezier curve to splicing to generate a path, the smoothness of the path can be improved and the safety problem caused by the excessive deviation between the smoothed path and the original path can be also solved. The simulated results show that CB-RRT^* algorithm can greatly improve the convergence of the algorithm and the smoothness of the path in the static and dynamic tidal flat environments, and ensures the optimal path length. The proposed method can ensure the long-term safe operation of tidal flat tracked vehicle in various tidal flat environments.

Key words: tidal flat tracked vehicle, path planning, Cauchy probability density function, maximum corner constraint, Bezier curve

中图分类号:

TP242

潘作栋, 周悦, 郭威, 徐高飞, 孙宇. 基于CB-RRT^*算法的滩涂履带车路径规划[J]. 兵工学报, 2024, 45(4): 1117-1128.

PAN Zuodong, ZHOU Yue, GUO Wei, XU Gaofei, SUN Yu. Path Planning of Tidal Flat Tracked Vehicle Based on CB-RRT^* Algorithm[J]. Acta Armamentarii, 2024, 45(4): 1117-1128.

图/表 22

图1 潮汐数据

Fig.1 Tidal data

图2 滩涂预测模型

Fig.2 Tidal flat prediction model

图3 CB-RRT*算法流程图

Fig.3 CB-RRT* algorithm flowchart

图4 柯西概率密度函数采样

Fig.4 Cauchy probability density function sampling

图5 节点角度对应

Fig.5 Node angle correspondence

图6 设置新节点的父节点

Fig.6 Setting the parent node of new node

图7 代价函数值

Fig.7 Cost function value

图8 更新父节点

Fig.8 Update parent node

图9 重布线

Fig.9 Rewiring

图10 局部路径模型图

Fig.10 Local path model

图11 贝塞尔曲线拟合路径

Fig.11 Bezier curve fitting path

图12 最大转角参数实验结果

Fig.12 Experimental results of maximum rotation angle parameter

图13 稠密障碍物环境实验结果

Fig.13 Experimental results of dense obstacle environment

表1 稠密障碍物环境中4种算法性能对比

Table 1 Performance comparison of four algorithms in dense obstacle environment

算法	路径长度/m	时间/s	曲率
RRT^*	56.73	58.34	0.215
Informed RRT^*	55.23	55.02	0.127
Quick-RRT^*	55.16	59.80	0.139
CB-RRT^*	54.80	56.51	0.024

图14 唯一通道环境中实验结果

Fig.14 Experimental results in a single-channel environment

表2 唯一通道环境中4种算法性能对比

Table 2 Performance comparison of four algorithms in a unique channel environment

算法	路径长度/m	时间/s	曲率
RRT^*	59.13	39.38	0.149
Informed RRT^*	61.27	37.89	0.274
Quick-RRT^*	59.22	38.86	0.116
CB-RRT^*	58.23	33.76	0.037

图15 U形障碍物环境中实验结果

Fig.15 Experimental results in U-shaped obstacle environment

表3 U形障碍物环境中4种算法性能对比

Tab.3 Performance comparison of four algorithms in U-shaped obstacle environment

算法	路径长度/m	时间/s	曲率
RRT^*	53.63	76.48	0.230
Informed RRT^*	55.06	69.67	0.272
Quick-RRT^*	52.54	72.75	0.174
CB-RRT^*	52.10	71.32	0.057

图16 动态滩涂环境

Fig.16 Dynamic tidal flat environment

表4 动态滩涂环境中4中算法性能对比

Table 4 Performance comparison of four algorithms in dynamic tidal flat environment

算法	路径规划序号	长度/m	时间/s	曲率
RRT^*	1	4229.61	96.71	0.105
	2	1541.34	59.60	0.114
Informed RRT^*	1	4474.95	90.36	0.179
	2	1736.04	64.28	0.137
Quick-RRT^*	1	4297.38	98.47	0.162
	2	1640.25	63.91	0.130
CB-RRT^*	1	4154.26	82.04	0.047
	2	1534.79	37.44	0.037

图17 滩涂环境下4种算法的路径规划结果

Fig.17 Path planning results of four algorithms in tidal flat environment

图18 滩涂环境路径规划结果

Fig.18 Result of tidal flat environment path planning

参考文献 21

[1]	TADDIA Y, PELLEGRINELLI A, CORBAU C, et al. High-resolution monitoring of tidal systems using UAV: a case study on Poplar Island, MD (USA)[J]. Remote Sensing, 2021, 13(7): 1364.
[2]	LI J Y, YAO X, JIE J, et al. Remote sensing method for extracting topographic information on tidal flats using spatial distribution features[J]. Marine Geodesy, 2021, 44(5): 408-431.
[3]	FLORES-DE-SANTIAGO F, VALDERRAMA-LANDEROS L, RODRíGUEZ-SOBREYRA R, et al. Assessing the effect of flight altitude and overlap on orthoimage generation for UAV estimates of coastal wetlands[J]. Journal of Coastal Conservation, 2020, 24(3): 35.
[4]	李东方, 王超, 邓宏彬, 等. 基于人工势场和RRT算法的机器蛇水下三维避障算法[J]. 兵工学报, 2017, 38(增刊1): 205-214.
	LI D F, WANG C, DENG H B, et al. Underwater 3D obstacle avoidance algorithm for robotic snakes based on artificial potential field and RRT algorithm[J]. Acta Armamentarii, 2017, 38(S1): 205-214. (in Chinese)
[5]	KARAMAN S, FRAZZOLI E. Incremental sampling-based algorithms for optimal motion planning[J]. Proceedings of Robotics Science and Systems VI. Zaragoza, Spain: Robotics:Science and Systems Foundation, 2010.
[6]	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]// Proceedings of the 2014 IEEE/RSJ International Conference on Intelligent Robots and Systems.Chicago, IL, US:IEEE/RSJ, 2014:14-18.
[7]	JEONG I B, LEE S J, KIM J H. Quick-RRT^: triangular inequality-based implementation of RRT^ with improved initial solution and convergence rate[J]. Expert Systems with Applications, 2019, 123: 82-90.
[8]	徐唐进, 张安民, 高邈, 等. 动态水深环境下的无人艇路径规划[J]. 测绘科学, 2021, 46(6): 180-189.
	XU T J, ZHANG A M, GAO M, et al. Path planning of unmanned vehicles in dynamic water depth environment[J]. Science of Surveying and Mapping, 2021, 46(6): 180-189. (in Chinese)
[9]	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.
[10]	WANG X W, WEI J B, ZHOU X, et al. AEB-RRT^: an adaptive extension bidirectional RRT^ algorithm[J]. Autonomous Robots, 2022, 46(6): 685-704.
[11]	陈秋莲, 蒋环宇, 郑以君. 机器人路径规划的快速扩展随机树算法综述[J]. 计算机工程与应用, 2019, 55(16): 10-17. doi: 10.3778/j.issn.1002-8331.1905-0061
	CHEN Q L, JIANG H Y, ZHENG Y J. A survey of fast extended random tree algorithms for robot path planning[J]. Computer Engineering and Applications, 2019, 55(16): 10-17. (in Chinese)
[12]	SATHIYA V, CHINNADURAI M, RAMABALAN S. Mobile robot path planning using fuzzy enhanced improved Multi-Objective particle swarm optimization (FIMOPSO)[J]. Expert Systems with Applications, 2022, 198: 116875.
[13]	HICHRI B, GALLALA A, GIOVANNINI F, et al. Mobile robots path planning and mobile multirobots control: a review[J]. Robotica, 2022, 40(12): 4257-4270.
[14]	张卫波, 肖继亮. 改进RRT算法在复杂环境下智能车路径规划中的应用[J]. 中国公路学报, 2021, 34(3): 225-234. doi: 10.19721/j.cnki.1001-7372.2021.03.017
	ZHANG W B, XIAO J L. Application of improved RRT algorithm in path planning of intelligent vehicles in complex environment[J]. Journal of China Highway Society, 2021, 34(3): 225-234. (in Chinese)
[15]	邓海鹏, 麻斌, 赵海光, 等. 自主驾驶车辆紧急避障的路径规划与轨迹跟踪控制[J]. 兵工学报, 2020, 41(3): 585-594. doi: 10.3969/j.issn.1000-1093.2020.03.020
	DENG H P, MA B, ZHAO H G, et al. Path planning and tracking control for autonomous vehicle for obstacle avoidance[J]. Acta Armamentarii, 2020, 41(3): 585-594. (in Chinese)
[16]	ŞOMÎTCǍ I-A, BRAD S, FLORIAN V, et al. Improving path accuracy of mobile robots in uncertain environments by adapted Bézier curves[J]. Electronics, 2022, 11(21): 3568.
[17]	徐岩, 崔媛媛. 基于Q-IGA动态拟合贝塞尔曲线的路径规划[J]. 湖南大学学报(自然科学版), 2020, 47(10): 68-75.
	XU Y, CUI Y Y. Path planning based on Q-IGA dynamic fitting Bezier curve[J]. Journal of Hunan University (Natural Science Edition), 2020, 47(10): 68-75. (in Chinese)
[18]	谭建豪, 潘豹, 王耀南, 等. 基于改进RRT^*FN算法的机器人路径规划[J]. 控制与决策, 2021, 36(8): 1834-1840.
	TAN J H, PAN B, WANG Y N, et al. Robot path planning based on improved RRT^*FN algorithm[J]. Control and Decision Making, 2021, 36(8): 1834-1840. (in Chinese)
[19]	WANG Z, LIANG Y, GONG C, et al. Improved dynamic window approach for unmanned surface vehicles' local path planning considering the impact of environmental factors[J]. Sensors, 2022, 22(14): 5181.
[20]	MIED R P, CHEN W, SMITH G B, et al. Airborne remote sensing of surface velocities in a tidal river[J]. IEEE Transactions on Geoscience and Remote Sensing, 2018, 56(8): 4559-67.
[21]	ZHANG J, MA X J, YUAN D, et al. Steering control of dual electric drive tracked vehicle based on model predictive control[J]. IOP Conference Series: Materials Science and Engineering, 2020, 782(3):032002.