融合时空散列的三维RRT*多编队航路规划

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

摘要/Abstract

摘要：

针对多编队时空路径生成研究的空白, 提出一种融合时空散列思想的无人机多编队航路规划方法。引入第3代安全散列算法对航路点时空信息进行散列计算和线性映射, 得到时空航路点和编队飞行区域。使用时空点面信息优化有偏采样, 解决多编队采样集中和无效路径过深问题。设计基于航路点偏置和时空平滑优化的三维增强型快速扩展随机树多编队航路规划算法, 以时空差异航路点为偏置目标, 结合人工势场法与时空约束条件优化节点搜索成本函数, 得到时空最佳差异路径。结果表明, 所提方法在规划用时和节点数上分别减少了53.33%和17.53%, 多编队路径数据验证了该方法具备时空差异生成能力。

关键词: 时空散列思想, 无人机多编队航路规划, 散列计算, 增强型快速扩展随机树, 时空约束域

Abstract:

Addressing the research gap in spatio-temporal path generation for multi-formation, a multi-unmanned aerial vehicle(UAV) formation route planning method is proposed integrating spatio-temporal hash concept. The third-generation secure hash algorithm is employed to process spatio-temporal waypoint information through hash computation and linear mapping, deriving spatio-temporal navigation points and formation flight regions. The methodology optimizes biased sampling using spatio-temporal point-surface information, effectively resolving issues of sampling concentration and excessive invalid path depth in multi-formation. A three-dimensional enhanced fastly-exploring random tree multi formation route planning algorithm based on waypoint offset and spatio-temporal smooth optimization is designed, with spatio-temporal difference waypoints as the offset target. By integrating artificial potential field methods with spatio-temporal constraints to optimize the node search cost function, the algorithm achieves spatio-temporally optimal differentiated paths. Experimental results demonstrate that the proposed method reduces planning time and node count by 53.33% and 17.53% respectively, with multi-formation path data verifying its spatio-temporal differentiation capability.

Key words: spatio-temporal hash concept, multi-unmanned aerial vehicle(UAV) formation route planning, hash computation, enhanced rapidly-exploring random tree (RRT), spatio-temporal constraint domain

中图分类号:

TP273

郑凯文, 杜承泽, 赵兴芳, 逄晓凡. 融合时空散列的三维RRT^*多编队航路规划[J]. 系统工程与电子技术, 2025, 47(7): 2256-2266.

Kaiwen ZHENG, Chengze DU, Xingfang ZHAO, Xiaofan PANG. Integrating spatio-temporal hash in three-dimensional RRT^* multi-formation route planning[J]. Systems Engineering and Electronics, 2025, 47(7): 2256-2266.

图/表 21

图1

图2

图3

图4

图5

图6

图7

图8

图9

图10

图11

图12

表1

图13

图14

表2

表3

表4

图15

表5

图16

参考文献 35

1	MOHSAN S A H , OTHMAN N Q H , LI Y , et al. Unmanned aerial vehicles (UAVs): practical aspects, applications, open challenges, security issues, and future trends[J]. Intelligent Service Robotics, 2023, 16 (1): 109- 137.
2	JAVED S , HASSAN A , AHMAD R , et al. State-of-the-art and future research challenges in UAV swarms[J]. IEEE Internet of Things Journal, 2024, 11 (11): 19023- 19045.
3	董国强. 无人机——现代战争中的新锐力量[J]. 农村青少年科学探究, 2024 (1): 4- 6.
	DONG G Q . Unmanned aerial vehicles—a cutting-edge force in modern warfare[J]. Scientific Inquiry for Rural Youth, 2024 (1): 4- 6.
4	PUENTE-CASTRO A , RIVERO D , PAZOS A , et al. A review of artificial intelligence applied to path planning in UAV swarms[J]. Neural Computing and Applications, 2022, 34 (1): 153- 170.
5	杨思明, 单征, 曹江, 等. 基于模型的强化学习在无人机路径规划中的应用[J]. 计算机工程, 2022, 48 (12): 255-260, 269.
	YANG S M , SHAN Z , CAO J , et al. Application of model-based reinforcement learning in path planning of unmanned aerial vehicle[J]. Computer Engineering, 2022, 48 (12): 255-260, 269.
6	杨清清, 高盈盈, 郭玙, 等. 基于深度强化学习的海战场目标搜寻路径规划[J]. 系统工程与电子技术, 2022, 44 (11): 3486- 3495. doi: 10.12305/j.issn.1001-506X.2022.11.24
	YANG Q Q , GAO Y Y , GUO Y , et al. Target search path planning for naval battle field based on deep reinforcement learning[J]. Systems Engineering and Electronics, 2022, 44 (11): 3486- 3495. doi: 10.12305/j.issn.1001-506X.2022.11.24
7	SHAKYA A K , PILLAI G , CHAKRABARTY S . Reinforcement learning algorithms: a brief survey[J]. Expert Systems with Applications, 2023, 231, 120495.
8	BAKIRCI M, OZER M M. Involvement of unmanned aerial vehicles and swarm intelligence in future modern warfare: an overview[C]//Proc. of the International Conference on Computing, Intelligence and Data Analytics, 2023: 58-67.
9	XU C , XU M , YIN C J . Optimized multi-UAV cooperative path planning under the complex confrontation environment[J]. Computer Communications, 2020, 162, 196- 203.
10	FUSIC S J , SITHARTHAN R . Improved RRT* algorithm-based path planning for unmanned aerial vehicle in a 3D metropolitan environment[J]. Unmanned Systems, 2024, 12 (5): 859- 875.
11	高升, 艾剑良, 王之豪. 混合种群RRT无人机航迹规划方法[J]. 系统工程与电子技术, 2020, 42 (1): 101- 107. doi: 10.3969/j.issn.1001-506X.2020.01.14
	GAO S , AI J L , WANG Z H . Mixed population RRT algorithm for UAV path planning[J]. Systems Engineering and Electronics, 2020, 42 (1): 101- 107. doi: 10.3969/j.issn.1001-506X.2020.01.14
12	MCCOURT M, TON C T, MEHTA S S, et al. Adaptive step-length RRT algorithm for improved coverage[C]//Proc. of the AIAA Guidance, Navigation, and Control Conference, 2016.
13	LEE H , LEE D , SHIM D H . Receding horizon-based RRT^* algorithm for a UAV real-time path planner[M]. Texas: Aircraft Industries Association of America, 2017.
14	杨小草, 都延丽, 步雨浓, 等. 基于层次分解的在线三维RRT^*协同航路规划[J]. 系统工程与电子技术, 2023, 45 (5): 1409- 1419. doi: 10.12305/j.issn.1001-506X.2023.05.17
	YANG X C , DU Y L , BU Y N , et al. Online three-dimensional RRT^* cooperative route planning based on hierarchical decomposition[J]. Systems Engineering and Electronics, 2023, 45 (5): 1409- 1419. doi: 10.12305/j.issn.1001-506X.2023.05.17
15	赵贵祥, 周健, 李云淼, 等. 改进双向快速搜索随机树的无人艇路径规划[J]. 系统工程与电子技术, 2024, 46 (4): 1364- 1371. doi: 10.12305/j.issn.1001-506X.2024.04.25
	ZHAO G X , ZHOU J , LI Y M , et al. Improved bi-directional rapidly-exploring random tree path planning for USV[J]. Systems Engineering and Electronics, 2024, 46 (4): 1364- 1371. doi: 10.12305/j.issn.1001-506X.2024.04.25
16	李广强, 董文超, 朱大庆, 等. 基于改进鲸鱼优化算法的AUV三维路径规划[J]. 系统工程与电子技术, 2023, 45 (7): 2170- 2182. doi: 10.12305/j.issn.1001-506X.2023.07.28
	LI G Q , DONG W C , ZHU D Q , et al. 3D path planning for AUV based on improved whale optimization algorithm[J]. Systems Engineering and Electronics, 2023, 45 (7): 2170- 2182. doi: 10.12305/j.issn.1001-506X.2023.07.28
17	WANG J K , CHI W Z , LI C M , et al. Neural RRT*: learning-based optimal path planning[J]. IEEE Trans.on Automation Science and Engineering, 2020, 17 (4): 1748- 1758.
18	KIANI F , SEYYEDABBASI A , ALIYEV R , et al. Adapted-RRT: novel hybrid method to solve three-dimensional path planning problem using sampling and metaheuristic-based algorithms[J]. Neural Computing and Applications, 2021, 33 (22): 15569- 15599.
19	GANESAN S , RAMALINGAM B , MOHAN R E . A hybrid sampling-based RRT* path planning algorithm for autonomous mobile robot navigation[J]. Expert Systems with Applications, 2024, 258, 125206.
20	GU M Y, HUANG Y Z. Dynamic obstacle avoidance of mobile robot based on adaptive velocity obstacle[C]//Proc. of the 36th IEEE Youth Academic Annual Conference of Chinese Association of Automation, 2021: 776-781.
21	CHEN H Y , JI Y B , NIU L J . Reinforcement learning path planning algorithm based on obstacle area expansion strategy[J]. Intelligent Service Robotics, 2020, 13 (2): 289- 297.
22	WU Z Y , DONG S P , YUAN M , et al. Rotate artificial potential field algorithm toward 3D real-time path planning for unmanned aerial vehicle[J]. Proceedings of the Institution of Mechanical Engineers, Part G: Journal of Aerospace Engineering, 2023, 237 (4): 940- 955.
23	YANG X , WU F Y , LI R C , et al. Real-time path planning for obstacle avoidance in intelligent driving sightseeing cars using spatial perception[J]. Applied Sciences, 2023, 13 (20): 11183.
24	ALT H , GODAU M . Computing the Frechet distance between two polygonal curves[J]. International Journal of Computational Geometry & Applications, 1995, 5, 75- 91.
25	YADAV M , ALAM M A . Dynamic time warping (DTW) algorithm in speech: a review[J]. International Journal of Research in Electronics and Computer Engineering, 2018, 6 (1): 524- 528.
26	ALMEIDA J B, BARITEL-RUET C, BARBOSA M, et al. Machine-checked proofs for cryptographic standards: indiffe-rentiability of sponge and secure high-assurance implementations of SHA-3[C]//Proc. of the ACM SIGSAC Conference on Computer and Communications Security, 2019.
27	SANG H Q , YOU Y S , SUN X J , et al. The hybrid path planning algorithm based on improved A * and artificial potential field for unmanned surface vehicle formations[J]. Ocean Engineering, 2021, 223 (3): 108709.
28	SHIN J J , BANG H . UAV path planning under dynamic threats using an improved PSO algorithm[J]. International Journal of Aerospace Engineering, 2020, 2020 (1): 8820284.
29	MOKRANE A, BRAHAM A C, CHERLI B. UAV path planning based on dynamic programming algorithm on photogrammetric DEMs[C]//Proc. of the IEEE International Conference on Electrical Engineering, 2020.
30	SEIFU T K , WOLDESENBET T A , ALEMAYEHU T , et al. Spatio-temporal change of land use/land cover and vegetation using multi-MODIS satellite data, western ethiopia[J]. The Scientific World Journal, 2023, 2023 (1): 7454137.
31	MUSA A, ZANATTA L, BARCHI F, et al. A method for accelerated simulations of reinforcement learning tasks of UAVs in AirSim[C]//Proc. of the 14th International Conference on Advances in System Simulation, 2022: 46-53.
32	TAN W H, LAI W K, CHEN P H, et al. An improved NSGA-Ⅱ for UAV path planning[C]//Proc. of the International Conference on Neural Information Processing, 2023: 305-316.
33	PUENTE-CASTRO A , RIVERO D , PEDROSA E , et al. Q-learning based system for path planning with unmanned aerial vehicles swarms in obstacle environments[J]. Expert Systems with Applications, 2024, 235, 121240.
34	王龙宝, 栾茵琪, 徐亮, 等. 基于动态簇粒子群优化的无人机集群路径规划方法[J]. 计算机应用, 2023, 43 (12): 3816- 3823.
	WANG L B , LUAN Y Q , XU L , et al. Path planning method for UAV swarm based on dynamic cluster particle swarm optimization[J]. Journal of Computer Applications, 2023, 43 (12): 3816- 3823.
35	HUANG Q, SHENG Z C, FANG Y, et al. A simulated annealing-particle swarm optimization algorithm for UAV multi-target path planning[C]//Proc. of the 2nd IEEE International Conference on Consumer Electronics and Computer Engineering, 2022: 906-910.

算法	规划时间/s			节点数
算法	max	avg	sd	opt	avg	sd
NRRT^*	75.4	69.2	15.3	40.3	45.7	5.8
TRH-RRT^*	3.1	1.5	1.3	25.5	30.8	6.7
Hash-RRT^*	1.4	0.7	0.6	20.4	25.4	4.5

算法	转弯角/(°)			飞行时间/min
算法	max	Avg	sd	opt	avg	sd
NRRT^*	44.8	15.9	3.7	11.9	13.8	1.5
TRH-RRT^*	43.0	14.3	3.5	11.4	13.3	1.4
Hash-RRT^*	37.2	15.1	1.5	9.3	10.8	0.9

算法	差异化处理
RRT^*^[10]	目标偏差、随机探索
NRRT^*^[17]	目标偏差、引入编队身份特征
改进NSGA-Ⅱ^[32]	初始化随机种群随机变异操作
2DQN^[33]	动态调整贪心策略和环境难度
DCPSO^[34]	随机初始设置、动态粒子群
SA-PSO^[35]	随机初始解和邻域搜索

量化方法	指标	RRT^*	NRRT^*	改进的NSGA-Ⅱ	2DQN	DCPSO	SA-PSO	Hash-RRT^*
Frechet	opt	3.63	2.7	7.46	3.86	6.2	2.03	13.43
	avg	1.53	1.49	6.33	2.46	4.46	1.18	10.75
	sd	1.24	0.32	0.47	0.47	0.98	0.11	3.41
DTW	opt	134.1	25.72	77.85	221.06	64.87	12.26	482.67
	avg	47.4	10.69	60.32	137.93	43.48	6.94	292.54
	sd	1814.04	39.56	102.9	1889.4	155.72	4.22	10 477
算法耗时/s	opt	77.92	424.6	40.08	149.18	115.39	8010.6	19
	avg	30.3	346.04	19.63	100.56	35.37	5177.6	3.55
	sd	185.22	62.33	14.38	800.61	397.8	196603	4.93

算法	编队路径长度/km					耗时/s
算法	1	2	3	4	5	耗时/s
NRRT^*	1.16	1.08	1.06	1.13	1.15	315.79
Hash-RRT^*	1.39	1.18	1.05	1.19	1.26	5.49