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

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

Abstract

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

CLC Number:

TP273

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.

Figures/Tables 21

Fig.1

Fig.2

Fig.3

Fig.4

Fig.5

Fig.6

Fig.7

Fig.8

Fig.9

Fig.10

Fig.11

Fig.12

Table 1

Fig.13

Fig.14

Table 2

Table 3

Table 4

Fig.15

Table 5

Fig.16

References 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

Integrating spatio-temporal hash in three-dimensional RRT^* multi-formation route planning

RichHTML

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 21

References 35

Related Articles 15

Recommended Articles

Metrics

Comments

[1]	Zebiao FENG, Xu YANG, Jianjun WANG. Modeling and parameter optimization based on active learning treed Gaussian process [J]. Systems Engineering and Electronics, 2025, 47(6): 1950-1963.
[2]	Ruru LI, Jing LI, Zhaohui ZHANG. Adaptive optimized tracking control of non-strict feedback systems under unknown perturbations [J]. Systems Engineering and Electronics, 2025, 47(6): 1985-1993.
[3]	Zeyang YIN, Hao LIANG, Yuxin LIAO, Xiaofang CHEN, Yongfang XIE. UAV formation path planning based on reachable envelope analysis of dynamic obstacle [J]. Systems Engineering and Electronics, 2025, 47(4): 1275-1284.
[4]	Shengjie XING, Dong ZHAO, Wenjing REN. Event-triggered based actuator failure compensation for flexible manipulator [J]. Systems Engineering and Electronics, 2025, 47(4): 1311-1318.
[5]	Bohai DENG, Jinfa XU. Semi-physical simulation verification of attitude control for compound unmanned helicopter [J]. Systems Engineering and Electronics, 2025, 47(2): 608-620.
[6]	Jiale LI, Qilin ZHONG, Jie XIAO, Guofei LI. Adaptive fixed-time formation control for multi-agent system [J]. Systems Engineering and Electronics, 2025, 47(2): 600-607.
[7]	Hucheng QIN, Yanyan HUANG, Tiande CHEN, Han ZHANG. Cluster multi-target fire planning method based on PPO algorithm [J]. Systems Engineering and Electronics, 2024, 46(11): 3764-3773.
[8]	Ruitao SONG, Xianming GAO, Jiaorui HUANG, Chungang YANG, Tao HUANG, Yuanyuan LI. Behavior tree based management and control architecture and scheduling method for networking service [J]. Systems Engineering and Electronics, 2024, 46(10): 3547-3556.
[9]	Weimin IU, Yongyue WANG, Xinyang MA, Jinkun LIU. Consensus control for input-delay multi-agent system with input constraint [J]. Systems Engineering and Electronics, 2024, 46(9): 3176-3184.
[10]	Dong ZHANG, Fuyi XING, Yunhe XU, Peng QIAN. Airborne inertial navigation system/radar integrated navigation method based on dual-mode switching [J]. Systems Engineering and Electronics, 2024, 46(8): 2770-2778.
[11]	Ningyun LU, Yang LI, Bin JIANG, Shoujin HUANG, Kun MA. Overview of design of testability and dot based fault diagnosis strategy for complex systems [J]. Systems Engineering and Electronics, 2024, 46(7): 2359-2373.
[12]	Yang GUI, Bochao ZHENG, Peng GAO. Sliding mode attitude control of quadrotor UAV based on NESO-LFDC [J]. Systems Engineering and Electronics, 2024, 46(3): 1075-1083.
[13]	Yuyu ZHAO, Chao SUO, Yuxiao WANG. Differential flatness-based tracking control method for hypersonic vehicle [J]. Systems Engineering and Electronics, 2024, 46(3): 1084-1092.
[14]	Shuxin HU, An ZHANG, Manyi SUN, Minghao LI. Obstacles avoidance for quadrotor formation based on consensus theory and S-MPC [J]. Systems Engineering and Electronics, 2024, 46(2): 658-667.
[15]	Zeyang JI, Chungang YANG, Fuqiang LI, Ying OUYANG, Xianglin LIU. Intent-driven network representation based on natural language processing [J]. Systems Engineering and Electronics, 2024, 46(1): 318-325.

Integrating spatio-temporal hash in three-dimensional RRT* multi-formation route planning

RichHTML

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 21

References 35

Related Articles 15

Recommended Articles

Metrics

Comments

Integrating spatio-temporal hash in three-dimensional RRT^* multi-formation route planning