搜救场景下UAV-UGV协同搜索任务规划

Collaborative search task planning for UAV-UGV in search and rescue scenarios

摘要

针对无人机（unmanned aerial vehicle，UAV）与地面无人车（unmanned ground vehicle，UGV）在搜救场景下的协同搜索任务规划问题，提出一种集中任务分配与独立路径规划相结合的方法。首先，根据需求明确任务并分配给UAV和UGV。然后，UAV和UGV依据各自所负责的任务分别进行航迹规划和路径规划。针对任务分配问题，引入一种基于任务类型的“多目标区域分割与分配”模型，采用一种结合遗传算法（genetic algorithm，GA）与禁忌搜索算法的自适应混合算法进行求解。航迹规划针对UAV任务需求构建了“旅行商路径-区域覆盖路径规划”（traveling salesman path-area coverage path planning，TSP-ACPP）模型，采用改进的遗传算法进行求解，即在传统遗传算法的基础上，引入“S”型路径作为初始种群，并设计适应度函数优化筛选过程。针对UGV的路径规划，提出了将A*算法与人工势场算法相结合求解最优行进路径的方法。仿真结果表明，与常用的遗传算法和A*算法相比，所提出的算法能有效完成搜索任务，并在任务执行效率和路径规划精度上均有显著改善。

Abstract

To address the collaborative search task planning issue for unmanned aerial vehicles （UAV） and unmanned ground vehicles （UGV） in search and rescue scenarios， a method that combines centralized task allocation with independent path planning was proposed. Firstly， tasks were clarified based on requirements and assigned to UAV and UGV. Firstly， the UAV and UGV conducted trajectory planning and path planning independently according to their assigned tasks. For the task allocation problem，a multi-objective area segmentation and allocation model based on task types was proposed，and an adaptive hybrid algorithnm incorporating genetic algorithm and tabu search was developed in solution.For trajectory planning， a “traveling salesman path-area coverage path planning” model was constructed based on the task requirements of the UAV， employing an improved genetic algorithm that introduced an “S”-shaped path as the initial population and designed a fitness function to optimize the selection process. Regarding the path planning for UGV， a method that combines A* algorithm with artificial potential field algorithm was proposed to find the optimal traveling path. Simulation results indicate that the proposed algorithm effectively completes search tasks and shows significant improvements in both task execution efficiency and path planning accuracy compared to commonly used genetic algorithms and A* algorithms.

Graphical abstract

关键词

任务分配 / 独立路径规划 / 遗传算法 / 禁忌搜索算法 / 搜救场景

Key words

task allocation / path planning / genetic algorithm / tabu search / search and rescue scene

随着无人系统技术的快速发展，无人机（本文仅研究旋翼无人机）和地面无人车（以下称UGV）在复杂环境中的协同作战能力得到重视。这些无人系统已被广泛应用于物流配送、灾害监测和环境勘测等领域^［1-3］。利用UAV和UGV的协同优势，可以有效覆盖大范围区域，提升任务执行效率。然而，实现高效的协同搜索^［4］任务规划仍然面临诸多挑战，尤其是在任务分配和路径规划环节。随着任务环境的复杂性和不确定性的增加，如何在任务分配和路径规划中兼顾效率和精度，成为亟待解决的问题。

在现有文献中，孟靖昊^［5］设计了自适应遗传算法，解决任务规划时冗余迭代与停滞问题。王垚等^［6］将遗传算法与模拟退火思想相结合，提升任务分配的求解速度。王志洋等^［7］从多个方面改进遗传算法确保无人艇集群航行总路线最短。师文喜等^［8］采用多智能体遗传算法解决任务分配和路径优化综合代价最小问题。Li等^［9］利用改进的遗传算法来解决多无人机协同侦查中任务分配和资源调度问题。Li等^［10］采用加权算法和遗传算法辅助整数线性程序完成对不同服务的无人机的任务分配。Pehlivanoglu等^［11］提出多种改进的遗传算法以提高路径规划的效率和安全性。Guo等^［12］提出了一种采用快速扩展随机树作为初始路径方案的改进遗传算法，解决传统遗传算法在连接路径点方面的不足问题。李明龙等^［13］提出一种自适应反馈调节遗传算法，解决UGV在路径规划中易陷入局部最优解的问题。

以上算法在任务规划方面取得了一定的进展，但在处理大规模任务时的计算效率仍需提升。因此，本文将进一步探讨UAV和UGV在复杂环境下的搜索任务规划问题，将其拆解为任务分配和UAV航迹规划、UGV的路径规划，进行建模分析，并提出相应的求解算法，结合任务场景进行仿真验证。

1 任务分配建模及算法设计

1.1 任务场景描述

在本文中，设定的救援任务场景如图1所示。该场景为受灾现场，存在多个潜在的搜救目标，且待搜索区域面积较大，考虑到UAV的续航时间和UAV、UGV区域分配，由UAV-UGV协同完成搜索任务。

在待搜索区域旁设置等待区，待作业的UAV、UGV停留在等待区等待分配任务。任务分配算法将待搜索区域划分为多个子区域，这些子区域将作为任务分配的基本单元分配给对应的UAV和UGV，这样便将多机协同搜索问题转化为子区域上的单机搜索问题^［14］。任务分配完成后，由UGV负载UAV奔赴待搜索区域。到达任务开始区域时，UAV起飞，按照规划的路线执行搜索任务；UGV以UAV规划的降落点为目标进行路径规划，去往任务结束区等待UAV降落，之后负载UAV返回基地。这种协同模式不仅节省了UAV的电量消耗，还提高了搜索行动的效率。

需要作出以下假设：

1）对于受灾位置的区域已知，UAV经过即视为搜索完成；UAV除起落外，其余均匀速飞行。

2）UAV执行搜索任务过程中，飞行高度不变且足够高，可忽略地形等影响，采用二维地图。

3）忽略UAV姿态变化，传感器高度h（单位为m）处的探测范围为半径R（单位为m），R=h\mathrm{t}\mathrm{a}\mathrm{n}\theta的圆^［15］。

1.2 任务分配模型

根据UAV的数量将待搜索区域分割成对应数量的子区域，各子区域的面积大小只需要考虑UAV的续航时间，然后将任务分配给对应的UAV和UGV。该问题可被描述为多目标区域分割与分配模型。该模型的目标为最大化覆盖率，确保分配的待搜索区域能够被完全覆盖。

目标函数为

F=\mathrm{m}\mathrm{a}\mathrm{x}{\displaystyle \sum _{i=\mathrm{1}}^n}{C}_i（1）

式中：C_i为第i架UAV的覆盖率；n为UAV的数量。UAV电量与搜索面积之间的关系为

A=\mathrm{2}vR\frac{E}{P}（2）

根据式（2）即可根据电量确定每个UAV可搜索的最大面积。在进行分配时，被分配的面积不可超过其可搜索的最大面积。

1.3 基于自适应遗传禁忌搜索的任务分配算法

针对多目标区域分割与分配模型，采用自适应遗传禁忌搜索算法（adaptive genetic tabu search algorithm，AGTSA）进行求解。遗传算法是一种模拟生物进化过程的优化算法，具有多目标优化、避免梯度依赖的特点，其进行任务分配的一般步骤如下：

1）初始化种群：种群中的每个个体都代表一条染色体，染色体上携带的基因代表了一种可能的任务分配方案。

2）适应度评估：计算每一个染色体的适应度函数，将任务完成总时间作为适应度函数，来确定该个体是否存活。适应度越高的个体越有可能进入下一代种群。

3）选择：根据适应度值，通过轮盘赌的方法从当前种群中选择染色体参与之后的遗传操作，将基因遗传到下一代群体中。

4）交叉：经过选择存活下来的个体成为子代，在子代中随机抽取两个个体成为父代，在父代个体中随机选取一个交叉点，两个父代个体自交叉点之后的部分互换，得到了两个新的个体。将新的个体添加到种群中，维持种群数量不变。

5）变异：随机抽取一个个体，随机指定两个不同的变异位置，将其基因互换，以增加种群的多样性。

6）更新种群：将新生成的染色体与原种群进行替换，形成新一代种群。

7）终止条件检查：检查是否满足终止条件，终止条件为适应度达到一定阈值。返回适应度最高的染色体作为最终的任务分配方案，并输出相关的任务执行信息。

在选择和交叉过程中，GA可能会过快地收敛到局部最优解，而不是全局最优解，会降低种群多样性。引入自适应机制和禁忌搜索算法，可以动态调整参数并克服局部最优解的问题。

在完成变异操作之后，在新的种群中引入禁忌搜索，生成邻域结构，通过交换任务生成一组新的邻域解，再对每个邻域解计算适应度，并从所有邻域解中选择适应度值最优且不在禁忌表中的解作为当前解，并将当前的最优解添加到禁忌表中。如果禁忌表已满，则删除最早添加的记录。再融合自适应机制，根据种群多样性动态调整交叉率和变异率，种群多样性越高，变异率越高，交叉率越低。AGTSA流程图如图2所示。

2 UAV航迹规划模型及算法设计

2.1 UAV航迹规划模型

在任务区域分配完成后，UAV需要前往所分配区域的任务起始区开始起飞，以最短路径和最大化搜索覆盖率为目标进行航迹规划，即为UAV的区域覆盖路径规划问题（coverage path planning，CPP）。UAV执行完搜索任务后，不需要回到任务起始区，以最后搜索点为任务结束区进行降落，可概括为旅行商路径问题（traveling salesperson path problem，TSPP）。因此，UAV的航迹规划可表示为旅行商路径-区域覆盖路径规划（TSPP-CPP）问题^［16］。

该目标是最小化总路径长度和最大化覆盖率，目标函数为

F={\omega }_{\mathrm{1}}\frac{l_i}{l_{\mathrm{m}\mathrm{a}\mathrm{x}}}-{\omega }_{\mathrm{2}}\frac{c_i}{c_{\mathrm{m}\mathrm{a}\mathrm{x}}} （3）

式中：F为综合目标函数；{\omega }_{\mathrm{1}}和{\omega }_{\mathrm{2}}为权重参数，{\omega }_{\mathrm{1}}和{\omega }_{\mathrm{2}}的确定需要进行大量的实验；l_i为当前路径的长度；l_{\mathrm{m}\mathrm{a}\mathrm{x}}为路径长度的最大可能值；c_i为当前路径的覆盖率；c_{\mathrm{m}\mathrm{a}\mathrm{x}}为覆盖率的最大可能值。

2.2 基于改进遗传的UAV航迹规划算法

针对UAV航迹规划的TSPP-CPP问题，采用改进的遗传算法（improved genetic algorithm，IGA）。将遗传算法与S型路径规划进行融合，同时引入奖惩机制。每个个体代表一种可能的航迹规划方案，生成初始种群。适应度函数考虑了覆盖率、路径长度。首先构建多目标适应度函数，明确主要目标是最小化路径长度及最大化搜索覆盖率，分别为以上二者选择合适的权重，并构建一个线性组合的适应函数。其次加入奖惩机制，当路径长度超过设定的阈值时，添加惩罚项；当覆盖率小于设定的阈值时，同样添加一个惩罚项；若路径长度非常短或覆盖率非常高时，添加一个奖励项。最后，对适应度函数进行优化。适应度函数为

F={\omega }_L\frac{L_{\mathrm{m}\mathrm{a}\mathrm{x}}-L}{L_{\mathrm{m}\mathrm{a}\mathrm{x}}}+{\omega }_C\frac{C}{C_{\mathrm{m}\mathrm{a}\mathrm{x}}}+P+R（4）

式中：{\omega }_L为航迹长度权重； {\omega }_C为覆盖率权重；L为航迹长度；L_{\mathrm{m}\mathrm{a}\mathrm{x}}为航迹长度的惩罚阈值；L_{\mathrm{m}\mathrm{i}\mathrm{n}}为航迹长度的奖励阈值；C为覆盖率；C_{\mathrm{m}\mathrm{i}\mathrm{n}}为覆盖率的惩罚阈值；C_{\mathrm{m}\mathrm{a}\mathrm{x}}为覆盖率的奖励阈值；P为惩罚系数，即

（5）

R为奖励系数，即

（6）

3 UGV路径规划模型及算法设计

3.1 UGV路径规划模型

UGV需要以UAV的起飞点为出发点，以UAV的降落点为目标点规划行进的路线，并要求到达时间不大于UAV执行搜索任务的时间。该过程可以被描述为一个路径规划问题。

目标函数为最小化路径长度，即

F=\mathrm{m}\mathrm{i}\mathrm{n}{\displaystyle \sum _{i=\mathrm{1}}^{n-\mathrm{1}}}d(p_i,p_{i+\mathrm{1}})（7）

其中d(p_i,p_{i+\mathrm{1}})为路径点p_i和p_{i+\mathrm{1}}之间的距离。

3.2 基于A*与人工势场融合的UGV路径规划算法

UGV的路径规划采用A*与人工势场融合算法（A*-artificial potential field algorithm，A*- APFA），结合两者优点，实现更高效的路径规划。A*算法在复杂和动态环境中的计算复杂度较高，导致实时性不足。为了解决这一问题，可以引入实时性强、易于实现的人工势场法，以适应动态环境，既确保路径的最优性，又能快速响应动态变化，从而提高算法的鲁棒性和搜索效率。此外，该算法能够实时感知动态调整路径，显著提升空地协同搜救系统的效率和可靠性，确保在紧急情况下快速、精准地完成任务。

使用A*算法在网格地图上找到从起点到终点的初步路径，由于栅格地图中存在障碍物，且UGV可以进行对角移动，故使用欧几里得距离作为启发式函数。再利用人工势场法对A*算法生成的初步路径进行优化。首先，对A*生成的初步路径上的各个节点分别计算其在人工势场中的总势场值；其次，采用梯度下降法调节路径节点的位置，使其在人工势场中沿势场梯度方向移动，以减少总势场值；最后，更新路径点的位置。

4 仿真验证

构建环境的栅格地图模型，每个网格代表环境中的10个单元，黑色代表障碍物，白色代表空闲区域。可根据实际情况，手动选择区域添加障碍物。构建的地图模型如图3所示。

4.1 任务分配算法验证

将构建的最终地图应用在AGTSA中，以评估任务分配效果。在AGTSA模型中设置了3个UAV，并设置其初始电量分别为95.00%、85.00%、75.00%。这种设置旨在模拟不同电量水平下的无人机任务执行能力，以更真实地反映实际应用场景。接下来运行AGTSA，算法考虑了各UAV的电量状态和任务需求，具体分配结果如图4所示。为了进一步评估AGTSA的性能，选用GA作为对比基准。在相同初始条件下运行GA，获得了对比实验的任务分配结果，如图5所示。

在实验中，AGTSA根据UAV的数量将整个待搜索区域划分为3个子区域，并使用不同颜色进行标注。各子区域的面积由UAV的电量决定，电量最多的UAV1分配了最大的面积，电量最少的UAV3分配了最少的面积。这一分配方式确保了高效的资源利用和任务执行。相比之下，GA任务分配结果显示，电量最少的UAV3被分配了最大的面积，这种分配显然缺乏合理性，因为电量较低的UAV在执行更大范围的任务时可能面临电量不足的问题，导致任务无法顺利完成。

4.2 UAV航迹规划算法验证

将AGTSA完成任务分配后的地图作为航迹规划的基础，并运行IGA以规划UAV航迹。为评估IGA的效果，使用GA进行对比实验，在相同的初始条件下运行两种算法，结果分别如图6、7所示。图片中每个区域的左上角为任务起始区，右上角为任务结束区，UAV将在此降落。经过100次试验，得到其所需时间，航迹规划长度及覆盖率对比分别如表1、表2所示。

1）在运行时间上，IGA在航迹规划上展现出极高的效率，其平均规划时间在10^-3s级，说明IGA可在短时间内生成有效的轨迹，大幅提升了实时应用的可能性；相比之下，GA规划航迹平均时间为12 s，明显低于IGA。

2）在航迹覆盖率上，IGA所规划航线覆盖率达到100%，即UAV可以按照规划路径完全覆盖指定区域。而GA规划航线覆盖率为13%左右，表明其在有效覆盖整个任务区域时明显存在不足，可能导致任务执行不完全或遗漏重要区域。

3）在航迹长度上，虽然IGA规划的航线长度要远大于GA规划的航迹长度，但其长度在合理范围内，且在实际任务中，要确保搜索区域的覆盖性。

4.3 UGV路径规划算法验证

以UAV航迹规划出的任务起始区为起点，任务结束区为终点，选用A*-APFA进行UGV的路径规划，规划结果如图8所示。图8中，第一个区域内左上角到右上角实线轨迹为UGV1规划的路线，第二个区域内左上角到右上角实线轨迹为UGV2规划的路线，上角实线轨迹为UGV3规划的路线。每个区域内的虚线为对比算法A*规划的路线。

表3、表4分别为100次试验路径规划时间对比及路径长度对比，实验表明：

1）A*-APFA可以减少不必要的运算，比起A*算法，在很大程度上缩短了规划的时间。

2）A*-APFA通过引入势能函数，能引导路径避开障碍物并更好地利用空旷区域，优化路径长度。

3）A*算法生成的路径是栅格化的路径，存在较多拐点，不够平滑。A*-APFA可以引入平滑约束，使得路径在避开障碍物的同时更加自然和连续，减少急转弯和不必要的路径折返。

5 结论

本文针对UAV、UGV在复杂环境下的协同搜索任务规划问题，提出了一种集中任务分配与独立路径规划相结合的方法。通过引入多目标区域分割与分配模型，在任务分配阶段将任务有效地分配给UAV和UGV，并结合自适应遗传禁忌搜索算法，提高了任务分配的效率。此外，针对UAV的航迹规划，构建了旅行商路径-区域覆盖路径规划模型，并采用改进的遗传算法，优化了路径规划的初始种群与适应度函数，从而提升了规划精度。对于UGV的路径规划，结合了A*算法与人工势场算法，能够有效求解最优行进路径。实验结果表明，所提出的算法在任务执行效率和路径规划精度方面均显著优于传统的遗传算法和A*算法。该方法为实现UAV与UGV的协同搜索任务规划提供了新的解决思路。

参考文献

[1] 职雪刚，马小东.基于消防应急救援的无人机集群系统研究［J］.今日消防，2023，8（10）：23-25.

[2] 郭兴海，计明军，温都苏，等.“最后一公里” 配送的分布式多无人机的任务分配和路径规划［J］.系统工程理论与实践，2021，41（4）：946-961.

[3] 刘森，姜雪松，张宇晨，等.林火搜救多无人机协同任务分配方法［J］.中国新技术新产品，2024（6）：133-136.

[4] 李彦强，王建辉.基于遗传算法的无人机编队高速公路巡检任务规划方法［J］.市政技术，2023，41（11）：67-73.

[5] 孟靖昊.空面多目标攻击中武器-目标最优分配［J］.航空科学技术，2024，35（8）：104-110.

[6] 王垚，石永康.基于改进遗传算法的多无人机任务分配［J］.现代电子技术，2023，46（4）：139-146.

[7] 王志洋，王龙金.基于改进遗传算法的无人艇集群多任务分配路径规划［J］.船舶工程，2024，46（4）：105-111.

[8] 师文喜，付艳云，赵学义，等.基于多智能体的巡逻任务分配和路径优化方法研究［J］.中国电子科学研究院学报，2021，16（7）：633-638.

[9] Li J T， Zhang S， Zheng Z，et al.Research on multi-UAV loading multi-type sensors cooperative reconnaissance task planning based on genetic algorithm［C］//Intelligent Computing Theories and Application.Cham：Springer International Publishing，2017：485-500.

[10] Li C Y， Chin K W， Zhu Y D.Maximizing data collection and rental requests in drone-based IIoT networks［J］.IEEE Transactions on Industrial Informatics，2024，20（4）：5937-5945.

[11] Pehlivanoglu Y V， Pehlivanoglu P.An enhanced genetic algorithm for path planning of autonomous UAV in target coverage problems［J］.Applied Soft Computing，2021，112：107796.

[12] Guo P F， Xu W P， Zhu Y C，et al.Multi-UAV collaborative path planning based on improved genetic algorithm［C］//Proceedings of 2021 International Conference on Autonomous Unmanned Systems.Singapore：Springer Singapore，2022：2648-2657.

[13] 李明龙，杨文婧，易晓东，等.面向灾难搜索救援场景的空地协同无人群体任务规划研究［J］.机械工程学报，2019，55（11）：1-9.

[14] 戴健，许菲，陈琪锋.多无人机协同搜索区域划分与路径规划［J］.航空学报，2020，41（）：723770.

[15] 于驷男，周锐，夏洁，等.多无人机协同搜索区域分割与覆盖［J］.北京航空航天大学学报，2015，41（1）：167-173.

[16] 李忠伟，刘旭阳，罗偲，等.旅行商和覆盖路径规划问题的自适应遗传算法［J］.计算机仿真，2024，41（2）：435-440.

基金资助

国家重点研发计划项目(2022YFC2903800)