基于混合策略的复杂山区覆盖搜索方法

刘全义, 刘继豪, 艾洪舟, 覃炜豪, 朱培

清华大学学报(自然科学版) ›› 2026, Vol. 66 ›› Issue (2) : 233-240.

PDF(4537 KB)
PDF(4537 KB)
清华大学学报(自然科学版) ›› 2026, Vol. 66 ›› Issue (2) : 233-240. DOI: 10.16511/j.cnki.qhdxxb.2025.22.038
公共安全

基于混合策略的复杂山区覆盖搜索方法

作者信息 +

Coverage search methods for complex mountainous areas using hybrid strategy

Author information +
文章历史 +

摘要

针对复杂山区环境下无人机覆盖搜索任务中路径冗余与地形阻碍问题,该文提出一种基于混合策略的覆盖搜索方法。该方法融合传统固定式路径规划方法与基于自适应惯性权重改进的粒子群优化算法,当无人机遇到死点时,利用改进粒子群优化算法回溯路径。对比分析了队列回溯与栈回溯两种搜索策略及其对应的优化后的混合策略在不同地形条件下的适用性,结果表明:混合策略在复杂山区任务中展现出显著优势,其搜索路径长度较基于栈回溯的固定式搜索方式减少31.8%,且路径覆盖率稳定增长至100%;改进粒子群优化算法通过自适应权重调整,较传统粒子群优化算法和人工蜂群优化算法收敛速度更快。在不同地形特征环境中进行模拟的结果验证了混合策略在覆盖搜索路径优化与地形适应性上的有效性。该研究为无人机在应急救援等场景中的应用提供了可靠的路径规划方法。

Abstract

Objective: In complex mountainous environments, unmanned aerial vehicle (UAV) coverage search tasks often encounter two core challenges: path redundancy and terrain obstructions. Although fixed-pattern search methods offer convenience and high efficiency in simple scenarios, they struggle to effectively avoid dead points and obstructures in complex terrains due to their rigid pre-planned trajectories. As a result, path repetition and reduced search efficiency become particularly prominent. To address the challenges of path redundancy and terrain obstructions in UAV coverage search tasks within complex mountainous environments, this study proposes a hybrid strategy that integrates traditional fixed-pattern search with an improved particle swarm optimization (PSO) algorithm. This strategy optimizes return path planning, minimizes path redundancy, and enhances adaptability in complex terrains. Methods: This research adopts a grid-based modeling approach to discretize complex terrains, constructing a simulation environment using real-world digital elevation model data from a specific area of Luding County, Sichuan Province, China. During data preprocessing, high-precision terrain data are converted into 3D surfaces via bi-linear interpolation, and threshold segmentation algorithms create binary representations of obstacle zones and passable areas. To address the challenge of dead points in fixed-pattern searches, this study introduces a hybrid backtracking mechanism that integrates queue-based and stack-based backtracking. When encountering dead points, an improved PSO algorithm with adaptive inertia weights is introduced to plan safe and efficient cross-regional paths. In the early iterations, the algorithm assigns larger inertia weights to enhance global exploration. Subsequently, these weights are reduced to refine local searches. In addition, path safety is ensured through various constraint functions, including mathematical models to avoid terrain blockages, maintain safe distances from obstacles, and ensure path continuity. Results: The experimental results indicate that the proposed hybrid strategy exhibits significant advantages in complex mountainous enviornments. This strategy, which combines queue-based backtracking and stack-based backtracking, reduces total path length by 0.66% and 21.1%, respectively. Path coverage gradually increases from initial levels to full coverage (100%), demonstrating robust performance across various terrain conditions. Notably, in highly complex environments, the improved PSO algorithm exhibits faster convergence speed and higher path-planning accuracy than the traditional PSO and the artificial bee colony algorithms. Comparative analysis reveals that stack-based backtracking performs better in complex terrains, whereas queue-based backtracking is more suitable for regions with greater local connectivity. Furthermore, this research is the first to demonstrate that the hybrid strategy can automatically adjust the number of backtrackings without prior information, ensuring flight safety while achieving optimal coverage. The overall optimization reaches 21.1%. Conclusions: This paper presents a hybrid-strategy-based UAV coverage search method for complex mountainous areas and validates its applicability and superiority across various terrain features through experiments. The findings reveal that the hybrid strategy maintains strong terrain adaptability while balancing efficiency and feasibility. In addition, the selection of backtracking methods directly influences the frequency of heuristic algorithm invocations and ultimately affects the quality of path planning. The successful application of the improved PSO algorithm demonstrates its potential for multi-objective optimization in complex environments, laying a foundation for further exploration of more intelligent and flexible UAV path planning technologies. This study holds significant implications for UAV applications in critical scenarios such as emergency rescue and disaster reconnaissance and provides new perspectives for autonomous UAV navigation.

关键词

覆盖搜索 / 改进粒子群优化算法 / 应急救援 / 路径规划

Key words

coverage search / improved particle swarm optimization algorithm / emergency rescue / path planning

引用本文

导出引用
刘全义, 刘继豪, 艾洪舟, . 基于混合策略的复杂山区覆盖搜索方法[J]. 清华大学学报(自然科学版). 2026, 66(2): 233-240 https://doi.org/10.16511/j.cnki.qhdxxb.2025.22.038
Quanyi LIU, Jihao LIU, Hongzhou AI, et al. Coverage search methods for complex mountainous areas using hybrid strategy[J]. Journal of Tsinghua University(Science and Technology). 2026, 66(2): 233-240 https://doi.org/10.16511/j.cnki.qhdxxb.2025.22.038
中图分类号: V249.122+.3   

参考文献

1
SONA G, PASSONI D, PINTO L, et al. UAV multispectral survey to map soil and crop for precision farming applications[J]. The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, 2016, XLI-B1, 1023- 1029.
2
ALOTAIBI E T, ALQEFARI S S, KOUBAA A. LSAR: Multi-UAV collaboration for search and rescue missions[J]. IEEE Access, 2019, 7, 55817- 55832.
3
SZIROCZAK D, ROHACS D, ROHACS J. Review of using small UAV based meteorological measurements for road weather management[J]. Progress in Aerospace Sciences, 2022, 134, 100859.
4
VASQUEZ-GOMEZ J I, MARCIANO-MELCHOR M, VALENTIN L, et al. Coverage path planning for 2D convex regions[J]. Journal of Intelligent & Robotic Systems, 2020, 97(1): 81- 94.
5
张佳庆, 孙韬, 蒋弘瑞, 等. 基于林火风险的高压输电线路无人机巡检路径规划[J]. 清华大学学报(自然科学版), 2024, 64(5): 911- 921.
ZHANG J Q, SUN T, JIANG H R, et al. Path planning for transmission line unmanned aircraft inspection based on forest fire risk[J]. Journal of Tsinghua University (Science and Technology), 2024, 64(5): 911- 921.
6
王兆杰, 彭涛, 茆明, 等. 基于随机搜索两阶段规划模型算法的未知海域水下全覆盖路径规划研究[J]. 中国舰船研究, 2024, 19, 1- 9.
WANG Z J, PENG T, MAO M, et al. Underwater full coverage path planning in unknown waters based on random search two-stage planning model algorithm[J]. Chinese Journal of Ship Research, 2024, 19, 1- 9.
7
CABREIRA T M, FRANCO C D, FERREIRA P R, et al. Energy-aware spiral coverage path planning for UAV photogrammetric applications[J]. IEEE Robotics and Automation Letters, 2018, 3(4): 3662- 3668.
8
AVELLAR G S C, PEREIRA G A S, PIMENTA L C A, et al. Multi-UAV routing for area coverage and remote sensing with minimum time[J]. Sensors, 2015, 15(11): 27783- 27803.
9
OTTO A, AGATZ N, CAMPBELL J, et al. Optimization approaches for civil applications of unmanned aerial vehicles (UAVs) or aerial drones: A survey[J]. Networks, 2018, 72(4): 411- 458.
10
TAN C S, MOHD-MOKHTAR R, ARSHAD M R. A comprehensive review of coverage path planning in robotics using classical and heuristic algorithms[J]. IEEE Access, 2021, 9, 119310- 119342.
11
LI J, XIONG Y H, SHE J H, et al. Optimal path planning for unmanned aerial vehicles with multiple round-trip flights in coverage tasks[J]. Robotics and Autonomous Systems, 2025, 189, 104970.
12
DATSKO D, NEKOVAR F, PENICKA R, et al. Energy-aware multi-UAV coverage mission planning with optimal speed of flight[J]. IEEE Robotics and Automation Letters, 2024, 9(3): 2893- 2900.
13
TANG G, TANG C Q, ZHOU H, et al. R-DFS: A coverage path planning approach based on region optimal decomposition[J]. Remote Sensing, 2021, 13(8): 1525.
14
郑博文, 陈志, 陈锐, 等. 基于RRT的无人机特征点覆盖搜索算法优化[J]. 软件导刊, 2020, 19(7): 56- 59.
ZHENG B W, CHEN Z, CHEN R, et al. UAV feature points coverage searching algorithm optimization based on RRT[J]. Software Guide, 2020, 19(7): 56- 59.
15
ZHU K, HAN B, ZHANG T. Multi-UAV distributed collaborative coverage for target search using heuristic strategy[J]. Guidance, Navigation and Control, 2021, 1(1): 2150002.
16
XU Z F, SUZUKI C, ZHAN X Y, et al. Heuristic-based incremental probabilistic roadmap for efficient UAV exploration in dynamic environments[C]//2024 IEEE International Conference on Robotics and Automation (ICRA). Yokohama, Japan: IEEE, 2024: 11832-11838.
17
CAO J H, WANG Y T, LI K, et al. Multi-UAV adaptive cooperative coverage search method based on area dynamic sensing[J]. Journal of Computational Design and Engineering, 2025, 12(4): 77- 93.
18
SADEGHIAN Z, AKBARI E, NEMATZADEH H, et al. A review of feature selection methods based on meta-heuristic algorithms[J]. Journal of Experimental & Theoretical Artificial Intelligence, 2025, 37(1): 1- 51.
19
YANG Y, GAO Y C, DING Z, et al. Advancements in Q-learning meta-heuristic optimization algorithms: A survey[J]. WIREs Data Mining and Knowledge Discovery, 2024, 14(6): e1548.
20
KIM B R, DO Y B, CHI J H, et al. Evaluation of coastal debris interpretability under varying GSD conditions in UAV imagery[J]. Korean Journal of Remote Sensing, 2025, 41(2): 327- 339.
21
KIM J H, SUNG S M. Quality analysis of unmanned aerial vehicle images using a resolution target[J]. Applied Sciences, 2024, 14(5): 2154.
22
周枫, 王卫东. 一种基于改进人工蜂群算法的无人机航迹规划方法[J]. 计算机与数字工程, 2024, 52(10): 2890- 2896.
ZHOU F, WANG W D. An UAV path planning method based on improved artificial bee colony algorithm[J]. Computer & Digital Engineering, 2024, 52(10): 2890- 2896.
23
耿增显, 广鑫, 陈俊宇, 等. 基于混沌粒子群算法的城市无人机路径规划[J]. 西华大学学报(自然科学版), 2024, 43(6): 1- 7.
GENG Z X, GUANG X, CHEN J Y, et al. Urban UA route planning based on chaotic PSO algorithm[J]. Journal of Xihua University (Natural Science Edition), 2024, 43(6): 1- 7.

基金

国家自然科学基金青年科学基金项目(52202416)
四川省科技厅省院校合作项目(2024YFHZ0027)
中国民用航空飞行学院民机火灾科学与安全工程四川省重点实验室课题(MZ2022JB01)
民航应急科学与技术重点实验室项目(NJ2022022)
民航应急科学与技术重点实验室项目(NJ2023025)
中央高校基本科研业务费专项资金资助项目(25CAFUC04084)

版权

版权所有,未经授权,不得转载。
PDF(4537 KB)

Accesses

Citation

Detail

段落导航
相关文章

/