無人機集群技術-智能組網(wǎng)與協(xié)同 課件 第8章 無人機集群任務分配

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

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

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

各個目標上不同類型的任務之間必須滿足的時序約束條件②

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

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

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

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

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

34PSO算法PSO算法在無人機集群中的應用場景

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

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

8.337遺傳算法遺傳算法

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

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

隨機生成大小為Npop的種群；③

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

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

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

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

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

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

計算新個體的適應值；⑩將擴展的種群最差的S個個體刪除，使其恢復原來種群的大?。?

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

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

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

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

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

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

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

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

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

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

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

安排該架無人機返航并著陸。②

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

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

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

對該編隊小組的無人機進行任務再分配。⑤

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

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

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

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

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

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

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

8.4

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

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

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

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

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

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

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

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

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

8.4

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