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

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

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

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

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

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

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

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

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

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

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

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

8.336PSO算法PSO算法求解的基本流程：①初始化一群大小為m的粒子，包括它的位置和速度。②設(shè)計(jì)適應(yīng)度函數(shù)并評(píng)價(jià)每個(gè)粒子的適應(yīng)度大小。③對(duì)每個(gè)粒子將其適應(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)化原則，將相對(duì)優(yōu)秀的生物個(gè)體通過遺傳保留下來(lái)。遺傳算法是這一大類算法中使用最多、最為典型的算法。遺傳算法采用三種進(jìn)化操作：選擇操作、交叉操作和變異操作。8.338遺傳算法1.遺傳算法基本步驟：①

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

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

評(píng)價(jià)UAV任務(wù)分配種群中的每一個(gè)個(gè)體；④

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

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

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

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

將新生成的個(gè)體加入種群中；⑨

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

8.456基于合同網(wǎng)協(xié)議的動(dòng)態(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)者對(duì)招標(biāo)者發(fā)送的任務(wù)信息實(shí)時(shí)監(jiān)測(cè)，并對(duì)感興趣的任務(wù)進(jìn)行投標(biāo)；

中標(biāo)階段：招標(biāo)者在一定的時(shí)間段內(nèi)對(duì)所收集的應(yīng)標(biāo)進(jìn)行評(píng)估，根據(jù)評(píng)估結(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é)議的動(dòng)態(tài)任務(wù)分配

8.4

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

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

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

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

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

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

，Pj2，···，Pji）為一個(gè)有序集，i表示有序集Pj

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

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

8.4

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