图源摄图网

摘要：无人机技术的发展使其在边境巡逻监测任务中承担了重要角色，而无人机续航时间的限制、多类型的越境方以及越境方的观测行为等现实因素对无人机巡逻策略的制定提出了新的难题。针对上述问题，首先构建了由多架无人机构成的巡逻方和多个越境方之间的Stackelberg安全博弈模型，其中巡逻策略和越境策略是基于所设计的有向图来描述的；进一步证明了巡逻策略与有向图上边际覆盖量之间的等价关系，进而将原博弈模型转化为了有向图最优边际覆盖的线性规划问题，并设计了两阶段映射算法；最后在仿真实验中，通过一个具体实例阐述了边际覆盖量到混合策略的转化过程，并在生成的数据集上从模型求解效率、巡逻策略的有效性和鲁棒性三方面进行了对比实验.实验结果表明转化后的模型能够有效应对指数级规模的巡逻策略给博弈求解带来的计算挑战，且能够给出具有较高质量以及较强鲁棒性的巡逻策略。
关键词：Stackelberg安全博弈 / 无人机 / 边境巡逻 / 非法越境活动 / 线性规划问题

一、研究背景及意义

边境巡逻作为边防安全工作的重要组成部分，其中一项关键任务是监测边境的非法越境活动。面对边境复杂的地理环境以及一些危险事件，人员，车辆等巡逻资源在巡逻过程中易发生伤亡，行动受限等情况。为了进一步加强边防安全，无人机逐渐被用于边境巡逻工作中，承担复杂环境下的巡逻任务。相对于人员，车辆等地面巡逻资源，无人机具有灵活，观测范围大等特点。然而，受到续航时间的限制，无人机并无法实时覆盖全部的边境线。此外，未知的越境方以及越境方的观测行为等也使得固定的巡逻策略难以形成有效的事先防护。如何有效规划多架无人机的巡逻顺序，制定多批次的动态巡逻计划对于提升巡逻效率，推动无人机在边境的应用至关重要。

针对多无人机边境巡逻问题中存在的多种类型的越境方以及巡逻策略会被观测的问题，本文首先构建了多无人机边境巡逻的Stackelberg安全博弈模型，其中在描述博弈双方的策略时，设计了包含边境线和巡逻时间两个因素的有向图，进而将巡逻策略和越境策略共同表示为图上的路径。然后基于节点覆盖量给出了边际覆盖量的定义，证明了其与巡逻策略之间的等价关系，将原博弈模型转化为了有向图最优边际覆盖的线性规划问题。对于线性规划问题给出的最优覆盖，进一步设计了两阶段映射算法对最优覆盖进行转化，从而生成可执行的混合策略。最后在生成的数据集上通过与现有算法以及常规巡逻策略进行对比实验来验证本文方法的有效性，并探讨了多无人机边境巡逻问题中的关键参数对巡逻策略的影响，以及这些参数在发生偏差时巡逻策略在收益方面的表现。

二、主要内容

本文所关注的问题是如何有效部署多架无人机以发现陆地边境线上潜在的非法越境活动，在这个问题中有两方参与者，一方是边境巡逻机构，本文统称为巡逻方，另一方是非法越境活动的执行者，本文统称为越境方。巡逻方计划部署一组续航时间有限的同构无人机在巡逻时间内对边境线巡逻以尽可能的发现越境方。多个越境方是完全理性的个体，其在观测巡逻策略后选择最优的越境策略，具体的越境策略是在一段时间内从边境线上的某一段通过。本文将越境方通过边境所需的时间统称为越境时间，根据越境时间的不同将多个越境方划分为不同类别，不同类别的越境方之间是相互独立的，各自的决策不受到其他类别的影响。越境方类别服从概率分布，文中假设该概率分布是先验信息。巡逻方并不知道越境方其具体的类型，但知道越境方所有可能的类型以及每种类型对应的概率。

本文将多无人机边境巡逻问题建模为Stackelberg安全博弈模型，该博弈属于不完全信息动态博弈，在巡逻方和越境方发生行动之前，自然首先决定越境方的类型以及相应类型存在的概率。博弈的第一阶段巡逻方进行决策，第二阶段多个越境方进行决策。巡逻方的目标是尽可能的发现越境方，相反越境方的目标是在通过边境时尽可能不被发现。在该博弈模型中，巡逻方在知道多个越境方的观测行为下，基于对越境策略的预测选择一个混合策略，越境方在观测巡逻策略后，选择使得自身被发现概率最小的策略。

为了更好的描述博弈双方的策略，本文首先设计了包含边境线和巡逻时间两个因素的有向图，进而将巡逻策略和越境策略共同表示为图上的路径。其中巡逻方的一个纯策略为所有无人机在有向图上的巡逻路径，巡逻方的一个混合策略为其所有纯策略的概率分布，越境方的一个纯策略为有向图上连接相同区域的一条路径，越境方的一个混合策略为其所有纯策略的概率分布。当越境方所选择的越境策略与无人机的巡逻路径有相同节点时，越境方可能被无人机发现。本文假设无人机在每个节点以一定的概率发现越境方，该发现概率与时间点以及区域均有关，这是因为天气因素以及地理环境因素均会影响无人机的监测效果。很显然无人机巡逻路径中这类节点越多，其发现越境方的可能性就会越高。因此无人机发现越境方的概率即为所有相同节点的概率和，采用累加的方式计算发现概率是因为无人机巡逻路径中的不同节点间是有关联的而非独立的，因此本文假设节点间的概率是相加的，总发现概率上限为1。巡逻方发现越境方的概率即为所有无人机发现越境方的概率和。此外考虑到不同越境方的目的不同，对于每个越境方，其成功通过边境能够获得一定的价值，同时被发现也会存在一定的损失，因此，越境方的收益即为在给定双方的策略下，其能够获得的收益值。越境方的目标是最大化其自身收益，巡逻方则相反，期望最小化越境方的收益，即双方的收益互为相反数，在此设定下，本文的博弈模型为零和博弈。

本文构建的博弈模型中，巡逻方是在每个越境方选择使得其自身收益最大化的策略来最优响应巡逻方策略的前提下，寻找使得其自身收益最大化的策略，对应于这一类博弈即寻找强Stackelberg均衡。在零和博弈的假设下，求解强Stackelberg均衡等同于求极大极小值，上述博弈问题可以转化为线性规划问题。对于线性规划问题,可以直接利用现有的求解器进行求解，前提是能够枚举出所有的纯策略。然而随着博弈规模的增大，巡逻方纯策略数量呈指数级规模增长，因此很难直接枚举出所有的策略，同时存储表示这些策略的变量对计算机的性能也提出了很高的要求。

为了应对博弈规模增大带来的计算挑战，本文采用覆盖量的概念将巡逻方的策略表示为有向图上的覆盖方案。由于无人机开始巡逻的时间点有多个，对于有向图的某些节点，可能既是出发节点又是某条路径的中间节点，因此仅计算原有向图上的覆盖量很难将这些节点的覆盖量进行拆分，并反映到不同的巡逻路径上。在原有向图基础上，本文进一步构建了原有向图的多个子图，这些子图的边际覆盖量之和等于原有向图的边际覆盖量，并证明了巡逻方的混合策略与多个子图上节点边际覆盖的等价关系。由此将原Stackelberg安全博弈模型转化为求解有向图最优边际覆盖的线性规划问题，同时给出了线性规划问题的最优解和强Stackelberg均衡解之间的等价性。对于给出的最优边际覆盖，进一步设计了两阶段映射算法将边际覆盖量转化为可执行的混合策略。

最后在生成的数据集上通过与列生成算法以及常规巡逻策略进行对比实验来验证本文方法的有效性，并探讨了多无人机边境巡逻问题中的关键参数对巡逻策略的影响，以及这些参数在发生偏差时巡逻策略在收益方面的表现。实验结果表明转化后的模型能够有效应对指数级规模的巡逻策略给博弈求解带来的计算挑战，且能够给出具有较高质量以及较强鲁棒性的巡逻策略。

三、主要结论

（1）相较于原博弈模型，转化后线性规划问题的求解效率有大幅度提升，且随着博弈规模的增加，求解效率提升的百分比也在逐渐增加，在区域数量为200，时间点数量为36时，求解时间未超过200秒； 此外，两阶段映射算法的求解效率也很高，在所有算例下的求解时间均不超过0.2秒；

（2）本文给出的巡逻策略相对于常规巡逻策略给巡逻方带来的收益更高，且在应对非完全理性越境方时，巡逻方的收益会有很大程度的提升，这也说明了本文给出的巡逻策略能够有效应对不同情形下越境方策略的变化，从而有效保障边防的安全；此外，在成本允许的情况下，可以通过增加无人机数量或延长无人机续航时间来提升无人机的巡逻效果；

（3）当模型中的参数由于实际巡逻过程中的突发状况而发生偏差时，本文给出的巡逻策略具有较强的鲁棒性，相对于本文巡逻策略其自身收益的波动值，其相比于常规巡逻策略给带来的巡逻方的收益优势更明显，这也从另一方面说明了本文给出的巡逻策略在有效应对模型参数发生偏差的同时，能够给巡逻方提供一种相对优势的巡逻策略。

四、边际贡献与未来拓展

本文研究了如何有效规划多架无人机对边境进行巡逻的问题，综合考虑越境方类型的不确定以及观测行为等影响巡逻策略的现实因素，构建了多无人机边境巡逻的Stackelberg安全博弈模型。基于对边境线和巡逻时间的离散化处理，设计了包含时间和空间因素的有向图将博弈双方的策略表示为图上的路径，并证明了巡逻方的策略与有向图上节点的边际覆盖量之间的等价关系。在此基础上，提出了有向图最优覆盖的线性规划问题对博弈模型进行转化，并设计了一种两阶段映射算法能够在短时间内根据边际覆盖量生成巡逻策略。

考虑到人的行为往往受到很多因素的影响，在未来的研究中可以进一步探讨越境方的不完全理性对巡逻方的影响。此外，无人机续航时间有限的问题仍然是一个重要的影响因素，如何将充电设施合理的部署到边防中以实现无人机的长时间巡逻也是一个值得深入研究的问题。

本文摘编自《系统工程理论与实践》第43卷第3期论文《基于Stackelberg安全博弈的多无人机边境巡逻问题研究》（点击题目链接全文）；
作者：雷星^1,2，博士研究生,研究方向:智能决策与优化；胡笑旋^1,2,3, 教授,博士,研究方向:智能互联系统工程；王国强^1,2,3, 副教授,博士,研究方向:多无人平台协同优化与智能决策；罗贺^1,2,3
        1. 合肥工业大学 管理学院, 合肥 230009;
        2. 过程优化与智能决策教育部重点实验室, 合肥 230009;
        3. 智能互联系统安徽省实验室, 合肥 230009