无人机协同侦察路径规划研究*

刘泽原，赵佳宜，赵文栋，刘存涛，李艾静

（陆军工程大学，江苏 南京 210000）

0 引言

近些年，无人机因其可操作性、高机动性、灵活性以及经济性等特点被广泛应用于军事和民用领域[1]。例如，在民用领域，无人机用于执行救灾救援、环境研究、天气预报以及农业监控等任务[2]；在军事领域，无人机能够在危险复杂区域飞行，并利用装载的摄像机或其他侦察设备获取多种形式的目标信息，有效降低了人力资源损耗，且能够更高效地执行侦察任务[3]。

相较于单架无人机，多架无人机协作可以创造更高的价值[4]。由于数量优势，它可以轻易扩展侦察覆盖范围，具有可扩展性。同时，无人机系统中的某一架无人机受到损坏时可以由其他无人机替代，相较单架无人机具有更高的抗风险能力[5]。此外，军事领域中，作战要求不断提高，侦察任务逐渐复杂化。尤其是随着未来战争的信息化、网络化、体系化对抗的发展，复杂环境下的情报侦察和战场监控具备更加多元的任务要求[6]，需要以多无人机协同侦察代替单架无人机侦察，以应对更加复杂的侦察任务。

无人机协同侦察中，无人机既可以通过负载的侦察设备获取目标区域信息[7]，也可以与地面传感器网络协同，获取传感器采集的侦察信息[8]。无人机协同侦察的方式和侦察任务的要求不同，因此其目标和约束具有多样性，如侦察时间、侦察信息量、侦察价值等诸多目标，或者能耗、飞行距离等约束。为了实现不同任务目标，需要对无人机进行合理的路径规划。路径规划问题通过规划无人机的飞行路径，使其可以在约束条件下完成指定的任务[9]。单架无人机路径规划中，需要根据已有的信息确定访问目标和访问顺序。它的路径具有时间连续性，涉及到多个连续变量，并会受到各种现实因素的制约[10]。在多无人机协同侦察中，对无人机路径规划前需要对其分配相应的侦察任务，因而任务分配和路径规划两个问题紧密耦合。任何一方的结果会对另一方问题的解决产生影响。为了满足任务要求，必须同时考虑两个问题。因此，无人机协同侦察的路径规划问题的研究具有重要的实际意义和挑战性。

1 路径规划分类

从路径类型上分类，无人机路径规划问题主要包括运动规划、轨迹规划和导航3 类[11]。运动规划涉及到无人机的飞行轨迹和转弯角度，通过优化最小路径长度和旋转角度来优化无人机路径。该路径为无人机在运动空间中的具体变化。轨迹规划主要对路径规划中的轨迹和飞行时间进行处理，路径大多表现为折线路径，体现了无人机访问的目标点和对目标点的访问顺序。导航主要研究无人机的碰撞规避和无人机定位问题，包括监控无人机从源点到目的点的拓扑变化。

从规划过程来看，无人机路径规划问题分为静态规划和动态规划两类。静态规划主要指无人机在飞行前已经获取全局的目标信息，根据所分配任务的要求预先规划飞行路径。静态路径规划要求规划结果更加准确可靠。动态路径规划则是在无人机飞行过程中进行实时路径规划，通常会出现由于其无法获取全局信息或者在飞行过程中飞行环境发生新的变化以及侦察任务要求发生变化的情况。因此，动态路径规划要求无人机在极短时间内产生规划结果。

2 路径规划问题表示方法

处理无人机路径规划问题过程包括预处理和路线规划两个阶段[12]。预处理阶段需要将无人机飞行环境和目标点表示出来，运用不同表示方法生成映射图形。不同的路径规划技术会以不同的方式定义无人机的点和飞行路线。路线规划阶段，无人机根据任务的要求运用不同的路径规划算法求解飞行路径。

预处理阶段主要负责对无人机飞行环境进行表示，而环境表示的合理与否影响着无人机路径规划效果的好坏[13]。表示飞行环境时，需要考虑访问目标、地形环境、飞行障碍、威胁区域等因素。对于不同的任务，无人机面临的飞行环境各不相同。合适的表示方式需要准确表示出当前环境的空间状态，并能够根据环境中部分因素的变化随时更新[14]。通常，无人机的飞行环境包括连续表示、图表示和网格法表示3 种数学表示方法。

2.1 连续数学表示方法

在连续数学表示方法中，无人机的飞行环境和飞行路线被视为连续的值。通常采用欧式空间表示二维或三维的环境空间[15-16]，利用一系列连续的航迹点表示无人机的飞行路径。此外，无人机的目标被视为一个点，环境空间存在的威胁被视为一个函数。例如：文献[17]将飞行环境表示为一个连续的势场，无人机被设计为一个受势场控制运动的粒子，其路径根据初始点到目标点的合成场进行计算；文献[18]运用连续方法表示一个农业系统环境，并设计了基于改进势场方法的威胁模型，被用于寻找局部最小点和生成随机目标点。连续数学表示方法能够精确表示无人机的路径规划问题，但是需要极大的储存空间，复杂度较高，不适合一般的优化计算。

2.2 图表示方法

图表示方法通过在三维环境中定义网络曲线，计算环境空间中各目标点的连通性，并构建路线图，在规划阶段求解起始点和目的点，通过曲线拼接找到无人机在这些点之间的路径。其中，各点之间的曲线权重表示无人机的飞行代价，在规划阶段根据无人机任务目标确定最优或次优的路径[19]。路线图的表示技术能够较好地解决静态环境下移动的无人机路径规划问题。文献[20]提出了基于最优控制的无人机路径规划算法，利用路线图解决了旅行商问题（Traveling Salesman Problem，TSP），同时计算了覆盖所有遥感区域的最小飞行时间，以执行无人机的所有通信任务。

根据图的来源不同，可以将构建路线图的方法分为构建概率图、快速随机探索树和Voronoi 图（Voronoi Diagram，VD）3 类。概率图（Probabilistic Roadmaps，PRM）由直边连接的随机节点组成。文献[21]基于PRM 提出了一种用于在城市环境中跟踪和搜索路径的路线图算法。文章中调查发现，该技术可以用于无人机的碰撞避免和发现通信缺口故障。构建快速随机探索树（Rapid-exploring Random Trees，RRT）通过构建随机空间填充树来表示高维空间。文献[22]提出了RRT 与人工势场相结合的方法，给出了最优无人机路径规划。Voronoi 图方法中，针对一个特定的平面，根据到路径点的距离将曲面划分为不同区域。对于不同的任务要求，该方法对路线图的节点和边的定义不同。文献[23]提出了无人机最优性的一致性理论，使用VD 设计路线图和寻找障碍，然后采用协同控制的方法对多障碍物进行探测，最后利用VD 中的一致性理论确定了最优路径，并计算了总飞行成本。

2.3 网格表示法

网格方法将场景分成多个网格，根据网格大小形状区别将其分为均匀网格和非均匀网格，其中均匀网格主要体现为正三角形网格、正方形网格和六边形网格。网格方法将无人机及目标用单一网格表示，将障碍物和禁飞区用多个连续网格表示[24]。同时，该表达方式可以简明判断出同一网格或相邻网格内两点的安全路径。在对环境空间的网格进行计算后，根据网格顺序规划出无人机飞行路径。此外，通过网格表示法得到的路径需要进行平滑处理。

3 路径规划求解算法

在规划阶段，无人机根据预处理阶段中对环境的数学表示，通过规划算法求解无人机飞行路径。无人机路径规划需要根据任务和实际要求综合考虑无人机到达时间、能耗限制、威胁区域、时间要求等因素，并根据任务目标规划出最优或次优的飞行路径，保证无人机圆满完成任务并返回基地[25]。可见，路径规划算法的优劣决定着规划的路径能否满足无人机的任务要求。当前路径规划算法可分为以数学推导为主的传统算法和以生物与自然规律为启发的智能算法。

3.1 传统算法

传统算法通常以寻找唯一全局最优点为目标，主要包括数学规划法、动态规划法、最优控制法、牛顿法以及梯度法等优化方法。文献[26]中基于凸优化理论，提出了一种有人/无人机协作系统的轨迹规划方法。文章建立系统的运动模型，分析控制过程，随后设计无人机的路径规划，分别以能量消耗最小和到达时间最短为优化目标，在时空约束条件下对规划模型进行了逼近和凸优化，最后利用凸优化算法求解问题。文献[27]探讨了自主监控跟踪目标的路径规划问题，包含探测、生存和跟踪等多个任务目标。文章通过对单目标的凸组合进行优化，在性能空间中找到了一组无人机的最优航迹点。

文献[28]针对四旋翼无人机路径规划中产生的轨迹位移、速度和加速度函数中存在大量不可微点的问题，提出了一种基于贝塞尔曲线最小和高阶位移导数轨迹的优化方法。采用最小位移导数法对轨迹进行优化，将贝塞尔曲线引入优化函数，通过讨论四旋翼无人机飞行约束，将其轨迹转化为凸二次规划问题，采用内点法进行求解。文献[29]研究了无人机空间覆盖类型应用的路径规划问题，将其看作旅行商问题和覆盖路径规划问题的组合，随后针对此类问题建模为混合整数线性规划问题，并分别利用动态规划和启发式方法对其进行求解。文献[30]研究了固定翼无人机U2U（UAV-to-UAV）的通信系统，通过规划无人机路径使信息传输时间最小化。文章提出了一个包含信息吞吐量、地面发射机干扰、无人机速度限制等因素的通用通信框架，并在此基础上提出了一种基于精确惩罚法和逐次凸逼近的路径规划算法。

3.2 智能算法

智能算法主要来源于人类智能、生物行为或自然规律的启发，包括进化算法、群体智能算法、模拟退火算法、禁忌搜索算法以及神经网络算法5 类，主要特点是能够通过迭代在短时间内获取路径规划问题的次优解。文献[31]提出了用于无人机航迹规划的改进人工蜂群算法，参数少，收敛速度快，能够使无人机避免实时环境下的动态威胁。文献[32]提出了一种经过模拟退火的遗传算法，称为GASA算法，用于改进无人机航迹规划。该算法具有成本最小、鲁棒性强、路径最佳以及速度快等优点。文献[33]提出了改进的遗传算法（Improved Genetic Algorithm，IGA）和基于蚁群优化算法的粒子群算法（Particle Swarm Optimization Based on Ant Colony Optimization，PSO-ACO）来解决无人机TSP 问题。文献[34]结合聚类算法和遗传算法对多无人机的任务分配和路径规划问题进行求解，有效满足了侦察任务的时间约束。

文献[35]考虑了无人机和无人车协同侦察和监视的任务场景，提出了一种结合分布估计算法（Estimation of Distribution Algorithm，EDA）和遗传算法（Genetic Algorithm，GA）的混合算法来解决无人机的路径规划问题。文献[36]提出了一种基于多智能体深度确定性策略的梯度（Multi-Agent Deep Deterministic Policy Gradient Algorithm，MADDPG）算法，同时使用人工智能方法解决动态环境下的路径规划问题。文献[37]研究无人机辅助的蜂窝网络，由无人机充当飞行中继将信息在蜂窝之间进行传递，随后针对接入点选择子问题具有NP 困难的特点，提出了一种基于博弈论的分布式算法，指导用户自主选择基站或无人机作为接入点。同时，为了实现最优信道状态，采用基于深度强化学习（Deep Reinforcement Learning，DRL）的方法求解无人机路径规划子问题，指导无人机在各个位置采取最优行动。

4 优化目标和约束

4.1 路径规划优化目标

无人机协同侦察路径规划的优化目标主要包括能耗优化、时间优化以及效益优化3 类。能耗优化的目的是在完成规定任务的前提下，减少多无人机执行侦察任务时的能量损耗，延长无人机寿命，主要包括能耗公平性、总能耗最小和最大能耗最小化3 类问题。文献[38]研究了无人机对目标区域进行视频侦察并将信息传回基站的场景，综合考虑了无人机侦察时的飞行能耗、通信能耗和悬停能耗，并提出了一种基于能耗公平性的路径规划算法。文献[39]研究了无人机辅助地面传感节点通信的场景，通过联合优化无人机轨迹和地面节点之间的通信时间分配和任务完成时间，实现无人机的能耗最小化。文献[40]将能量消耗建模为与飞行速度和飞行状态等因素相关的函数，并找到使总能耗最小的飞行速度。

时间优化是为了无人机提高完成侦察的效率，在保证规定任务完成的情况下减少无人机执行任务的时间。无人机通常在执行延迟容忍的侦察任务时将时间作为约束和优化目标。文献[41]考虑了多无人机从数据中心出发为传感器提供数据采集场景，以无人机返回数据中心时间最短为目标，并通过联合传感器调度和无人机路径规划优化任务完成时间。文献[42]研究了无人机成辅助采集传感器信息中信息年龄最小化问题，将问题建模为最大时间最小化的路径规划问题，并利用基于强化学习的策略求解问题。文献[43]主要利用无人机作为空中平台，通过联合优化无人机路径和通信资源分配方法，在满足各目标点的数据需求的同时，最大限度地缩短无人机的周期飞行时间和任务完成时间。

效益优化主要是为了提高无人机在规定时间或其他限制下侦察收益的最大化。侦察收益包括无人机访问目标点所获得的数据量、信息价值等。文献[44]考虑了无人机采集水下多模态无线传感器网络的场景，将感知的数据价值与一个随时间衰减的值相关联，并利用基于贪婪的自适应寻路算法，以最大化接收数据的信息价值。文献[45]考虑到不同侦察点的信息价值不同，为多架异构无人机提供侦察信息价值最大化的路径规划方案。文献[46]则将目标区域划分为簇，根据信息价值和节点功率确定簇头及数据转发规则。传感器节点以事件驱动的方式收集周围的信息。无人机作为移动汇聚节点收集簇头节点的数据。

4.2 路径规划约束

无人机的约束来自3 个方面。

一是由无人机自身的约束，如电池容量限制、飞行速度限制、运动性能限制、加速度和转角等约束。文献[47]针对无人机具有不同飞行速度时的路径规划问题进行了数学建模，并提出了以最小化侦察时间为目标的路径算法。文献[48]则考虑了无人机存在起飞时间间隔的情况，研究了侦察区域覆盖率最大化的路径规划问题。

二是无人机需要满足环境的约束，如禁飞区、障碍物等。文献[49]考虑了不同类型的禁飞区存在的场景，提出了一种基于A*算法解决多类型禁飞区并存的无人机避障路径规划问题。文献[50]则利用改进的人工势能算法解决无人机在追踪目标的过程中实时避障的问题。

三是任务约束，根据任务要求决定，如访问目标要求、任务完成时间要求等。例如，文献[51]中无人机侦察多个目标区域，其获取目标区域的信息大小取决于其在目标区域的停留，其路径规划面临最大飞行时间和目标区域最低停留时间的双重约束。

5 下一步研究方向

5.1 面向多用户的无人机协同能耗问题

当前无人机协同侦察路径规划研究大多只考虑无人机服务单个用户或者无人机只向一个分发信息的基站传递信息的情况。然而，有多个用户存在且缺少分发信息的基础设施的情况下，无人机则必须进行对目标的侦察和对用户的信息分发两个过程。无人机协同侦察目标后，每架无人机可能具有多个用户需要的信息，在信息分发过程中则会导致多架无人机对用户的冗余访问，进而造成较大的能耗。因此，对于面向多个用户，无人机同时进行侦察和信息分发两个过程的协同路径规划问题需要进一步研究。

5.2 不同优先级用户的信息获取时间问题

在面向多用户的侦察场景中，由于用户的重要程度不同和对信息需求的紧迫程度不同，其信息获取的优先级也不同。相对于优先级较低的用户，优先级高的用户需要更快地获取信息。当前针对侦察任务时间的研究中，大多没有考虑不同优先级用户存在的情况。一方面，大多研究以无人机侦察时间为优化目标，没有综合考虑不同优先级用户的信息获取时间，其优化目标不能基于优先级情况平衡各用户信息获取时间，因而需要建立一套面向不同优先级用户信息获取时间的评价指标。另一方面，相关路径规划研究中，无人机通常采取一次性侦察或多次往返侦察的模式，即无人机所有需要目标后前往信息接收节点，或者无人机多次往返于侦察区域与信息接收节点，每一次往返无人机只带回部分目标的信息。一次性往返的侦察模式无法保证高优先级用户更快地获取信息，多次往返侦察模式则会导致低优先级用户信息获取时延过大。因此，在多优先级用户存在的情况下，需要对无人机侦察模式和路径规划方法进行进一步研究。

5.3 多用户决策效用问题

无人机为战场用户提供侦察服务时，需要考虑到用户的决策效用问题。用户决策的效用同时取决于其进行决策的时间和进行决策时所依据的信息的总价值。前者决定了用户决策的时机性，后者决定了用户决策的正确性。前者要求无人机减少侦察时间以尽快带回信息，后者则要求无人机增加侦察时间以获取更多目标的信息。在无人机资源有限的情况下，如何平衡相互矛盾的两个需求以最大化用户决策的战略价值是一个严峻的挑战。此外，战场中通常存在多个决策用户，它们具有不同的信息需求且所作决策的重要程度不同。如何对各用户的决策效用进行综合衡量并设计相应的路径规划方案也需要进一步研究。

6 结语

路径规划问题从路径类型上分为运动规划、轨迹规划和导航3 类问题，从规划类型上分为静态路径规划和动态路径规划2 类。无人机路径规划环境和路径表示方法包括连续数学表示、图表示方法以及网格表示法。无人机路径规划算法主要分为智能算法和传统数学算法两大类。传统数学算法利用数学推导求解路径规划问题，智能算法则通过迭代方式在短时间内获取次优解。此外，路径规划算法还需要考虑侦察目标约束，通常包括能耗约束、时间约束和侦察收益约束3 类。下一步工作还需要考虑无人机为不同优先级用户提供侦察服务的情况，包括面向多个用户的协同侦察能耗问题，面向不同优先级用户的信息获取时间问题和多用户决策效用问题。