基于改进合同网的无人机群协同实时任务分配问题研究

    张梦颖 王蒙一 王晓东 宋勋

    DOI：10.12132/ISSN.1673-5048.2019.0153

    摘要：在未来的信息化战争中，战场环境日益复杂且瞬息万变，无人机群的任务分配结果需要根据战场信息的改变迅速做出响应。针对无人机群协同实时任务分配问题，提出改进合同网算法。通过招标者参与投标策略，将招标者作为基准筛选优质的投标者;引入并发机制，使多个任务可以同时进行拍卖。所提算法提高了协商效率，减少了通信量和通信频率。仿真结果表明，基于并发的合同网算法能够快速有效处理复杂战场中出现的各种突发情况，满足实时任务分配的要求。

    关键词：改进合同网算法;无人机群;实时;任务分配;武器协同技术

    中图分类号：TJ765;V279文献标识码：A文章编号：1673-5048（2019）04-0038-09

    0引言

    合同网自提出以来被广泛应用于分布式系统中，成为了一种有效的多Agent协调机制[1]。近年来，合同网模型应用在生产调度、多无人机任务分配和多机器人系统协作等方面，都取得了显著的成果[2]。文献[3]提出适合异构水下多机器人协同任务分配的改进合同网模型，将任务负载率指标和令牌环网概念结合起来，有效解决选择招标者及其任务不合理的问题。文献[4]提出一种分布估计量子遗传算法（ED-QGA），用于初始全局最优分配，当出现突发动态任务时，采用合同网进行分配方案的局部调整。文献[5]提出基于合同网任务分配模型的带双向筛选机制的动态任务分配方法，以减少协商过程的通信开销。合同网在类似的任务分配问题中有很好的表现，本文针对无人机群协同任务分配的特点，使用改进合同网对无人机群协同实时任务分配问题进行研究。

    1无人机群协同实时任务分配问题描述与建模

    1.1战场突发情况分析

    无人机群协同实时任务分配是由于战场突发情况导致原本的任务分配方案无法执行。战场突发情况是任务实时分配的触发条件[6]。对无人机群协同实时任务分配问题进行分析，首先要对战场突发情况进行分析。一般来说，无人机群协同作战的过程中，需要重新进行任务分配的情况有以下几种：

    （1）未知目标的出现

    任务预分配目标的确定是基于前期的侦察结果，不能保证覆盖整个区域内的所有目标，因此，战场环境中存在未知目标。在无人机群任务执行过程中，地面站观测区域出现新的目标或者无人机侦察设备检测到新的目标都会导致任务集的增加，需要分配合适的无人機去执行新任务。

    5结论

    针对无人机群协同实时任务分配问题，本文提出改进合同网算法：

    （1）招标者参与投标。通过招标者参与投标策略，将招标者作为基准筛选优质的投标者，提高协商效率，减少各节点的运算量和通信量。

    （2）引入并发机制使多个任务可以同时进行拍卖，减少拍卖回合，提高协商效率，减少了通信频率。

    改进的合同网算法能够快速有效处理复杂战场中出现的各种突发情况，满足实时任务分配的要求，但仍存在以下问题：

    （1）没有考虑通信范围。受限于实际传感器通信范围，并不能实现所有无人机之间的全范围通信，在后续研究中可以考虑。

    （2）没有考虑通信延时。在实际战场情况中，无人机之间的通信存在延时情况，导致无人机进行拍卖时不能同时收到所有标书，对延时情况下的合同网研究也非常必要。

    参考文献：

    [1]YeungWL.EfficiencyofTaskAllocationBasedonContractNetProtocolwithAudienceRestrictioninaManufacturingControlApplication[J].InternationalJournalofComputerIntegratedManufacturing，2018，31（10）：1005-1017.

    [2]秦久峰，曾凡明，陈于涛，等.基于改进合同网的多Agent系统协作机理研究[J].武汉理工大学学报：交通科学与工程版，2014，38（5）：1065-1069.

    QinJiufeng，ZengFanming，ChenYutao，etal.ResearchonCooperationMechanismofMultiAgentSystemBasedonImprovedContractNet[J].JournalofWuhanUniversityofTechnology：TransportationScience&Engineering，2014，38（5）：1065-1069.（inChinese）

    [3]李娟，张昆玉.基于改进合同网算法的异构多AUV协同任务分配[J].水下无人系统学报，2017，25（6）：418-423.

    LiJuan，ZhangKunyu.HeterogeneousMultiAUVCooperativeTaskAllocationBasedonImprovedContractNetAlgorithm[J].JournalofUnmannedUnderseaSystems，2017，25（6）：418-423.（inChinese）

    [4]刘振，李伟，任建存，等.多基地多UCAV任务分配建模及求解方法[J].东南大学学报：自然科学版，2019，49（1）：88-93.

    LiuZhen，LiWei，RenJiancun，etal.ModelingofMultiBaseMultiUCAVTaskAllocationandItsSolvingMethod[J].JournalofSoutheastUniversity：NaturalScienceEdition，2019，49（1）：88-93.（inChinese）

    [5]刘政强，陈寿元，邵增珍，等.多机器人追捕中带双向筛选的动态任务分配算法研究[J].小型微型计算机系统，2017，38（7）：1568-1572.

    LiuZhengqiang，ChenShouyuan，ShaoZengzhen，etal.ResearchonDynamicTaskAllocationAlgorithmwithBilateralSelectiveinMultiRobotCapture[J].JournalofChineseComputerSystems，2017，38（7）：1568-1572.（inChinese）

    [6]McArthurSDJ，DavidsonEM.ConceptsandApproachesinMultiAgentSystemsforPowerApplications[C]∥Proceedingsofthe13thInternationalConferenceonIntelligentSystemsApplicationtoPowerSystems，Arlington，2005.

    [7]刘刚，王瑛，张发，等.合同网协议协商机制收敛性与收敛速率分析[J].控制与决策，2014，29（6）：1027-1034.

    LiuGang，WangYing，ZhangFa，etal.ConvergenceandConvergentRateAnalysisofContractNetProtocolNegotiationMechanism[J].ControlandDecision，2014，29（6）：1027-1034.（inChinese）

    [8]CannyJF.TheComplexityofRobotMotionPlanning[M].Cambridge：TheMITPress，1988.

    [9]NilssonNJ.ArtificialIntelligence：ANewSynthesis[M].SanFrancisco：MorganKaufmannPublishers，Inc.，1998.

    [10]SzczerbaRJ，GalkowskiP，GlickteinIS，etal.RobustAlgorithmforRealTimeRoutePlanning[J].IEEETransactionsonAerospace&ElectronicSystems，2000，36（3）：869-878.

    [11]DaSilveiraLR，TanscheitR，VellascoMMBR.QuantumInspiredEvolutionaryAlgorithmforOrderingProblems[J].ExpertSystemswithApplications，2017，67：71-83.

    [12]郭智杰，糜玉林，肖陽，等.改进合同网协议在防空武器目标分配中的应用[J].现代防御技术，2017，45（4）：104-111.

    GuoZhijie，MiYulin，XiaoYang，etal.ApplicationofImprovedContractNetProtocolonWeaponTargetAssignmentofAirDefenseCombat[J].ModernDefenseTechnology，2017，45（4）：104-111.（inChinese）

    [13]郭超，熊伟，刘呈祥.合同网协议改进研究现状与展望[J].装备学院学报，2016，27（6）：82-89.

    GuoChao，XiongWei，LiuChengxiang.ProspectsandCurrentResearchesonImprovementofContractNetProtocol[J].JournalofEquipmentAcademy，2016，27（6）：82-89.（inChinese）

    [14]李新亮，翟江涛，戴跃伟.动态环境下基于改进合同网的多Agent任务分配算法[J].科学技术与工程，2013，13（27）：8014-8019.

    LiXinliang，ZhaiJiangtao，DaiYuewei.ATaskAllocationAlgorithmBaseonImprovedContractNetProtocolundertheDynamicEnvironment[J].ScienceTechnologyandEngineering，2013，13（27）：8014-8019.（inChinese）