國家級虛擬仿真實驗教學(xué)一流本科課程《無人機(jī)集群技術(shù)》第八章無人機(jī)集群任務(wù)分配目錄8.1無人機(jī)集群的任務(wù)8.2無人機(jī)集群任務(wù)分配求解8.3集中式動態(tài)任務(wù)分配算法8.4分布式動態(tài)任務(wù)分配算法8.5本章小結(jié)8.1無人機(jī)集群的任務(wù)無人機(jī)集群任務(wù)類型8.1無人機(jī)集群的任務(wù)的定義無人機(jī)集群任務(wù)是指需要由多架無人機(jī)共同完成的任務(wù)，該任務(wù)擁有足夠的時間資源，允許多架無人機(jī)順序工作或者擁有充足的空間資源容納多架無人機(jī)同時配合工作。任務(wù)的耦合關(guān)系、任務(wù)的內(nèi)容不同，無人機(jī)集群任務(wù)的類型也有所差別。4無人機(jī)集群任務(wù)類型根據(jù)任務(wù)的耦合關(guān)系分類：緊耦合任務(wù)和松耦合任務(wù)兩類。根據(jù)任務(wù)的內(nèi)容分類：協(xié)同控制類、協(xié)同工作類和搜索偵查類三類。依據(jù)系統(tǒng)協(xié)作執(zhí)行任務(wù)時，無人機(jī)之間的關(guān)系分類：競爭關(guān)系與合作關(guān)系兩類。8.15無人機(jī)集群任務(wù)分配問題描述結(jié)合無人機(jī)任務(wù)分配的實際情況，可以把UAV任務(wù)分配問題定義為：基于一定的環(huán)境知識（如任務(wù)目標(biāo)位置、威脅區(qū)域位置等），綜合考慮無人機(jī)性能、到達(dá)時間、油耗、威脅及空域管制等約束條件，為集群中的各無人機(jī)分配一個或一組有序的任務(wù)集，包括目標(biāo)集合、執(zhí)行任務(wù)的類型以及不同任務(wù)的執(zhí)行順序和時間等，確保無人機(jī)集群在多任務(wù)執(zhí)行過程中的協(xié)同性，盡可能完成最多的任務(wù)，實現(xiàn)最高的無人機(jī)集群執(zhí)行任務(wù)的整體效率。8.16無人機(jī)集群任務(wù)分配問題描述任務(wù)分配問題的具體含義：首先設(shè)置了任務(wù)集和無人機(jī)集：包含四個待執(zhí)行任務(wù)、兩架無人機(jī)。然后設(shè)計具體的路徑和任務(wù)執(zhí)行順序來完成所設(shè)定的四個任務(wù)。圖中每個帶箭頭直線上方的數(shù)字表示無人機(jī)在該段航路上所花費(fèi)的時間，四個圓圈表示四個任務(wù)。圓圈斜線左邊的數(shù)字表示的無人機(jī)任務(wù)集中任務(wù)的序號，斜線右邊的數(shù)字表示完成這個任務(wù)需要的時間。一個典型的任務(wù)分配問題示意圖8.17無人機(jī)集群任務(wù)分配問題描述無人機(jī)集群任務(wù)分配描述方法：8.1一個UAV集群U包含N個無人機(jī)U={U1,U2，···，UN}。假設(shè)UAV集群在一個二維空間執(zhí)行任務(wù)，在任意時刻t，無人機(jī)U的位置為

。設(shè)每架UAV為具有恒定速度的質(zhì)點(diǎn)，無人機(jī)的屬性可以用一個七元素組來表述：＜＞表示無人機(jī)編號、位置、健康狀況、價值、任務(wù)集合、順利完成概率和最大完成數(shù)量。在任務(wù)區(qū)域內(nèi)包含有限數(shù)目的待執(zhí)行任務(wù)，組成一個任務(wù)集，NT為任務(wù)的數(shù)量，其屬性可以用一個六元素組來表述：＜＞表示目標(biāo)編號、位置、狀態(tài)、價值、威脅半徑和順利完成概率，對應(yīng)水平位置為8無人機(jī)集群任務(wù)分配問題描述無人機(jī)集群任務(wù)分配描述方法：UAV任務(wù)分配的結(jié)果是為集群中的任一無人機(jī)Ui分配一條任務(wù)執(zhí)行路線Pi有：其中表示無人機(jī)Ui的出發(fā)位置，也就是說，對應(yīng)無人機(jī)Ui需要制定一個有序任務(wù)集：8.19無人機(jī)集群任務(wù)分配問題描述8.1無人機(jī)集群任務(wù)分配的特點(diǎn)：123無人機(jī)所需處理的一般為相互耦合的復(fù)雜任務(wù)系統(tǒng)。復(fù)雜性如何保證優(yōu)先執(zhí)行目標(biāo)價值高的任務(wù)，如何在短的時間或損耗概率下，盡可能多地執(zhí)行任務(wù)，都是任務(wù)分配過程中需要考慮的問題。準(zhǔn)確性在任務(wù)環(huán)境中存在不確定性和無人機(jī)預(yù)先探測信息的不完備性，會使預(yù)先任務(wù)分配方案變得不再可行，此時就需要進(jìn)行動態(tài)的在線任務(wù)分配，這就要求任務(wù)分配算法具有較小的計算復(fù)雜度，能夠保證實時性要求。實時性10無人機(jī)集群任務(wù)分配問題描述無人機(jī)任務(wù)分配的一般原則：（1）無人機(jī)的利益最大化，最有利于任務(wù)完成的無人機(jī)，將優(yōu)先分配到任務(wù)目標(biāo)；（2）盡量縮短任務(wù)的執(zhí)行時間或者縮短無人機(jī)的總航程；（3）目標(biāo)的優(yōu)先級，那些具有較高價值的目標(biāo)應(yīng)該首先被分配執(zhí)行；（4）要考慮不同無人機(jī)之間的任務(wù)均衡性。8.111在無人機(jī)集群的任務(wù)分配中，通常需要考慮的約束條件：1.最大執(zhí)行能力無人機(jī)只有有限的任務(wù)能力，假設(shè)無人機(jī)Ui的任務(wù)執(zhí)行集合為Pi，則該任務(wù)集合的總能力消耗Q(Pi)應(yīng)小于該無人機(jī)的最大任務(wù)執(zhí)行能力

，此約束可表示為：2.最大航程受機(jī)載燃油或電源的限制，無人機(jī)只能進(jìn)行有限距離的連續(xù)飛行。假設(shè)無人機(jī)Ui的任務(wù)執(zhí)行集合為，對應(yīng)的無人機(jī)Ui的飛行總距離為Li，應(yīng)小于無人機(jī)的最大航程，此約束可表示為： 3.每個任務(wù)都能被分配到所有的任務(wù)都需要被分配執(zhí)行，此約束可表示為：無人機(jī)集群任務(wù)分配問題描述8.1125.任務(wù)時序約束在多無人機(jī)多任務(wù)分配問題中，任務(wù)之間的時序約束通常包括以下兩類：①

各個目標(biāo)上不同類型的任務(wù)之間必須滿足的時序約束條件②

不同目標(biāo)的任務(wù)之間存在的時序約束如當(dāng)Ti對Tj具有保護(hù)作用時，則對Tj的任務(wù)必須在確認(rèn)了Ti的任務(wù)完成之后才能執(zhí)行，即在無人機(jī)集群的任務(wù)分配中，通常需要考慮的約束條件：4.同一個任務(wù)不能分配給多架無人機(jī)同一個任務(wù)只能分配給一架無人機(jī)，這可以避免任務(wù)的重復(fù)執(zhí)行，對于需要多架無人機(jī)共同執(zhí)行的任務(wù)，也將其分解為多個子任務(wù)，將每個子任務(wù)分配給一架無人機(jī)。此約束可表示為：無人機(jī)集群任務(wù)分配問題描述8.113在無人機(jī)集群的任務(wù)分配中，通常需要考慮的約束條件：6.多機(jī)協(xié)同約束任務(wù)集合中的任何一個任務(wù)只能被完成一次，除非在預(yù)先的任務(wù)需求中對某個特定的目標(biāo)指定了多次任務(wù)或者該任務(wù)沒能順利完成。設(shè)xi,j∈{0,1}為決策變量，其值滿足無人機(jī)集群任務(wù)分配問題描述則多機(jī)協(xié)同約束可以表達(dá)為：

8.1通過上述描述可知，無人機(jī)集群任務(wù)分配也是具有諸多約束條件的復(fù)雜多目標(biāo)優(yōu)化問題。不同約束條件之間還存在著耦合關(guān)系，這也增加了無人機(jī)任務(wù)分配的難度。14無人機(jī)集群任務(wù)分配問題描述無人機(jī)集群的任務(wù)過程：1.離線任務(wù)預(yù)規(guī)劃：在起飛前，指揮控制中樞根據(jù)任務(wù)計劃和目標(biāo)環(huán)境信息為無人機(jī)進(jìn)行靜態(tài)環(huán)境下的最優(yōu)載荷配置、目標(biāo)分配和參考航跡規(guī)劃。2.巡航飛行：無人機(jī)集群以編隊的形式進(jìn)行巡航飛行，指揮控制中樞上的引導(dǎo)操縱員根據(jù)參考航跡和無人機(jī)集群的狀態(tài)信息。3.在線任務(wù)重規(guī)劃：在線動態(tài)調(diào)整無人機(jī)集群的任務(wù)與航跡，實現(xiàn)多無人機(jī)動態(tài)協(xié)同響應(yīng)不同的突發(fā)事件。4.任務(wù)實施：進(jìn)入目標(biāo)區(qū)域后，按照預(yù)先定義的功能角色和協(xié)同方案展開任務(wù)。5.返航：完成既定任務(wù)后，無人機(jī)集群計算剩余可用燃油（或剩余可用電量）、選擇最佳著陸點(diǎn)并規(guī)劃返航航跡。8.1158.2無人機(jī)集群任務(wù)分配求解無人機(jī)集群任務(wù)分配模型分類在任務(wù)分配與協(xié)調(diào)建模方面，通常采用的方法是對問題進(jìn)行適當(dāng)簡化后通過經(jīng)典優(yōu)化問題進(jìn)行建模。根據(jù)任務(wù)分配建模分類，現(xiàn)階段的模型主要有旅行商問題模型，通用分配問題模型，車輛路徑問題模型，混合整數(shù)線性規(guī)劃模型，多無人機(jī)協(xié)同任務(wù)分配問題模型以及隨機(jī)博弈論任務(wù)分配模型。8.217無人機(jī)集群任務(wù)分配模型分類1.多旅行商問題（MTSP）模型一般來講，泛化的MTSP問題定義為：給定n個城市集合，讓m個旅行商各自從一個城市出發(fā)，每位旅行商訪問其中一定數(shù)量的城市，最后回到其出發(fā)城市。要求每個城市至少被一位旅行商訪問一次并且只能訪問一次，問題的目標(biāo)是求得訪問m條環(huán)路的代價最小訪問次序，其中代價可以是距離、時間、費(fèi)用等。8.218無人機(jī)集群任務(wù)分配模型分類使用MTSP問題模型對無人機(jī)任務(wù)分配問題建模：假設(shè)由a架無人機(jī)構(gòu)成的無人機(jī)集群，有b個目標(biāo)任務(wù)的任務(wù)集，無人機(jī)集群從同一個基地出發(fā)，沿著預(yù)先設(shè)定的飛行航路，完成所有的任務(wù)，每個任務(wù)只能被完成一次，最后考慮無人機(jī)的總航程、無人機(jī)完成任務(wù)的時間、無人機(jī)消耗的能力、完成任務(wù)的價值利益等。該模型適用于多無人機(jī)單任務(wù)分配情形。8.21.多旅行商問題（MTSP）模型192.通用分配問題（GAP）模型通用分配問題屬于背包問題的一種，描述為將N個物品分配到M個背包中去。每個背包的容量固定，分配目標(biāo)是找到一種分配方式，使所有背包整體收益達(dá)到最大。使用GAP問題模型對無人機(jī)任務(wù)分配問題建模：考慮將m個任務(wù)分配給n架無人機(jī)，每個任務(wù)只能給一架無人機(jī)執(zhí)行并且單架無人機(jī)的資源，如最大任務(wù)數(shù)、最大航程受到限制。無人機(jī)集群任務(wù)分配模型分類8.220無人機(jī)集群任務(wù)分配模型分類3.車輛路徑問題（VRP）模型車輛路徑問題是一類具有重要實用價值的組合優(yōu)化問題，對車輛路徑模型進(jìn)行如下描述：假設(shè)有m輛貨車，每輛車的負(fù)載能力不同，它們從同一個基地出發(fā)，為n個目標(biāo)點(diǎn)輸送貨物，每個目標(biāo)點(diǎn)需要送達(dá)的貨物數(shù)量不同，最后，所有貨車回到出發(fā)點(diǎn)。車輛路徑問題模型要考慮送達(dá)的時間，貨物送達(dá)的消耗，完成輸送的價值等，并保證所有的貨物安全送達(dá)。VRP模型分為靜態(tài)VRP模型和動態(tài)VRP模型8.221無人機(jī)集群任務(wù)分配模型分類4.混合整數(shù)線性規(guī)劃（MILP）模型混合整數(shù)線性規(guī)劃是利用線性化函數(shù)建立模型，該模型描述簡潔、直接，有助于提高無人機(jī)任務(wù)執(zhí)行效率和生存能力。將多無人機(jī)對地面目標(biāo)執(zhí)行攻擊任務(wù)問題建模為MILP模型，對每個目標(biāo)必須要按序執(zhí)行確認(rèn)、打擊和評估三項任務(wù)，并且定義任務(wù)之間存在使能約束、時序約束等多種約束條件。從目標(biāo)優(yōu)化的角度出發(fā)，考慮各種約束條件建立了多無人機(jī)協(xié)同任務(wù)分配的多目標(biāo)MILP模型。該模型適用于多無人機(jī)多任務(wù)分配情形。8.222無人機(jī)集群任務(wù)分配模型分類5.多無人機(jī)協(xié)同任務(wù)分配問題（CMTAP）模型CMTAP模型適用于多無人機(jī)多任務(wù)分配情形。隨著無人機(jī)能力的不斷增強(qiáng)，無人機(jī)執(zhí)行任務(wù)的復(fù)雜程度也隨之增大，不同任務(wù)之間存在著復(fù)雜的時序以及時間約束。正是在這種背景下，CMTAP模型被提出。該模型充分考慮一組無人機(jī)完成一系列針對地面目標(biāo)的連貫任務(wù)，包括任務(wù)目標(biāo)的識別、攻擊、毀傷評估等。8.223無人機(jī)集群控制架構(gòu)1.集中式控制架構(gòu)在這種控制架構(gòu)下，集群中的無人機(jī)將收集到的外部環(huán)境信息和自身狀態(tài)信息等局部信息發(fā)送給中心控制節(jié)點(diǎn)，中心控制節(jié)點(diǎn)將所有數(shù)據(jù)進(jìn)行融合、分類得到全局信息，然后根據(jù)全局信息進(jìn)行分析和決策，將決策結(jié)果以控制指令的形式發(fā)送給各無人機(jī)。其優(yōu)點(diǎn)是分配算法實現(xiàn)簡單且具備產(chǎn)生全局最優(yōu)解的潛力。該種控制體系結(jié)構(gòu)適用于已知確定的環(huán)境，規(guī)模較小的系統(tǒng)。8.224無人機(jī)集群控制結(jié)構(gòu)集中控制存在的問題：1)實時性差當(dāng)約束條件較多、信息量較大時，任務(wù)分配的計算時間也會拉長，不易滿足實時性要求。2）魯棒性差中心控制節(jié)點(diǎn)是整個系統(tǒng)的核心決策單元，負(fù)責(zé)集群內(nèi)所有無人機(jī)的任務(wù)決策。一般情況下，中心控制節(jié)點(diǎn)只有一個，一旦該中心控制節(jié)點(diǎn)出現(xiàn)故障，則整個集群將失去執(zhí)行任務(wù)的能力，最終不可避免地導(dǎo)致任務(wù)失敗。8.225無人機(jī)集群控制結(jié)構(gòu)區(qū)別于集中式控制體系，分布式控制體系中無人機(jī)集群中的無人機(jī)是具有獨(dú)自決策能力的智能體，它們具有很強(qiáng)的協(xié)同能力和自治性。主要可以分為兩種：完全分布式控制體系結(jié)構(gòu)和部分分布式控制體系結(jié)構(gòu)。（1）完全分布式控制體系架構(gòu)完全分布式控制體系是一種依靠無人機(jī)的自主性和相互協(xié)作的一種體系結(jié)構(gòu)，在完全分布式控制體系中，把無人機(jī)看成具有決策能力的智能體，這樣無人機(jī)任務(wù)分配問題就轉(zhuǎn)化成為各個智能體之間任務(wù)的分配和決策問題。8.22.分布式控制架構(gòu)26無人機(jī)集群控制結(jié)構(gòu)（2）部分分布式控制體系架構(gòu)部分分布式控制體系吸取了無人機(jī)任務(wù)分配控制體系結(jié)構(gòu)中集中式控制和完全分布式控制體系各自的優(yōu)勢，對于多類型無人機(jī)集群任務(wù)分配問題的解決方案更為合理。而且部分分布式控制體系對集中式控制體系和分布式控制體系進(jìn)行取長補(bǔ)短，具有較大的實際應(yīng)用意義。8.227基于多智能體的分層集散式控制該控制方法借鑒多智能體系統(tǒng)（Multi-AgentSystem,MAS）的思想，將任務(wù)控制站中具有人機(jī)界面的控制系統(tǒng)和各無人機(jī)內(nèi)部的自主控制系統(tǒng)結(jié)合，建立一個分層多智能體系統(tǒng)，用于描述多類型無人機(jī)系統(tǒng)的集散式控制體系結(jié)構(gòu)，左圖為控制體系的結(jié)構(gòu)圖：8.23.基于多智能體的分層集散式控制28無人機(jī)集群控制結(jié)構(gòu)在這種結(jié)構(gòu)中，集中式控制體現(xiàn)在任務(wù)控制站中，而分布式控制體現(xiàn)在兩個方面：一是在預(yù)分配階段，二是在任務(wù)執(zhí)行階段。從控制體系結(jié)構(gòu)圖中可以看出無人機(jī)集群包含以下兩個部分：（1）集中控制層：該功能實現(xiàn)的是任務(wù)控制站中控制系統(tǒng)的集中控制功能。（2）分布式控制層：當(dāng)外部環(huán)境發(fā)生變化時，各無人機(jī)組通過TSA相互通信，重新分配任務(wù)。組內(nèi)TSA把目標(biāo)任務(wù)分解成若干子任務(wù)，然后把子任務(wù)分配給組內(nèi)的各架UAV。同時，UAV也將信息反饋給任務(wù)控制站中的指揮員。8.229集中式無人機(jī)集群動態(tài)任務(wù)分配算法8.3集中式無人機(jī)集群任務(wù)分配算法無人機(jī)集群任務(wù)分配求解方法無人機(jī)集群的任務(wù)分配定義:

基于一定的環(huán)境知識（如任務(wù)目標(biāo)位置、威脅區(qū)域位置等）和任務(wù)要求，為編隊中各架無人機(jī)分配一個或一組有序的任務(wù)集（或目標(biāo)、空間位置），以便在完成最大任務(wù)的同時，使無人機(jī)集群的整體效率達(dá)到最優(yōu)。求解無人機(jī)任務(wù)分配的有效方法是設(shè)計出能在合理的計算時間內(nèi)找到最優(yōu)或近似最優(yōu)解的算法。8.331集中式無人機(jī)集群任務(wù)分配算法典型啟發(fā)式算法集中式任務(wù)分配求解方法可以分為最優(yōu)化方法和啟發(fā)式方法。典型的最優(yōu)化方法窮舉法、整數(shù)規(guī)劃法、約束規(guī)劃法和圖論法。典型啟發(fā)式算法聚類算法、群智能類算法群智能類算法以粒子群優(yōu)化算法和遺傳算法居多。

8.332PSO算法群智能算法的具體特點(diǎn)：昆蟲群的群體行動指的是昆蟲個體根據(jù)一些規(guī)律進(jìn)行個別的運(yùn)動，從而導(dǎo)致整個群體顯現(xiàn)出一種運(yùn)動規(guī)則。在運(yùn)動中昆蟲主要遵循三個準(zhǔn)則：第一，實時監(jiān)測與鄰近個體距離，防止產(chǎn)生交叉沖突；第二，采集鄰近個體的信息，如速度、位置等；第三，保證和其他昆蟲的距離，不能太遠(yuǎn)，而脫離群體。

8.333PSO算法群智能算法的優(yōu)點(diǎn)：隨機(jī)性強(qiáng)；可以對較大規(guī)模的實際問題進(jìn)行求解；邏輯簡單，適用于簡單的任務(wù)判斷；在搜索過程中消耗的能力少。8.3群智能算法的缺點(diǎn)：實時性差，很難確定具體時間；理論依據(jù)不夠充分；得到的解不一定是最優(yōu)的；對于多類型的無人機(jī)不適用。

34PSO算法PSO算法在無人機(jī)集群中的應(yīng)用場景

現(xiàn)假設(shè)共有N架無人機(jī)和M個地面目標(biāo)，無人機(jī)數(shù)量遠(yuǎn)小于目標(biāo)數(shù)。需要對每個目標(biāo)執(zhí)行一次交互任務(wù)，因此有M個任務(wù)。每個單交互任務(wù)只需要一架無人機(jī)攻擊相應(yīng)目標(biāo)；而每個多交互任務(wù)需要多架無人機(jī)同時與相應(yīng)的目標(biāo)交互。無人機(jī)完成任務(wù)會獲得的綜合收益由交互的價值、交互時間、完成交互的飛行距離等因素決定。每架無人機(jī)的載荷有限。8.335PSO算法該場景下的約束條件：（1）飛行器執(zhí)行任務(wù)時的總航程D。（2）飛行器的載荷上限是Q。（3）飛行器的飛行路程不能超過最大航程Lmax。如何設(shè)計適應(yīng)度函數(shù)：（a）飛行器要盡可能避免發(fā)生損毀和失聯(lián)，記為飛行器損耗C。（b）飛行器要盡可能的減少資源消耗，記為航程消耗L。（c）飛行器要盡可能的與價值高的目標(biāo)進(jìn)行交互，記為交互收益H。

8.336PSO算法PSO算法求解的基本流程：①初始化一群大小為m的粒子，包括它的位置和速度。②設(shè)計適應(yīng)度函數(shù)并評價每個粒子的適應(yīng)度大小。③對每個粒子將其適應(yīng)度大小與歷史極值P作比較，如果比歷史極值好，便將它作為新的P。④根據(jù)迭代公式，改變粒子的位置和速度。⑤如達(dá)到結(jié)束條件（有足夠好的適應(yīng)值或者達(dá)到預(yù)設(shè)的迭代次數(shù)），則結(jié)束；否則，返回步驟②。⑥算法結(jié)束。

8.337遺傳算法遺傳算法

進(jìn)化理論算法的理論依據(jù)是仿照自然界中生物種群進(jìn)化過程，以優(yōu)勝劣汰的進(jìn)化原則，將相對優(yōu)秀的生物個體通過遺傳保留下來。遺傳算法是這一大類算法中使用最多、最為典型的算法。遺傳算法采用三種進(jìn)化操作：選擇操作、交叉操作和變異操作。8.338遺傳算法1.遺傳算法基本步驟：①

設(shè)置演化代數(shù)Ngen，種群規(guī)模Npop，繁殖池子大小S，交叉概率Pc，變異概率Pm；②

隨機(jī)生成大小為Npop的種群；③

評價UAV任務(wù)分配種群中的每一個個體；④

如果滿足終止，轉(zhuǎn)到第?步，否則，進(jìn)入第⑤步；⑤

利用選擇輪盤種群中選取S個個體組成繁殖池子；⑥

按交叉概率Pc，采用部分映射交叉PMX方式進(jìn)行交操作；⑦

按照變異概率Pm，進(jìn)行變異操作；8.339遺傳算法1.遺傳算法基本步驟：⑧

將新生成的個體加入種群中；⑨

計算新個體的適應(yīng)值；⑩將擴(kuò)展的種群最差的S個個體刪除，使其恢復(fù)原來種群的大??；?

轉(zhuǎn)到第④步；?

從種群中選出最好的個體作為所求航跡，進(jìn)化過程結(jié)束。8.340遺傳算法2.染色體編碼方法：染色體編碼方案：用一個長度為L的任務(wù)點(diǎn)排列表示每個種群個體，染色體的每個基因座上隨機(jī)設(shè)定一個任務(wù)點(diǎn)的序號。同時對于集群中的所有UAVi（i=1，···，NU），此染色體還對應(yīng)一個隨機(jī)產(chǎn)生的非負(fù)整數(shù)Ni的集合，集合中的元素表示該UAV分配到的任務(wù)點(diǎn)的數(shù)目，并保證 。下圖染色體表示：2個UAV組成的飛行編隊，其中UAV1按序執(zhí)行任務(wù)2-3，N1

=2；UAV2按序執(zhí)行任務(wù)1-4-5，N2

=3。8.341遺傳算法3.無人機(jī)集群任務(wù)分配問題的進(jìn)化操作：（1）選擇操作具體的執(zhí)行過程如下：①計算出種群中每一個個體的評價函數(shù)的值，得到它們的總和；②分別計算種群子個體評價函數(shù)值的相對值，即各個個體被選中作為父代遺傳到下一子代的概率；③再使用類似賭博輪盤的操作（即產(chǎn)生0-1之間的隨機(jī)數(shù)），從而分別確定每個個體被選中遺傳到下一代的概率。8.342遺傳算法3.無人機(jī)集群任務(wù)分配問題的進(jìn)化操作：（2）交叉操作由父代染色體Tx，Ty

按照PMX方法產(chǎn)生兩個新子代染色體算法步驟：

8.343遺傳算法3.無人機(jī)集群任務(wù)分配問題的進(jìn)化操作：（3）變異操作在UAV任務(wù)分配的混合搜索算法中，將細(xì)菌覓食算法中的遷徙操作作為改進(jìn)進(jìn)化算法中的變異算子使用，稱之為遷徙變異算子。遷徙變異算子首先進(jìn)行遷徙操作，以概率隨機(jī)選擇種群中評價函數(shù)值較差的染色體，作為變異的初始染色體，然后以概率Pm隨機(jī)抽取初始染色體中的一位進(jìn)行變異操作。8.344遺傳算法遺傳算法優(yōu)點(diǎn)：以評價函數(shù)值為依據(jù)進(jìn)行判斷，不需引入其他數(shù)學(xué)方法對數(shù)據(jù)進(jìn)行處理；因為有多個基因插入點(diǎn)，所以具有很強(qiáng)的隨機(jī)性；存在變異概率，可以跳出局部最優(yōu)。遺傳算法缺點(diǎn)：變異的概率很小，所以很難跳出局部最優(yōu)解而得到全局最優(yōu)解;遺傳算法由于其本質(zhì)上的隨機(jī)性，導(dǎo)致其在大規(guī)模組合優(yōu)化問題的求解

效率和精度不高。8.345無人機(jī)集群任務(wù)動態(tài)再分配無人機(jī)任務(wù)再分配的定義無人機(jī)任務(wù)再分配是指在無人機(jī)執(zhí)行任務(wù)的過程中，出現(xiàn)無人機(jī)損毀、環(huán)境變化、敵方目標(biāo)變化以及總體任務(wù)變化等情況時，無人機(jī)任務(wù)規(guī)劃系統(tǒng)對這些不確定性事件做出應(yīng)對措施。在具體環(huán)境中，環(huán)境的動態(tài)性和不確定性以及協(xié)同控制的復(fù)雜性，任務(wù)集、無人機(jī)集和環(huán)境可能隨時發(fā)生改變，所以在無人機(jī)靜態(tài)任務(wù)分配的基礎(chǔ)上，必須存在任務(wù)動態(tài)再分配機(jī)制，根據(jù)環(huán)境變化和集群狀態(tài)的變化快速調(diào)整無人機(jī)的任務(wù)計劃，以適應(yīng)復(fù)雜的任務(wù)執(zhí)行環(huán)境。8.346無人機(jī)集群的動態(tài)環(huán)境任務(wù)再分配1.任務(wù)動態(tài)再分配的觸發(fā)條件

123無人機(jī)集群在執(zhí)行任務(wù)過程中，其任務(wù)集并不一定是固定不變的。任務(wù)改變由于各種不確定因素，隊中的各架無人機(jī)可能退出任務(wù)的執(zhí)行，而它原先分配到的任務(wù)需要分配給其他無人機(jī)，這時，需要進(jìn)行任務(wù)再分配。無人機(jī)狀態(tài)改變地面控制站可在任何時刻對正在執(zhí)行的任務(wù)進(jìn)行干預(yù)而觸發(fā)任務(wù)再分配地面控制站8.347無人機(jī)集群的動態(tài)環(huán)境任務(wù)再分配2.任務(wù)動態(tài)再分配采用的策略

123此種方案如同起飛前的任務(wù)靜態(tài)分配。其優(yōu)點(diǎn)是保證了全局最優(yōu)；缺點(diǎn)是問題規(guī)模較大時，計算時間長。整個編隊的完全再分配此種方案是任務(wù)再分配針對每架無人機(jī)單獨(dú)調(diào)整，優(yōu)點(diǎn)是任務(wù)再分配快速；缺點(diǎn)是最優(yōu)性難于保證。局部調(diào)整此種方案是上述兩種方案的折中，它首先對無人機(jī)和任務(wù)進(jìn)行分組，然后進(jìn)行組內(nèi)任務(wù)再分配。分組基礎(chǔ)上的再分配8.348無人機(jī)集群的動態(tài)環(huán)境任務(wù)再分配3.任務(wù)動態(tài)再分配的流程任務(wù)分配完成后，當(dāng)條件發(fā)生變化，一些任務(wù)需要變更時，將觸發(fā)任務(wù)再分配，之后系統(tǒng)又回到穩(wěn)定狀態(tài)，等待整個系統(tǒng)任務(wù)完成或下一次再分配。整個再分配過程中系統(tǒng)狀態(tài)發(fā)生變化，同時系統(tǒng)中各執(zhí)行者的狀態(tài)也將受到影響。任務(wù)重分配流程圖8.349無人機(jī)集群的動態(tài)環(huán)境任務(wù)再分配4.任務(wù)動態(tài)再分配需要考慮的因素假設(shè)任務(wù)動態(tài)再分配只在現(xiàn)有無人機(jī)集群中進(jìn)行，即不給現(xiàn)有無人機(jī)集群增加新的無人機(jī)。這時需要考慮的因素包括以下幾點(diǎn)：編隊中現(xiàn)有可執(zhí)行任務(wù)的無人機(jī)的種類及其數(shù)量。

編隊中現(xiàn)有可執(zhí)行任務(wù)的無人機(jī)的當(dāng)前位置和續(xù)航時間。

待執(zhí)行的任務(wù)目標(biāo)位置和時間窗口。8.350無人機(jī)集群的動態(tài)環(huán)境任務(wù)再分配5.任務(wù)改變時的任務(wù)動態(tài)再分配算法（1）首先確定參加新任務(wù)的無人機(jī)；（2）被確定參加新任務(wù)的無人機(jī)停止執(zhí)行現(xiàn)行任務(wù)，原地等待；（3）選擇任務(wù)動態(tài)再分配策略；（4）對所有參加新任務(wù)的無人機(jī)指派任務(wù)和規(guī)劃航線；（5）如果規(guī)劃的新航線滿足執(zhí)行新任務(wù)的要求，則將任務(wù)集發(fā)送給對應(yīng)的無人機(jī)，并啟動執(zhí)行；（6）收到任務(wù)集后，參加新任務(wù)的無人機(jī)結(jié)束等待，并啟動執(zhí)行。8.351無人機(jī)集群的動態(tài)環(huán)境任務(wù)再分配6.無人機(jī)狀態(tài)改變時的任務(wù)再分配算法①

安排該架無人機(jī)返航并著陸。②

確定該架無人機(jī)狀態(tài)改變使該無人機(jī)不能繼續(xù)執(zhí)行的任務(wù)是哪一個任務(wù)。③

判斷該編隊小組中是否有同類無人機(jī)可以替代退出的無人機(jī)。若有，轉(zhuǎn)④；

否則，轉(zhuǎn)⑤。④

對該編隊小組的無人機(jī)進(jìn)行任務(wù)再分配。⑤

判斷是否可能從編隊中的其他小組抽調(diào)一架同類無人機(jī)替代退出的無人機(jī)。

若有，轉(zhuǎn)下一步；若無，則不能繼續(xù)按原計劃執(zhí)行該任務(wù)。⑥

涉及的兩個編隊小組進(jìn)行任務(wù)再分配。8.352分布式無人機(jī)集群動態(tài)任務(wù)分配算法8.4分布式無人機(jī)集群動態(tài)任務(wù)分配算法分布式控制體系在分布式控制體系中，無人機(jī)集群內(nèi)部或者無人機(jī)集群之間的每一架無人機(jī)都是具有獨(dú)自決策能力的智能體，它們具有很強(qiáng)的協(xié)同能力和自治性。無人機(jī)之間以數(shù)據(jù)鏈技術(shù)為支撐，對無人機(jī)所處環(huán)境信息，任務(wù)目標(biāo)集信息，無人機(jī)狀態(tài)信息進(jìn)行交互，綜合考慮各種因素，提出具體的解決任務(wù)分配問題的方案和具體步驟。無人機(jī)個體在分布式控制體系下具有實時性較強(qiáng)、抗干擾能力強(qiáng)、計算量小、計算復(fù)雜度小等優(yōu)點(diǎn)，且其主要適用于動態(tài)環(huán)境，中等至大規(guī)模系統(tǒng)中。8.454分布式無人機(jī)集群任務(wù)分配無人機(jī)的任務(wù)分配問題與市場機(jī)制中的資源分配有一定的相似性。市場中有許多客戶，每個客戶依據(jù)自己的投資能力和預(yù)期效益對市場中的項目進(jìn)行投資，個別客戶個體無法改變整個市場的走勢，但是把所有的客戶看作一個統(tǒng)一的大集合，就可以通過投資對整個市場的走勢產(chǎn)生決定性的作用，即市場的發(fā)展或者市場的消退。典型的的算法是合同網(wǎng)算法和拍賣算法。8.455基于合同網(wǎng)協(xié)議的動態(tài)任務(wù)分配合同網(wǎng)算法（ContractNetProtocol，CNP）合同網(wǎng)協(xié)議(Contractnetprotocol,CNP)是分布式環(huán)境下廣泛采用的較為成熟的協(xié)商機(jī)制。其主要思想是：當(dāng)一個任務(wù)可以被執(zhí)行時，這個任務(wù)就被公開招標(biāo)，等待執(zhí)行該任務(wù)的所有個體則參與投標(biāo)，最后中標(biāo)的個體，也就是最適合完成該任務(wù)的個體，獲得完成這個任務(wù)的合同并開始執(zhí)行。

8.456基于合同網(wǎng)協(xié)議的動態(tài)任務(wù)分配合同網(wǎng)一般有三大類任務(wù)執(zhí)行角色：招標(biāo)者、投標(biāo)者、中標(biāo)者?；诤贤W(wǎng)協(xié)議的任務(wù)分配主要過程：

招標(biāo)階段：招標(biāo)者發(fā)送任務(wù)信息給投標(biāo)者，包括任務(wù)數(shù)量、任務(wù)完成期限等；

投標(biāo)階段：投標(biāo)者對招標(biāo)者發(fā)送的任務(wù)信息實時監(jiān)測，并對感興趣的任務(wù)進(jìn)行投標(biāo)；

中標(biāo)階段：招標(biāo)者在一定的時間段內(nèi)對所收集的應(yīng)標(biāo)進(jìn)行評估，根據(jù)評估結(jié)果向其滿意的投標(biāo)者分配任務(wù)；簽約階段：招標(biāo)者向中標(biāo)者發(fā)送中標(biāo)信息，中標(biāo)者確認(rèn)招標(biāo)者提出的任務(wù)分配合同，形成承諾監(jiān)督關(guān)系。合同網(wǎng)協(xié)議的原理8.457基于合同網(wǎng)協(xié)議的動態(tài)任務(wù)分配

8.4

58基于合同網(wǎng)協(xié)議的動態(tài)任務(wù)分配兩種經(jīng)典的應(yīng)用在多無人機(jī)任務(wù)分配中的買賣合同：（1）基于買賣合同的任務(wù)分配8.4

59基于合同網(wǎng)協(xié)議的動態(tài)任務(wù)分配

8.460基于合同網(wǎng)協(xié)議的動態(tài)任務(wù)分配

8.461基于合同網(wǎng)協(xié)議的動態(tài)任務(wù)分配

8.462基于合同網(wǎng)協(xié)議的動態(tài)任務(wù)分配

8.463基于合同網(wǎng)協(xié)議的動態(tài)任務(wù)分配合同網(wǎng)協(xié)議應(yīng)用無人機(jī)集群多任務(wù)動態(tài)分配中的具體方法（1）當(dāng)無人機(jī)集群中的某架無人機(jī)者有任務(wù)需要時，則啟動一個任務(wù)招標(biāo)。（2）在啟動招標(biāo)前，該無人機(jī)首先生成一個帶權(quán)重的損失向量，然后這個損失向量被廣播給所有無人機(jī)作為參考，即向潛在投標(biāo)無人機(jī)發(fā)布任務(wù)請求。（3）其他所有收到任務(wù)請求信息的潛在投標(biāo)無人機(jī)檢索自己的預(yù)定路線，也計算出一個自己的損失函數(shù)，作為“投標(biāo)值”發(fā)還給招標(biāo)者無人機(jī)。（4）招標(biāo)者無人機(jī)設(shè)定一個時間期限，選出一個最優(yōu)者作為中標(biāo)者無人機(jī)，并通知其接受任務(wù)。如果在給定時間內(nèi)最優(yōu)者由于種種原因沒有回應(yīng)，則發(fā)給次優(yōu)者，以此類推。8.464基于合同網(wǎng)協(xié)議的動態(tài)任務(wù)分配合同網(wǎng)協(xié)議應(yīng)用無人機(jī)集群多任務(wù)動態(tài)分配中的具體方法（5）一旦中標(biāo)的投標(biāo)者無人機(jī)回應(yīng)了招標(biāo)者無人機(jī)，則該任務(wù)的執(zhí)行權(quán)就由招標(biāo)者交給了中標(biāo)者無人機(jī)，即建立了相應(yīng)的合同。按合同執(zhí)行任務(wù)的中標(biāo)者無人機(jī)若不能獨(dú)立完成任務(wù)，就需扮演投標(biāo)者角色，將任務(wù)繼續(xù)分解，并按合同網(wǎng)方式進(jìn)行分配。8.465基于拍賣算法的實時任務(wù)分配拍賣算法的本質(zhì)是模擬實際的拍賣過程，其中參與拍賣的各個個體都是一個智能體。在拍賣開始前，參與拍賣的各個個體計算每一個任務(wù)的收益、消耗的能力和選擇函數(shù)等。拍賣算法首先隨機(jī)生成一個競拍的先后次序，各個個體按照次序去完成自己拍賣得到的任務(wù)集，一輪拍賣完成后得到一個整體的任務(wù)分配方案。重復(fù)多輪拍賣過程，直到時間和資源超出限制，得到當(dāng)前的最優(yōu)解。拍賣算法原理8.466基于拍賣算法的實時任務(wù)分配拍賣算法首先要解決的是競拍機(jī)制的制訂為方便描述，假定無人機(jī)完成任務(wù)方案可以表示為Pj=(Pj1

，Pj2，···，Pji）為一個有序集，i表示有序集Pj

中元素的個數(shù)。競拍中，主要考慮下面兩個函數(shù)（1）預(yù)期效益函數(shù)：

其中，ρi,jk表示無人機(jī)Ui完成任務(wù)Pjk的概率；σjk表示任務(wù)的重要程度。8.467基于拍賣算法的實時任務(wù)分配

8.4

68基于拍賣算法的實時任務(wù)分配無人機(jī)集群分布協(xié)同拍賣目標(biāo)任務(wù)分配的流程：（1）拍賣開始前，所有競拍者構(gòu)建拍賣任務(wù)列表；（2）拍賣主持者生成隨機(jī)的本輪次競拍次序；（3）拍賣過程中各競拍者按照生成的競拍次序出價，每個競拍者記錄拍賣完成后本輪次任務(wù)分配總代價和執(zhí)行關(guān)系；（4）計算拍賣生成的方案目標(biāo)函數(shù)，將最優(yōu)方案替換為本輪結(jié)果方案；8.469基于拍賣算法的實時任務(wù)分配無人機(jī)集群分布協(xié)同拍賣目標(biāo)任務(wù)分配的流程：（5）如果時間和資源約束允許，轉(zhuǎn)到第（2）步，否則轉(zhuǎn)第（6）步；（6）輸出拍賣后最低總代價的任務(wù)方案和競拍者與任務(wù)的執(zhí)行關(guān)系。8.470基于拍賣算法的實時任務(wù)分配市場類算法的主要優(yōu)點(diǎn)拍賣方法雖然不是確定