基于改進合同網的無人機群協同實時任務分配問題研究

張夢穎 王蒙一 王曉東 宋勛

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）