以不间断更新目标区域信息为目标的移动持续监视，是实现战场态势感知的基础，对战场搜索、入侵检测、安防等具有重要意义^[1]，同时，也可广泛应用于人群和社会运动监测^[2]、交通管控^[3]、环境调查^[4]、精确农业^[5]、森林火灾监控等^[6]民事任务中。

随着自动化水平的提升，旋翼无人机(UAV)因机动能力强、移动速度快、监视范围大的优点，被广泛应用于持续监视任务中^[7]。实际中，由于旋翼无人机飞行高度约束，在城市、大型工厂等复杂环境中，无人机必须沿着实际道路网进行移动。然而，已有的持续监视研究普遍处理平面内无障碍的场景^[8-9]，很少关注对路网区域的持续监视问题。事实上，路网持续监视的场景广泛存在于现实任务，比如，无人车在校园道路上巡逻或检测异常^[10]、无人船在河道网络中检测事故或收集水文信息^[4]、移动传感器在精确农业中监控田间气体湿度等相关数据^[11]。

路网持续监视可以抽象为具有一定覆盖范围的移动单元在网络拓扑结构上连续移动以寻求整体最优效果的新问题。因此，监视问题的建模和移动单元的轨迹规划是路网持续监视的2个关键问题。现有的研究中，与路网持续监视问题最相似的是多机器人巡逻问题。巡逻问题解决如何最小化无向图中所有巡逻点2次访问的时间间隔^[12]的问题，其问题建模时直接以时间变量^[13]及其相应的变种^[14-15]为评价指标，存在“所至即覆盖”的假设，不考虑传感器的实际监视效果^[16]。在轨迹规划方面，现有的巡逻路径规划方法可分为循环路径(闭路径)模式、区域分割模式和随机模式3类。循环模式的目的是为各移动单元规划一条统一的路径^[10]，各单元以等间距或等时间间隔编队移动^[17]，此模式的好处在于任务周期内轨迹已知，利于系统的规划和决策，且被证明是可使所有兴趣点的最大间隔时间最小的最优巡逻模式^[15]，缺点是周期化的轨迹极容易被反侦察，同时不能适应巡逻环境的动态扩展。区域分割模式中，基于各种图分割^[18]或区域分割^[19]技术为每个移动单元生成单独巡逻路径，通过规划各单元的巡逻速度和停留时间实现一定的均衡性和随机性，但分区策略在面对智能攻击者时的表现不如非分区方法^[12]。随机方法规划出的巡逻轨迹，相对于反侦察者而言是不可预知的，因此更适合防渗透的安防监视和态势感知任务。目前的随机轨迹生成方法主要分为反应式、认知式、概率式和学习式。反应式方法是指依靠局部信息驱动机器人运动的方法^[20]，诸如分布式协调方法^[21]、基于贪婪策略的方法^[22]、基于信息素的群智能方法^[23]也可归为反应式方法；认知式方法是指依靠全局信息驱动机器人运动的方法^[24]；概率式方法是指基于概率模型的机器人轨迹生成方法^[25]，如基于蒙特卡罗搜索树^[26]和贝叶斯学习^[27]等方法；学习式方法是基于人工智能技术驱动机器人运动的方法，如使用安全博弈^[28]、强化学习^[29]等，但学习式的方法训练成本大，尤其是大型地图上^[30]。

与巡逻问题不同，在路网持续监视问题中，由于无人机具有一定的感知范围，无人机不必到达每个节点，而是到达可以完全监视目标节点的节点即可。由此可见，路网持续监视的轨迹规划问题是“区域到区域”的规划，由于路网的强约束性，获得使区域内各节点的监视效果最佳的无人机最优轨迹相当困难，而巡逻问题针对“点到点”的规划，因此，目前的多机器人巡逻问题的轨迹规划算法无法直接应用于路网持续监视问题中。本文研究多无人机路网持续监视问题，提出一种多无人机协同持续监视轨迹规划算法。首先，定义多无人机路网持续监视问题，给出该问题的严格的数学表达形式；其次，构造了适合多机协同持续监视的决策量；然后，考虑到传感器的监视准确度，从全局协作的角度设计了一种简单有效的轨迹规划算法。

本文其他部分内容如下：第1节，建立了路网持续监视模型，构造了不确定度度量，并公式化我们的问题；第2节，构造无人机持续监视轨迹规划决策量，基于启发式认知架构和集中式协作策略提出了持续监视轨迹规划算法；第3节，建立了性能评价指标，对多机持续监视算法进行仿真与性能分析，表明协同持续监视算法的准确性和通用性；最后，给出了本工作的研究结论。

1 路网持续监视问题建模 1.1 问题描述

本质上讲，无人机路网持续监视的任务场景是一个事件发生位置和时间均未知的区域。尽管精确的发生时间未知，但事件的持续时间是先验可知的^[31]。因此，持续监视不同于一般的警务巡逻问题^[32]。在警务巡逻问题中，不同位置的犯罪发生率是先验的，且对各个位置的达到频率没有特殊要求^[13]。在持续监视中，任务区域应以一定的频率被不间断地覆盖访问。因此，持续监视任务中无人机的基本行动原则是最优化一个与监视效果相关的指标。通过最小化该指标，事件被监视的可能性将被最大化。考虑无人机传感器监视准确度的影响，路网持续监视问题定义如下。

定义1    多无人机路网持续监视为一组在一片未知事件发生概率和位置的路网区域上移动的具有一定覆盖范围的无人机寻找各自的移动轨迹，以最优化一个与监视效果相关的指标。

1.2 环境离散化模型

路网持续监视建模是轨迹规划的基础。将连续地图构建为由监视指标反映的离散模型，是监视问题中的常用方法^[8]。路网持续监视任务中无人机必须沿地面道路网的拓扑结构移动。按照实际路网的拓扑结构，沿道路中心线将路网中的道路标出，将所有道路表示为集合形式，记W={W₁, W₂, …, W_m}，将所有道路所连接的两侧端点表示为集合形式，记I={I₁, I₂, …, I_u}；取l_e为允许建模偏差，对于非直线道路，将其离散为多条直线段代替，每条直线段段与实际道路W_i间的最大距离不大于允许建模偏差l_e。将离散出的所有直线段的端点记为V={V₁, V₂, …, V_N}，根据道路拓扑结构将各相邻点连接形成边，由此构造无向带权图G=(V, E)，其中，带权边(v_a, v_b)∈E表示无人机从兴趣点v_a到点v_b的实际路程，而两点间的坐标距离为实际距离。

1.3 监视指标构建

考虑到实际传感器网络的动力学特性，构造不确定度^[33]作为监测点决策属性。在不确定度度量中，考虑无人机的传感器监视识别能力、不同监测点的监视优先级和监测点2次被完全覆盖所经历的时间间隔。

首先考虑传感器识别准确度模型。为了不失通用性，不针对任何传感器产品或监视系统，而是假设一个通用关系。传感器识别准确度与移动速度、探测距离和环境复杂度等有关，在我们的模型中，假设无人机移动速度相同，同时假设区域环境复杂度相似，因此传感器识别准确度仅与探测距离有关，距离越近识别准确度越高，反之越低，达到一定距离后将无法识别。因此，将传感器识别准确度建立为分段概率函数形式：

$ {f_{\rm{c}}} = \left\{ {\begin{array}{*{20}{l}} 1&{d \le {d_{\rm{c}}}}\\ {\left( {{d_{\rm{c}}} - d} \right)/\left( {{d_1} - {d_{\rm{c}}}} \right) + 1}&{{d_{\rm{c}}} < d \le {d_1}}\\ 0&{d > {d_1}} \end{array}} \right. $	（1）

式中：d为某一点到传感器中心的距离；d_c为完全探测范围；d_l为可探测极限。

当存在多个传感器对同一监测点进行监测时，采用概率叠加原理^[34]，传感器的联合监测错误度为所有传感器都识别错误的概率F_ci，即

$ {F_{{\rm{c}}i}} = \prod\limits_{r = 1}^{{R_i}} {\left( {1 - {f_{{\rm{c}}r}}} \right)} $	（2）

式中：R_i为覆盖第i个监测点的无人机个数；f_cr为第r个无人机对i点的传感器识别准确度。

其次考虑监测点i被2次完全识别的间隔时间t_ai，表示为

$ {t_{{\rm{a}}i}} = {t_k} - {t_{{\rm{lv}}i}} $	（3）

式中：t_k为当前系统时间；t_lvi为第i个点上次被完全识别时的系统时间。

最后考虑监视等级, 采用线性权重的方式，令每个点具有不同的不确定度增长速率，以满足对某区域的重点监视要求。将三者联合，不确定度会随着时间增加和传感器准确度的下降而增加，因此构造不确定度属性为线性函数：

$ {\delta _i} = {\sigma _i}\left( {{t_k} - {t_{{\rm{lv}}i}}} \right)\prod\limits_{r = 1}^{{R_i}} {\left( {1 - {f_{{\rm{c}}r}}} \right)} $	（4）

式中：σ_i为i点监视权重；σ_i∈σ，σ为监视权重矩阵；δ_i为i点的不确定度。

1.4 不确定度归一化

注意到此时不确定度的量纲为时间单位(s)，实际上不确定度的物理意义是一个“程度”或“可能性”，这是个无量纲的指标，因此采用归一化方式，令当前不确定度除以一个关于时间的上限t_lim，得到归一化不确定度度量：

$ \delta _i^N = {\sigma _i}\left( {{t_k} - {t_{1{\rm{v}}i}}} \right)\prod\limits_{r = 1}^{{R_i}} {\left( {1 - {f_{{\rm{c}}r}}} \right)} /{t_{{\rm{lim}}}} $	（5）

定义归一化不确定度具有以下性质：当某点处的传感器联合监测错误度为0，则该点不确定度为0，其访问时间间隔为0；当传感器联合错误度不为0时，则采用式(5)计算归一化不确定度，归一化不确定度上限为1。

1.5 问题公式化

为定量描述路网持续监视问题，定义一个可反映所有监视点被监视情况的变量作为持续监视的目标函数，记C₁：

$ {C_1} = \frac{1}{N}\sum\limits_{i = 1}^N {\delta _{ji}^N} $	（6）

式中：δ_ji^N为第i个监视点在第j个时刻的归一化不确定度。

因此，路网持续监视问题可以被公式化为：在道路拓扑结构G=(V, E)、传感器识别准确度f_c、监视权重σ的约束下，为一组无人机R寻找各自的轨迹X_Tr以最小化C₁。

2 多无人机持续监视轨迹规划

将定义1中的轨迹规划计算过程视为每一时刻对无人机位置的决策，因此需要构造决策量并制定决策方法。这一部分中，首先定义持续监视的决策量，然后考虑单无人机沿路网进行持续监视时的轨迹规划情况，再考虑多无人机协同持续监视问题，最后分析了算法的计算复杂度。

2.1 决策量设计

为达到降低不确定度的目的，应驱使无人机向不确定度高的区域移动。考虑到实际运行路径，无人机向某个点移动会产生时间成本^[9]，因此，不可直接按照不确定度进行决策，需要设置一个包含移动距离的收益函数。

与固定翼无人机、无人船可在地图内自由移动不同，路网持续监视任务中的旋翼无人机须沿着实际道路行驶。构造归一化不确定度和无人机移动距离的函数，表示无人机对第i个点的持续监视收益值，以此作为无人机轨迹规划中的决策量。同时考虑不确定度的动态特性，构造持续监视收益公式为

$ {A_{ir}} = \delta _i^N - {q_w}d_{\min }^r/\left( {{\sigma _i}{v_r}{t_{\lim }}} \right) $	（7）

式中：A_ir为无人机r到第i个点的收益；q_w为收益系数；d_min^r为无人机r到目标点的可覆盖最短路长度，可覆盖最短路的含义如图 1所示；v_r为无人机r的速度。

定义2    (完全覆盖点)与目标点相关，当无人机抵达该点时，可实现对目标点的完全覆盖。

定义3    (可覆盖最短路)无人机从当前位置移动到目标点的各个完全覆盖点，其中所有路径中距离最短的路径。

2.2 单无人机轨迹规划方法

启发式算法可通过为个体设置简单行动规则获得近似全局最优的效果，是解决复杂路径规划问题的常用思路^[22]。为了达到最大化路网监视效果，令每个无人机向自身全局最大收益位置移动。选用Warshall-Floyd算法计算最短路径。

为了保证算法的全局持续监视效果且避免局部不确定度异常，要求我们应同时考虑全局和局部决策规则。设置了3个基本规则，分别是决策简化、折返抑制和防止停留。

1) 决策简化：为简化决策难度，规定当无人机抵达监测点时才进行规划，规划后将沿着此方向一直移动直至下一监测点。由于实际数值离散精度原因，当无人机实际位置到监测点位置的距离d_r≤0.5v_rdt时，则无人机抵达，其中，dt为算法的规划时间步长。

2) 折返抑制：由于路网的复杂拓扑结构，无法准确判断无人机原路返回是否不利于减小整体监视不确定度，因此允许无人机原路折返，但根据各点的度d_gi确定无人机在该点的折返概率，取折返的概率P_b满足：

$ {p_{\rm{b}}} = \left\{ {\begin{array}{*{20}{l}} 1&{{d_{{\rm{g}}i}} = 1}\\ {0.4/{d_{{\rm{g}}i}}}&{{d_{{\rm{g}}i}} > 1} \end{array}} \right. $	（8）

3) 防止停留：当无人机在某监测点停留时，系统将随机指定该点所有连接的边中的一个，作为下一时刻的前进方向。

2.3 多无人机协作决策方法

文献[35]指出多机器人系统的个体最优性往往不能直接扩展到群体，需通过合理的协同提高群体性能。在单无人机决策基础上，采用集中式协作策略，期望通过全局调控，达到降低平均不确定度和最大不确定度的目的。为降低决策复杂度，减小计算时间，构造2个简单协作规则。

1) 减少轨迹重复：无人机经过某边或即将经过某边时，向其他无人机报告，其他无人机在规划时将尽量减少经过此边的概率。

该协作策略的目的是减少无人机间的重复轨迹，以减少对某些点的重复监视。每次决策前，无人机获取各边被占用情况，若某边被其他无人机使用，则将相应边的路径值修改为一个大数。

2) 分散布局：无人机选中目标点后，通知其他无人机，其他无人机将远离该目标点。

该协作的目的是降低多无人机同时向相邻区域移动的可能性，使其分散布置，以防止部分区域长期未被监测。每次决策前，无人机计算到各点的收益，同时获取其他无人机的目标点及目标点邻接点的序号，将对应的自身收益修改为0。

两个协作策略均期望算法在随机基础上平均化监视效果。最终的多无人机协同路网持续监视算法伪代码如算法1所示。

2.4 算法复杂度分析

关注无人机一次决策(算法1第6~第17步)的计算时间复杂度。很明显，算法1的第6、12、14、16、17步中，仅一次计算，故复杂度为O(1)。算法1第7步为协作过程，待规划无人机向其他无人机索要位置和目标信息，因此复杂度为O(R-1)。算法1第8步中，待规划无人机根据其他无人机数据修改对应的自身路径成本，故复杂度亦为O(R-1)。算法1第9步中，需计算每个点的所有完全覆盖点到当前位置的最短路，记第i点的完全覆盖点个数为n_oi，则需计算O(Nn_oi)次。本算法采用Warshall-Floyd算法计算最短路，其复杂度为O(N³)，故算法1第9步的复杂度为O(N⁴n_oi)。算法1第10步为取最值过程，复杂度为O(N)。算法1第11步中，可根据目标点序号读取在算法1第9步中计算出的可覆盖最短路，故该步复杂度为O(1)。算法1第13步与算法1第15步均需寻找当前位置的邻接点，故复杂度为O(N)。将算法1第6~17步所有步骤的复杂度叠加，则无人机一次决策的计算复杂度最大为O(N⁴·max n_oi)。

3 仿真与结果 3.1 性能评价指标

本文采用的评价指标如下：平均不确定度(C₁)、稳定后的最大间隔时间(C₂)、稳定后的平均不确定度均值(C₃)、稳定后的平均不确定度标准差(C₄)，具体形式如下。

1) 平均不确定度指每个时步中所有监测点的归一化不确定度的平均值，计算方法见式(6)。

2) 最大间隔时间是从稳定监视状态至任务结束，各监视点的归一化不确定度的最大值。其中，无人机的稳定监视状态为无人机至少完成一次全区域覆盖后的时间。

3) 平均不确定度均值是从稳定监视状态至任务结束，区域内各点归一化不确定度的均值：

$ {C_3} = \frac{1}{{T - {t_{\rm{w}}} + 1}}\sum\limits_{j = {t_{\rm{w}}}}^T {\delta _j^N} $	（9）

式中：t_w为稳定状态的起始时间。

4) 平均不确定度方差是从稳定监视状态至任务结束，区域内各点归一化不确定度的标准差：

$ {C_4} = \sqrt {\frac{1}{{T - {t_{\rm{w}}} + 1}}\sum\limits_{j = {t_{\rm{w}}}}^T {{{\left( {\delta _j^N - {C_3}} \right)}^2}} } $	（10）

3.2 仿真结果

为检验算法在不同地图中的可行性与有效性，设置3个在连通度、监视点分布、拓扑结构方面不同的虚拟路网模型，如图 2所示，分别记为G₁、G₂、G₃，3个模型均设置64个点。其中，G₂和G₃分别模拟低连通度和高连通度路网，二者各点均匀分布，最短边长度为100 m，覆盖面积为490 000 m²。G₁中点和边的分布不均，且包含多个度为1的点，具有一般性，其最短边长度为30 m，最长边长度为120 m，覆盖面积为494 000 m²。为了突出算法的性能，假设路网中无人机无监测障碍且忽略旋翼无人机的转弯和调头时间。按照从左到右、从下到上的顺序对路网模型中的监测点进行编号。为了分析监视权重对算法性能的影响，设置2种监视权重矩阵。一组为“标准权重”，记作S_W：在1~64中随机选取8个数，作为高优先级监视点的编号，并在(1, 2]内随机生成8个数作为高优先级监测点的监视权重，其他56个点的监视权重取1；另一组为“均一权重”，记作A_W：其中64个点的监视权重均设置为1。

设置仿真基本条件：Δt=1 s、T=10 000 s、v_r=10 m/s、R=3、t_w=1 000 s、t_lim=1 000 s、q_w=3.5。本文所有仿真结果均来自于一台CPU为Intel Core i7-7700(3.6 GHz)、显卡为Nvidia Geforce GT730(2 GB)、内存为Samsung DDR4(4 GB)的台式机上的Matlab^®2017b软件。

3.2.1 算法的准确性

为说明算法在不同覆盖范围、监视等级和路网拓扑下的普遍规律，设置4组条件。条件1：A_W & d_c=10 m，条件2：S_W & d_c=10 m，条件3：A_W & d_c=100 m，条件4：S_W & d_c=100 m。图 3和表 1展示了不同条件下的算法性能。

如图 3所示，在任一拓扑结构路网模型中，各监视点的平均不确定度均随任务时间增长而逐渐下降，在达到一个极小值后开始往复震荡，震荡域相对较小，可见达到了减小整体不确定度的效果，从而表明算法实现了不同覆盖范围的无人机组对不同监视等级的不同拓扑结构的路网区域的持续监视。

由表 1所示，比较相同监视权重、不同探测范围场景的平均不确定度情况。可见，随探测范围增加，平均不确定度的下降速度加快同时稳定后的均值降低。事实上，探测范围增加将会提高整体的监视效果。再比较相同探测范围、不同监视权重场景的平均不确定度情况。可见，监视权重的增加加大了稳定后的不确定度均值和方差。这是由于监视权重的差异打破了原有的访问均衡性，加大了无人机的轨迹随机性，使得算法性能受到影响。由此可见，算法在不同探测范围、不同监视等级和不同拓扑结构地图下所反映的规律与事实相符，表明了本文算法的准确性。

3.2.2 算法的通用性

图 3和图 4的结果表明所提算法对多机器人巡逻问题和路网持续监视问题的通用性。由图 3和图 4可见，当探测范围d_c=10 m时，均一权重场景下的无人机完成了对所有观测点的遍历，且监视点的平均不确定度趋于稳定。注意到不确定度式(4)，当监视权重传感器探测极限d_l小于各路网点间最小欧氏距离(G₁路网中任意2点间欧氏距离最小值为20 m)时，不确定度实则直接反映了各兴趣点的访问间隔时间。由此可以认为，当前普遍研究的基于间隔时间的多机器人巡逻问题是本文研究的基于传感器监视准确度的路网持续监视问题的特例。由此表明，所提算法也是对巡逻模型的一种解法，且为更一般的通用解法。

3.2.3 算法的有效性

为验证2.3节协作规则的有效性，在不同拓扑结构的路网模型中进行协同效果测试。设置3组仿真，第1组不含协作，第2组仅含第1种协作，第3组含2种协作。3组仿真分别标记为S1~S3。在“均一权重”和基本仿真条件下，分别取d_c=10 m、d_c=100 m和d_c=200 m，仿真结果如图 5所示。

如图 5所示，尽管路网模型的拓扑结构差异较大，但随着协同的加入，算法性能在不同路网模型中的变化规律相似。对比任一相同路网模型中的3组仿真结果，稳定后的最大不确定度C₂、平均不确定度均值C₃和平均不确定度方差C₄随着协同的加入均逐渐减小，说明2种协同的加入有效提高了算法的效率，并有效减少了系统随机性的影响，提高了算法的持续监视能力，使整体性能更加稳定。

3.2.4 算法的可扩展性

无人机团队存在中途加入或退出时对算法性能的影响一般也被称为算法的可扩展性，这是算法实时性能的体现。在基本仿真条件下，分别取d_c=10 m和d_c=100 m，并设置3组仿真条件，标记为S1~S3。第1组中，无人机开始有5个，运行至4 000 s时，随机选择一架使其停止运行，至7 000 s时，再随机选择一架使其停止运行；第2组中，无人机个数始终为5个；第3组中，无人机开始有5个，运行至4 000 s时，于初始位置增加一架进入任务，至7 000 s时，再于初始位置增加一架。第1组仿真用以模拟无人机失效场景，第2组模拟正常任务场景，第3组模拟增援场景。由于可扩展性并不受路网拓扑结构影响，故仅选择G₁路网进行算法的可扩展性测试。

如图 6所示，3组场景的不确定度均值C₃和最大不确定度C₂，随无人机数目增加逐渐减小，且增援场景的C₄明显小于失效场景的C₄值，说明无人机增援提升了持续监视性能。然而，尽管在增援场景中增加了无人机的个数，C₄仍高于正常任务场景下的C₄值，说明无人机数目变化增加了对持续监视系统的扰动。以上分析表明，算法实现了在无人机数目变化情况下的持续监视，准确反映了增援和失效场景中的监视效果变化规律，具有良好的可扩展性。

4 结论

1) 定义了无人机路网持续监视问题，建立了基于传感器监视准确度的持续监视问题模型，提出了协同持续监视轨迹规划算法。

2) 所提算法对基于间隔时间的多机器人巡逻问题和基于传感器监视准确度的路网持续监视问题具有通用性。

3) 所提算法具有离线和在线规划能力，解决了多无人机协同路网持续监视轨迹规划问题，同时也为基于图模型的持续数据采集、连续覆盖等任务提供了一种有效的解决方案。