基于改進合同網(wǎng)的無人機群協(xié)同實時任務(wù)分配問題研究

張夢穎 王蒙一 王曉東 宋勛

DOI：10.12132/ISSN.1673-5048.2019.0153

摘要：在未來的信息化戰(zhàn)爭中，戰(zhàn)場環(huán)境日益復(fù)雜且瞬息萬變，無人機群的任務(wù)分配結(jié)果需要根據(jù)戰(zhàn)場信息的改變迅速做出響應(yīng)。針對無人機群協(xié)同實時任務(wù)分配問題，提出改進合同網(wǎng)算法。通過招標(biāo)者參與投標(biāo)策略，將招標(biāo)者作為基準(zhǔn)篩選優(yōu)質(zhì)的投標(biāo)者;引入并發(fā)機制，使多個任務(wù)可以同時進行拍賣。所提算法提高了協(xié)商效率，減少了通信量和通信頻率。仿真結(jié)果表明，基于并發(fā)的合同網(wǎng)算法能夠快速有效處理復(fù)雜戰(zhàn)場中出現(xiàn)的各種突發(fā)情況，滿足實時任務(wù)分配的要求。

關(guān)鍵詞：改進合同網(wǎng)算法;無人機群;實時;任務(wù)分配;武器協(xié)同技術(shù)

中圖分類號：TJ765;V279文獻標(biāo)識碼：A文章編號：1673-5048（2019）04-0038-09

0引言

合同網(wǎng)自提出以來被廣泛應(yīng)用于分布式系統(tǒng)中，成為了一種有效的多Agent協(xié)調(diào)機制[1]。近年來，合同網(wǎng)模型應(yīng)用在生產(chǎn)調(diào)度、多無人機任務(wù)分配和多機器人系統(tǒng)協(xié)作等方面，都取得了顯著的成果[2]。文獻[3]提出適合異構(gòu)水下多機器人協(xié)同任務(wù)分配的改進合同網(wǎng)模型，將任務(wù)負(fù)載率指標(biāo)和令牌環(huán)網(wǎng)概念結(jié)合起來，有效解決選擇招標(biāo)者及其任務(wù)不合理的問題。文獻[4]提出一種分布估計量子遺傳算法（ED-QGA），用于初始全局最優(yōu)分配，當(dāng)出現(xiàn)突發(fā)動態(tài)任務(wù)時，采用合同網(wǎng)進行分配方案的局部調(diào)整。文獻[5]提出基于合同網(wǎng)任務(wù)分配模型的帶雙向篩選機制的動態(tài)任務(wù)分配方法，以減少協(xié)商過程的通信開銷。合同網(wǎng)在類似的任務(wù)分配問題中有很好的表現(xiàn)，本文針對無人機群協(xié)同任務(wù)分配的特點，使用改進合同網(wǎng)對無人機群協(xié)同實時任務(wù)分配問題進行研究。

1無人機群協(xié)同實時任務(wù)分配問題描述與建模

1.1戰(zhàn)場突發(fā)情況分析

無人機群協(xié)同實時任務(wù)分配是由于戰(zhàn)場突發(fā)情況導(dǎo)致原本的任務(wù)分配方案無法執(zhí)行。戰(zhàn)場突發(fā)情況是任務(wù)實時分配的觸發(fā)條件[6]。對無人機群協(xié)同實時任務(wù)分配問題進行分析，首先要對戰(zhàn)場突發(fā)情況進行分析。一般來說，無人機群協(xié)同作戰(zhàn)的過程中，需要重新進行任務(wù)分配的情況有以下幾種：

（1）未知目標(biāo)的出現(xiàn)

任務(wù)預(yù)分配目標(biāo)的確定是基于前期的偵察結(jié)果，不能保證覆蓋整個區(qū)域內(nèi)的所有目標(biāo)，因此，戰(zhàn)場環(huán)境中存在未知目標(biāo)。在無人機群任務(wù)執(zhí)行過程中，地面站觀測區(qū)域出現(xiàn)新的目標(biāo)或者無人機偵察設(shè)備檢測到新的目標(biāo)都會導(dǎo)致任務(wù)集的增加，需要分配合適的無人機去執(zhí)行新任務(wù)。

5結(jié)論

針對無人機群協(xié)同實時任務(wù)分配問題，本文提出改進合同網(wǎng)算法：

（1）招標(biāo)者參與投標(biāo)。通過招標(biāo)者參與投標(biāo)策略，將招標(biāo)者作為基準(zhǔn)篩選優(yōu)質(zhì)的投標(biāo)者，提高協(xié)商效率，減少各節(jié)點的運算量和通信量。

（2）引入并發(fā)機制使多個任務(wù)可以同時進行拍賣，減少拍賣回合，提高協(xié)商效率，減少了通信頻率。

改進的合同網(wǎng)算法能夠快速有效處理復(fù)雜戰(zhàn)場中出現(xiàn)的各種突發(fā)情況，滿足實時任務(wù)分配的要求，但仍存在以下問題：

（1）沒有考慮通信范圍。受限于實際傳感器通信范圍，并不能實現(xiàn)所有無人機之間的全范圍通信，在后續(xù)研究中可以考慮。

（2）沒有考慮通信延時。在實際戰(zhàn)場情況中，無人機之間的通信存在延時情況，導(dǎo)致無人機進行拍賣時不能同時收到所有標(biāo)書，對延時情況下的合同網(wǎng)研究也非常必要。

參考文獻：

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

[2]秦久峰，曾凡明，陳于濤，等.基于改進合同網(wǎng)的多Agent系統(tǒng)協(xié)作機理研究[J].武漢理工大學(xué)學(xué)報：交通科學(xué)與工程版，2014，38（5）：1065-1069.

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

[3]李娟，張昆玉.基于改進合同網(wǎng)算法的異構(gòu)多AUV協(xié)同任務(wù)分配[J].水下無人系統(tǒng)學(xué)報，2017，25（6）：418-423.

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

[4]劉振，李偉，任建存，等.多基地多UCAV任務(wù)分配建模及求解方法[J].東南大學(xué)學(xué)報：自然科學(xué)版，2019，49（1）：88-93.

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

[5]劉政強，陳壽元，邵增珍，等.多機器人追捕中帶雙向篩選的動態(tài)任務(wù)分配算法研究[J].小型微型計算機系統(tǒng)，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]劉剛，王瑛，張發(fā)，等.合同網(wǎng)協(xié)議協(xié)商機制收斂性與收斂速率分析[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]郭智杰，糜玉林，肖陽，等.改進合同網(wǎng)協(xié)議在防空武器目標(biāo)分配中的應(yīng)用[J].現(xiàn)代防御技術(shù)，2017，45（4）：104-111.

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

[13]郭超，熊偉，劉呈祥.合同網(wǎng)協(xié)議改進研究現(xiàn)狀與展望[J].裝備學(xué)院學(xué)報，2016，27（6）：82-89.

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

[14]李新亮，翟江濤，戴躍偉.動態(tài)環(huán)境下基于改進合同網(wǎng)的多Agent任務(wù)分配算法[J].科學(xué)技術(shù)與工程，2013，13（27）：8014-8019.

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