(沈陽航空航天大學(xué) 自動(dòng)化學(xué)院，沈陽 110136)
本文摘自《沈陽航空航天大學(xué)學(xué)報(bào)》
摘要：任務(wù)分配是無人機(jī)完成軍事任務(wù)的重要保證，是任務(wù)規(guī)劃的重要組成部分，一直是無人機(jī)作戰(zhàn)系統(tǒng)的重要研究課題。首先介紹了無人機(jī)任務(wù)分配的基本概念，然后分別從集中式分配、分布式分配和分層次分布式分配等研究方法對(duì)無人機(jī)任務(wù)分配進(jìn)行了綜述，最后分析了無人機(jī)任務(wù)分配的關(guān)鍵技術(shù)以及未來的發(fā)展趨勢(shì)，分別從異構(gòu)多類型無人機(jī)的協(xié)同任務(wù)分配、不確定條件下的任務(wù)分配、靜態(tài)博弈、動(dòng)態(tài)博弈、動(dòng)態(tài)實(shí)時(shí)任務(wù)分配、多要素綜合任務(wù)分配等方面說明了還需要進(jìn)一步研究與解決的關(guān)鍵問題。
關(guān)鍵詞：任務(wù)分配；集中式；分布式；分層次分布式
無人機(jī)即由自己控制或者地面操作人員操控的無人駕駛飛機(jī)[1-2]。隨著科學(xué)技術(shù)的不斷發(fā)展，戰(zhàn)場(chǎng)形勢(shì)的日趨嚴(yán)峻，無人機(jī)在現(xiàn)代戰(zhàn)爭(zhēng)中的作戰(zhàn)優(yōu)勢(shì)越發(fā)明顯，所以得到越來越多國(guó)家軍事高層的青睞。任務(wù)分配是根據(jù)既定的目標(biāo)把需要完成的任務(wù)合理地分派給系統(tǒng)中的組員，達(dá)到高效率執(zhí)行任務(wù)、優(yōu)化無人機(jī)系統(tǒng)的目的[3]。
目前，學(xué)者們的研究重點(diǎn)是多架同構(gòu)、異構(gòu)無人機(jī)組成的無人機(jī)編隊(duì)協(xié)同執(zhí)行任務(wù)[4-12]。在編隊(duì)中，每架無人機(jī)的性質(zhì)、作用、有效載荷、作戰(zhàn)能力等各方面都有差異，滿足各種約束的條件下，最大效率地將全部作戰(zhàn)任務(wù)合理分配給無人機(jī)編隊(duì)，使系統(tǒng)的各種性能指標(biāo)盡可能達(dá)到極值，發(fā)揮無人機(jī)編隊(duì)協(xié)同工作效能，這是無人機(jī)編隊(duì)作戰(zhàn)系統(tǒng)的重要研究課題。文獻(xiàn)[5]探索了對(duì)不同種類的目標(biāo)進(jìn)行偵察、打擊和評(píng)估任務(wù)時(shí)異構(gòu)無人機(jī)的協(xié)同任務(wù)分配問題。對(duì)于偵察與評(píng)估任務(wù)中所得到的信息量，運(yùn)用信息論中熵的變化量對(duì)其進(jìn)行度量，把無人機(jī)對(duì)不同類型目標(biāo)的打擊能力簡(jiǎn)化為對(duì)目標(biāo)的毀傷概率，同時(shí)把每個(gè)任務(wù)之間的關(guān)聯(lián)性考慮在內(nèi)，建立了異構(gòu)多無人機(jī)協(xié)同任務(wù)分配模型。文獻(xiàn)[6]歸納和總結(jié)了多無人機(jī)協(xié)同任務(wù)規(guī)劃的國(guó)內(nèi)外研究現(xiàn)狀，重點(diǎn)總結(jié)了任務(wù)分配方法的常見模型和算法，對(duì)各種算法的優(yōu)缺點(diǎn)進(jìn)行了討論，得出多智能體的市場(chǎng)機(jī)制類算法在空戰(zhàn)中將有廣泛的應(yīng)用價(jià)值。文獻(xiàn)[7]建立了以合同網(wǎng)協(xié)議和多智能體系統(tǒng)理論為基礎(chǔ)的有人機(jī)/無人機(jī)編隊(duì)MAS(Multi-agent System,MAS)結(jié)構(gòu)和基于投標(biāo)過程的無人機(jī)任務(wù)分配模型。文獻(xiàn)[8]在無人機(jī)協(xié)同多任務(wù)分配的研究中，運(yùn)用了基于分工機(jī)制的蟻群算法進(jìn)行求解，并給出了基于作戰(zhàn)任務(wù)能力評(píng)估的問題解構(gòu)造策略和基于作戰(zhàn)任務(wù)代價(jià)的狀態(tài)轉(zhuǎn)移規(guī)則，大幅度提升了算法的性能。文獻(xiàn)[9]以異構(gòu)類型多目標(biāo)多無人機(jī)任務(wù)分配問題為原型，設(shè)計(jì)了一種基于時(shí)間窗的多無人機(jī)聯(lián)盟組任務(wù)分配方法，此算法使用沖突消解機(jī)制來防止無人機(jī)實(shí)時(shí)任務(wù)分配過程中出現(xiàn)多機(jī)資源死鎖，其次通過無人機(jī)兩階段任務(wù)聯(lián)盟構(gòu)成算法，組成了任務(wù)聯(lián)盟，使無人機(jī)任務(wù)分配的有效性和實(shí)時(shí)性有了很大的提高。文獻(xiàn)[10]在基于任務(wù)依賴關(guān)系和ISO-DATA(Iterative Self-organizing Data Analysis Technique)算法相結(jié)合的基礎(chǔ)上設(shè)計(jì)了新的任務(wù)分組方法，在保持無人機(jī)負(fù)載均衡的基礎(chǔ)上，給出了基于資源福利的任務(wù)組級(jí)組粗粒度的無人機(jī)任務(wù)分配方法，在任務(wù)組內(nèi)提出了結(jié)合粒子群算法的細(xì)粒度任務(wù)分配算法。文獻(xiàn)[11]設(shè)計(jì)出一種多無人機(jī)任務(wù)分配與航跡規(guī)劃相結(jié)合的整體控制架構(gòu)，假設(shè)威脅和障礙區(qū)域?yàn)楹侠淼亩噙呅文Ｐ停褂酶倪M(jìn)的算法求出兩個(gè)航跡點(diǎn)之間的最短路徑，將此路徑當(dāng)成任務(wù)分配過程全局目標(biāo)函數(shù)的輸入，然后用粒子群優(yōu)化任務(wù)分配迭代尋優(yōu)。文獻(xiàn)[12]詳細(xì)分析了實(shí)際戰(zhàn)場(chǎng)上信息的不確定性，同時(shí)指出了在此條件下多無人機(jī)面臨的任務(wù)分配問題。將收益毀傷代價(jià)指標(biāo)、目標(biāo)價(jià)值及航程代價(jià)指標(biāo)的不確定信息作為參考依據(jù)，在此基礎(chǔ)上建立了基于區(qū)間信息環(huán)境下多無人機(jī)的任務(wù)分配模型，采用隨機(jī)概率的多屬性方案排序(Stochastic Multi-criteria Acceptability Analysis，SMAA)方法，得出不確定環(huán)境下多無人機(jī)動(dòng)態(tài)任務(wù)分配求解方法。
無人機(jī)任務(wù)分配有多種分類方式，按照無人機(jī)作戰(zhàn)任務(wù)之間的相關(guān)聯(lián)性，可歸類為協(xié)同任務(wù)分配和獨(dú)立任務(wù)分配[13]；按照無人機(jī)作戰(zhàn)任務(wù)所處的環(huán)境，又可歸類為靜態(tài)任務(wù)分配和動(dòng)態(tài)任務(wù)分配[14]。本文分別從集中式任務(wù)分配、分布式任務(wù)分配和分層次分布式任務(wù)分配三種分類方式論述無人機(jī)任務(wù)分配問題的研究現(xiàn)狀。
1 集中式任務(wù)分配方法
集中式控制系統(tǒng)就是編隊(duì)中的無人機(jī)之間的通信、信號(hào)的傳輸和控制均由唯一的一個(gè)控制中心來進(jìn)行。以集中式控制系統(tǒng)為基礎(chǔ)進(jìn)行任務(wù)分配最常用的模型有多旅行商問題(Multiple Traveling Salesman Problem，MTSP)模型[15]、車輛路徑問題(Vehicle Routing Problem，VRP)模型[16]、混合整數(shù)線性規(guī)劃問題(Mixed-Integer Linear Programming，MILP)模型[17]、動(dòng)態(tài)網(wǎng)絡(luò)流優(yōu)化(Dynamic Network Flow Optimization，DNFO)模型[18]、多處理器資源分配問題(Multiple Processors Resource Allocation，CMTAP)模型[19]等。
集中式求解方法還能夠進(jìn)一步分為最優(yōu)化方法和啟發(fā)式方法[20]，其中最優(yōu)化方法包括窮舉法(寬度優(yōu)先或深度優(yōu)先)、整數(shù)規(guī)劃、約束規(guī)劃、圖論方法等。如果問題有解，基于某些假設(shè)的基礎(chǔ)上，最優(yōu)化方法可以確保給出問題的最優(yōu)解。但是，因?yàn)槿蝿?wù)分配及協(xié)同規(guī)劃問題的NP特性，問題規(guī)模越大，最優(yōu)化方法的求解難度越大，時(shí)間耗費(fèi)也越長(zhǎng)。不同的是，啟發(fā)式方法的目的是在可接受的時(shí)間范圍之內(nèi)計(jì)算出問題的滿意解，它在計(jì)算時(shí)間和解質(zhì)量之間進(jìn)行折中，而不強(qiáng)求問題的最優(yōu)解。啟發(fā)式方法又能夠進(jìn)一步分為傳統(tǒng)啟發(fā)式算法和智能優(yōu)化算法。
1.1 最優(yōu)化方法
(1)窮舉法指的是為了求得問題的最優(yōu)解，而列舉出可行解域內(nèi)的全部可行解。這種方法適用于離散且問題規(guī)模較小的情況，問題規(guī)模變大且解的領(lǐng)域隨之變大的情況下，使用該方法問題將會(huì)長(zhǎng)時(shí)間得不到解決。文獻(xiàn)[21]中的滿意決策(Satisficing Decision,SD)方法可用于問題規(guī)模不大的情況，它在窮舉法的基礎(chǔ)上，將不可行或效率低的解去除掉，一定程度上縮減了解的搜索空間。
(2)整數(shù)規(guī)劃方法(Mixed Integer Linear Programming，MIP)是根據(jù)既定的目的和目標(biāo)，通過建立目標(biāo)函數(shù)和約束條件的方法對(duì)規(guī)模較小的任務(wù)分配問題進(jìn)行解決的一種最優(yōu)化方法。矩陣作業(yè)法、單純型法、匈牙利法、分支定界法等是比較常用的整數(shù)規(guī)劃方法。文獻(xiàn)[22]應(yīng)用分支定界法解決多處理機(jī)的分配調(diào)度問題，這種方法適用于約束條件和變量數(shù)目較少的問題的求解，由于滿足不了實(shí)時(shí)性要求而不適于解決規(guī)模較大的問題。
(3)約束規(guī)劃(Constraint Programming，CP)方法由變量集和約束集兩者組成[23]，變量集內(nèi)的所有變量都有自己對(duì)應(yīng)的值域，且變量的取值也只能從其值域中選取，它是求解組合優(yōu)化問題的一種通用方法。文獻(xiàn)[24]在衛(wèi)星空間資源的管理與調(diào)度中運(yùn)用了約束規(guī)劃方法與禁忌搜索算法相結(jié)合的方法，同時(shí)文獻(xiàn)[25]還研究出了數(shù)個(gè)支持約束規(guī)劃方法運(yùn)行的工具包。
(4)圖論方法是通過圖示的方法把任務(wù)和接受任務(wù)的成員特征表述出來，同時(shí)在任務(wù)和系統(tǒng)成員之間用圖論方法建立匹配，以此設(shè)計(jì)出合理可行的任務(wù)分配方案[3]。網(wǎng)絡(luò)流模型和偶圖匹配模型是兩種經(jīng)典的圖論任務(wù)分配模型。文獻(xiàn)[26]在兩個(gè)處理器的任務(wù)分配問題中應(yīng)用了網(wǎng)絡(luò)流模型，文獻(xiàn)[27]在任務(wù)網(wǎng)絡(luò)和組織成員(agent)間的映射中應(yīng)用了偶圖匹配模型，同時(shí)表明該映射的優(yōu)勢(shì)是使得執(zhí)行任務(wù)時(shí)消耗時(shí)間最少。圖論方法可以比較清晰地表現(xiàn)出任務(wù)和系統(tǒng)成員的結(jié)構(gòu)，但對(duì)于任務(wù)的數(shù)量和系統(tǒng)成員的數(shù)量比較多的情況不能得到有效的求解，有很大的局限性。
1.2 啟發(fā)式方法
啟發(fā)式方法(heuristic methods)與最優(yōu)化方法不同，它的基本思想是在算法時(shí)間和求解結(jié)果兩者之間進(jìn)行調(diào)節(jié)，在能夠接受的時(shí)間范圍內(nèi)求得局部最優(yōu)解或滿意解。列表規(guī)劃(List Scheduling,LS)方法、聚類方法和負(fù)載均衡(Load Balancing,LB)方法是三種常見的啟發(fā)式方法。
(1)列表規(guī)劃(List Scheduling,LS)方法的步驟是首先建立任務(wù)的優(yōu)先權(quán)函數(shù)，求得任務(wù)的處理次序，然后按照求得的任務(wù)處理次序?qū)⑷蝿?wù)分派給系統(tǒng)成員。最常見的列表規(guī)劃方法有動(dòng)態(tài)列表規(guī)劃(Dynamic List Scheduling，DLS)法、多維動(dòng)態(tài)列表規(guī)劃(Multi-Dimensional Dynamic List Scheduling，MDLS)方法、多優(yōu)先級(jí)動(dòng)態(tài)列表規(guī)劃(Multi-Priority List Dynamic Scheduling，MPLDS)等。文獻(xiàn)[28]在作戰(zhàn)任務(wù)的平臺(tái)資源分配中運(yùn)用了MDLS方法，文獻(xiàn)[29]利用DSL方法解決了異構(gòu)網(wǎng)絡(luò)系統(tǒng)中的計(jì)算資源分配問題，文獻(xiàn)[30]運(yùn)用MPLDS方法實(shí)現(xiàn)了作戰(zhàn)任務(wù)的平臺(tái)資源分配。
(2)聚類方法是通過將每個(gè)任務(wù)作為一個(gè)簇進(jìn)行聚類，直到任務(wù)簇與系統(tǒng)成員數(shù)目達(dá)到一致時(shí)停止聚類的一種啟發(fā)式方法。將關(guān)鍵路徑上的任務(wù)進(jìn)行聚類，然后從任務(wù)圖中將這些已聚類任務(wù)節(jié)點(diǎn)[31]移除是一個(gè)比較常用的聚類方法。文獻(xiàn)[32]證明了聚類方法在解決多處理機(jī)資源調(diào)度的問題上有很好的應(yīng)用前景。
(3)智能優(yōu)化算法是20世紀(jì)70年代末被提出來的，近年來得到了廣泛的應(yīng)用。它是利用現(xiàn)代智能優(yōu)化算法對(duì)任務(wù)分配問題進(jìn)行優(yōu)化求解的一種優(yōu)化方法。這種方法與精確方法的全局搜索不同的是，它的目的是在能夠接受的時(shí)間范圍內(nèi)求得自己滿意的解，在求解的時(shí)間和解質(zhì)量之間進(jìn)行調(diào)節(jié)。它的優(yōu)點(diǎn)是比較容易實(shí)現(xiàn)，同時(shí)計(jì)算不是很復(fù)雜，解的質(zhì)量也比較高等。
①進(jìn)化算法。隨著計(jì)算機(jī)技術(shù)的快速發(fā)展，不斷出現(xiàn)各種進(jìn)化算法(Evolutionary Algorithm，EA)，主要有遺傳算法(Genetic Algorithm，GA)、遺傳規(guī)劃(Genetic Programming，GP)、進(jìn)化策略(Evolution Strategy，ES)、進(jìn)化規(guī)劃(Evolutionary Programming,GP)等。EA是一種具有智能性和并行性等特點(diǎn)的全局優(yōu)化算法，求解大規(guī)模問題時(shí)非常適合應(yīng)用。文獻(xiàn)[33]用遺傳算法解決面向作戰(zhàn)任務(wù)的平臺(tái)資源分配，文獻(xiàn)[34]用遺傳算法解決異構(gòu)計(jì)算系統(tǒng)的多處理機(jī)調(diào)度。許多學(xué)者針對(duì)遺傳算法容易不收斂或局部收斂的不足進(jìn)行了改進(jìn)，可以有效應(yīng)用到不同背景問題中，文獻(xiàn)[35-36]應(yīng)用了改進(jìn)的遺傳算法解決多目標(biāo)優(yōu)化問題。
②群智能算法(Swarm Intelligence Algorithm，SIA)模擬的是各種群體動(dòng)物的自組織行為，基于此，學(xué)者們發(fā)明了許多包含新功能的且具有實(shí)用價(jià)值的工具。其中最著名的群智能優(yōu)化算法是粒子群算法(Particle Swarm Optimization,PSO)和蟻群算法(Ant Colony Optimization,ACO)。蟻群算法模擬的是螞蟻?zhàn)迦翰东@食物的過程，是20世紀(jì)90年代初由意大利學(xué)者首度提出來的，在許多離散優(yōu)化問題中得到成功應(yīng)用。粒子群算法是20世紀(jì)90年代末提出的，文獻(xiàn)[37]詳細(xì)介紹了粒子群算法，剛開始僅僅是解決連續(xù)的優(yōu)化問題，現(xiàn)在已越來越多的組合優(yōu)化問題也開始應(yīng)用[38]。群智能算法的不足之處是非常容易陷入局部收斂。文獻(xiàn)[39]在工程項(xiàng)目的資源分配問題中應(yīng)用了ACO算法，文獻(xiàn)[40-44]分別對(duì)單目標(biāo)和多目標(biāo)任務(wù)分配問題進(jìn)行了優(yōu)化，在多處理器任務(wù)分配和武器分配中應(yīng)用了PSO算法。
③其他智能優(yōu)化方法還包括人工免疫(Artificial Immune，AI)算法、禁忌搜索(Tabu Search，TS)算法、模擬退火(Simulated Annealing Algorithm，SA)算法等，在任務(wù)分配中也將有較廣泛的應(yīng)用空間。
啟發(fā)式方法的優(yōu)點(diǎn)是計(jì)算效率高，同時(shí)求得的解的質(zhì)量也較高，可是基于不同的假設(shè)和約束條件需要設(shè)計(jì)新的啟發(fā)式規(guī)則，即靈活性和可拓展性比較差。上述的兩種啟發(fā)式算法雖然可以在比較短的時(shí)間內(nèi)求得問題的可行解，但卻不能保證可以求得問題的最優(yōu)解，存在一定的局限性。
2 分布式任務(wù)分配方法
分布式控制系統(tǒng)與集中式控制系統(tǒng)不同的是實(shí)現(xiàn)信號(hào)傳輸?shù)姆绞�，前者無人機(jī)還可以在編隊(duì)內(nèi)進(jìn)行通信，具有更好的靈活性。分布式控制系統(tǒng)結(jié)構(gòu)相比集中式控制系統(tǒng)結(jié)構(gòu)來說對(duì)無人機(jī)的要求更高，需要無人機(jī)具備獨(dú)立計(jì)算、分析與決策等能力�；诜植际娇刂葡到y(tǒng)結(jié)構(gòu)的任務(wù)分配方法主要有基于合同網(wǎng)市場(chǎng)競(jìng)拍機(jī)制的方法、分布式模型預(yù)測(cè)控制方法、基于蟻群算法的多無人機(jī)任務(wù)分配方法、基于粒子群優(yōu)化算法的多無人機(jī)任務(wù)分配方法等。
2.1 合同網(wǎng)方法
目前，合同網(wǎng)(ContractNet)是應(yīng)用范圍最廣的一種分布式任務(wù)分配方法，它的核心是為防止產(chǎn)生沖突，對(duì)每個(gè)問題的求解用通信的方式協(xié)商處理。文獻(xiàn)[45]介紹了合同網(wǎng)方法的提出及發(fā)展。合同網(wǎng)方法有發(fā)布者和競(jìng)標(biāo)者兩個(gè)角色，由“招標(biāo)-投標(biāo)-中標(biāo)-確認(rèn)”4個(gè)交互階段組成。在合同網(wǎng)協(xié)作方法中，系統(tǒng)成員的角色不用提前規(guī)定，任何系統(tǒng)成員可以是管理者，也可以是工作者，區(qū)別只在于成員是發(fā)布任務(wù)通知還是應(yīng)答任務(wù)通知,于是任務(wù)能夠被層次地分解分派。這種方法的缺點(diǎn)是通信量大、作為發(fā)布者的系統(tǒng)成員工作強(qiáng)度大且任務(wù)分解分配沒有有效融合等，針對(duì)這些問題，研究人員進(jìn)行了改進(jìn)和延伸，文獻(xiàn)[46-47]表明合同網(wǎng)方法可以成功地解決衛(wèi)星資源和作戰(zhàn)目標(biāo)等任務(wù)分配問題。
2.2 拍賣方法
拍賣方法是實(shí)現(xiàn)資源配置的一種市場(chǎng)機(jī)制，指的是買方在清楚了解拍賣規(guī)則的前提下，采用競(jìng)價(jià)的方式?jīng)Q定特定物品的價(jià)格，也就是將要拍賣的物品用公開競(jìng)價(jià)的方式轉(zhuǎn)賣給應(yīng)價(jià)最高(最低)者的一種交易方式。一個(gè)拍賣主要由參與方、拍賣品、收益函數(shù)和應(yīng)價(jià)策略4個(gè)要素組成，在無人機(jī)任務(wù)分配問題中，無人機(jī)需要執(zhí)行的任務(wù)可視為拍賣品，無人機(jī)的任務(wù)分配方和任務(wù)接受方共同組成參與者，且雙方都有各自對(duì)應(yīng)的收益函數(shù)和出價(jià)策略。拍賣方法是一種協(xié)商協(xié)議，因其規(guī)則明確且便于操作，近年來受到越來越多學(xué)者們的關(guān)注。拍賣方法用明確的規(guī)則引導(dǎo)買賣雙方進(jìn)行交互，可操作性非常強(qiáng)，能在較短時(shí)間內(nèi)將資源合理分配，得到問題的最優(yōu)解或較優(yōu)解。該方法現(xiàn)已廣泛運(yùn)用在無人機(jī)作戰(zhàn)和傳感器等資源分配問題中[48-50]。
3 分層次分布式任務(wù)分配方法
分層次分布式控制系統(tǒng)(見圖1)同時(shí)具有集中式和分布式控制系統(tǒng)結(jié)構(gòu)雙方的優(yōu)點(diǎn)，是一種混合的控制系統(tǒng)結(jié)構(gòu)。將所有的無人機(jī)根據(jù)一定的規(guī)則進(jìn)行分層和歸類，先根據(jù)類別分組，同一層次的無人機(jī)類和同一組內(nèi)的無人機(jī)選擇集中式控制系統(tǒng)結(jié)構(gòu)，不同的組和控制中心則選擇分布式控制系統(tǒng)結(jié)構(gòu)。這種控制系統(tǒng)結(jié)構(gòu)在無人機(jī)執(zhí)行作戰(zhàn)任務(wù)時(shí)，具有很大的靈活性，可以自主根據(jù)真實(shí)狀況調(diào)節(jié)與控制中心之間信息的交流量，一定程度上減少了計(jì)算時(shí)間，同時(shí)還可以根據(jù)實(shí)際戰(zhàn)場(chǎng)情況適時(shí)地調(diào)整任務(wù)分配策略，更加滿足實(shí)際戰(zhàn)場(chǎng)的要求。
圖1 分層次分布式控制系統(tǒng)結(jié)構(gòu)
4 關(guān)鍵技術(shù)及未來發(fā)展趨勢(shì)
4.1 不確定條件下的任務(wù)分配
如今的任務(wù)分配方法一般都偏重于解決確定條件下的分配問題，而在現(xiàn)實(shí)中，因?yàn)槿蝿?wù)環(huán)境的部分可觀性，還有傳感器和情報(bào)信息的誤差，未知的對(duì)抗、規(guī)劃時(shí)所依賴的環(huán)境信息等是不確定的。另外，任務(wù)分配實(shí)施的結(jié)果也可能存在誤差，這會(huì)對(duì)任務(wù)的成敗形成不可逆的影響。所以，在任務(wù)分配過程中盡可能對(duì)以上不確定性因素加以考慮，其中對(duì)信息的不確定性可以運(yùn)用概率統(tǒng)計(jì)等方法進(jìn)行處理。
4.2 異構(gòu)多類型無人機(jī)的協(xié)同任務(wù)分配
目前，多無人機(jī)協(xié)同任務(wù)分配主要是研究同類型多無人機(jī)的分配問題，即僅需要考慮多無人機(jī)對(duì)同一作戰(zhàn)目標(biāo)的不同任務(wù)之間的時(shí)序要求。但是實(shí)戰(zhàn)中，無人機(jī)任務(wù)規(guī)劃系統(tǒng)必須具有協(xié)同規(guī)劃能力，只有這樣，才能保證多個(gè)飛行平臺(tái)在時(shí)域、空域和頻域具有一致性，滿足無人機(jī)協(xié)同任務(wù)的作戰(zhàn)要求。異構(gòu)無人機(jī)系統(tǒng)非常復(fù)雜，在滿足各方面因素和約束的條件下，如何制定合理有效的作戰(zhàn)機(jī)制、體系滿足實(shí)際戰(zhàn)場(chǎng)的需求；如何在某一類型的異構(gòu)無人機(jī)數(shù)量短缺的情況下，選擇其他合適的無人機(jī)互相配合去更加有效地完成任務(wù)；異構(gòu)無人機(jī)所攜帶的作戰(zhàn)使命、傳感器、作戰(zhàn)半徑、戰(zhàn)術(shù)使命、作戰(zhàn)意圖等都不一樣，為了得到精準(zhǔn)的需求信息，如何對(duì)異構(gòu)多類型無人機(jī)載傳感器采集的信息進(jìn)行有效快速的融合；為了實(shí)現(xiàn)各種性能指標(biāo)的最優(yōu)化，如何將不同種類的任務(wù)分配給適合的異構(gòu)無人機(jī)；為滿足戰(zhàn)場(chǎng)的實(shí)際需求，指揮控制中心應(yīng)該如何派遣數(shù)量恰當(dāng)?shù)漠悩?gòu)無人機(jī)等都是將來研究多無人機(jī)協(xié)同任務(wù)分配問題必須深入考慮的方向。
4.3 動(dòng)態(tài)實(shí)時(shí)任務(wù)分配
在無人機(jī)執(zhí)行任務(wù)的過程中，當(dāng)既定目標(biāo)和外部環(huán)境發(fā)生改變時(shí)，保證任務(wù)的成功率非常重要，所以進(jìn)行實(shí)時(shí)任務(wù)規(guī)劃具有實(shí)際的研究意義。實(shí)時(shí)任務(wù)規(guī)劃不僅需要克服信息的動(dòng)態(tài)性和不確定性所帶來的影響，而且還需要在有限的時(shí)間及計(jì)算資源的條件下給出合理有效的規(guī)劃結(jié)果，使得該問題具有非常高的復(fù)雜性和求解難度。在實(shí)時(shí)的動(dòng)態(tài)任務(wù)規(guī)劃中，需要綜合考慮真實(shí)模型、簡(jiǎn)化模型、局部最優(yōu)以及全局最優(yōu)等各個(gè)方面，如何求解出合理、有效的最優(yōu)解或滿意解，還需要進(jìn)行深入的研究與探索。
4.4 靜態(tài)博弈
作戰(zhàn)環(huán)境越來越繁雜，出現(xiàn)各種各樣的無人機(jī)作戰(zhàn)方式，而多機(jī)協(xié)同作戰(zhàn)能夠?qū)崿F(xiàn)同時(shí)攻擊多個(gè)敵方目標(biāo)，具有較高的殺傷概率，因而將成為將來空中作戰(zhàn)的主流方向。然而，多無人機(jī)在執(zhí)行任務(wù)中，不僅需要考慮己方的方案策略，同時(shí)也要考慮敵方的方案策略，能否成功完成任務(wù)的關(guān)鍵問題之一是如何在雙方預(yù)選的策略集中，選擇雙方合理的決策策略，使得無人機(jī)之間能夠相互協(xié)調(diào)完成復(fù)雜任務(wù)，這將是無人機(jī)領(lǐng)域研究的重要問題。
傳統(tǒng)的無人機(jī)協(xié)同作戰(zhàn)是僅考慮己方的最優(yōu)決策問題，而博弈論是考慮雙方的最優(yōu)決策策略問題。博弈的三要素包含局中人集、局中人的策略集、局中人的支付函數(shù)。目前有關(guān)博弈策略的研究有完全信息靜態(tài)博弈和不完全信息靜態(tài)博弈，如何在全面考慮眾多約束條件情況下建立模型并且求得納什均衡解，還需要進(jìn)行深入研究與探索。
4.5 動(dòng)態(tài)博弈
無人機(jī)編隊(duì)空戰(zhàn)是多階段動(dòng)態(tài)博弈的過程。包含零和博弈和非零和博弈：零和博弈是指博弈雙方的支付值的和為零，即我方的收益等于敵方的支出；非零和博弈是指參與者雙方的支付值的和不為零，即我方的收益值不等于敵方的支付值。多無人機(jī)空戰(zhàn)動(dòng)態(tài)博弈通常包含六個(gè)要素:1)博弈的參與者，博弈的參與者為我方無人機(jī)和敵方空戰(zhàn)戰(zhàn)斗機(jī)；2)無人機(jī)空戰(zhàn)動(dòng)態(tài)博弈的策略，是指敵我雙方無人機(jī)有先后順序選擇自己的行動(dòng)策略;3)策略組合，在動(dòng)態(tài)博弈中，每個(gè)參與者行動(dòng)時(shí)都會(huì)在自己的行動(dòng)集中選擇一個(gè)行動(dòng)，一個(gè)階段選出一個(gè)行動(dòng)，這些行動(dòng)構(gòu)成一個(gè)行動(dòng)組合，而每個(gè)參與者行動(dòng)時(shí)選出一個(gè)行動(dòng)組合稱為策略組合；4)信息，包含為完美信息博弈和不完美信息博弈；5)博弈的支付，是指博弈雙方根據(jù)自己的所選策略得到的收益值；6)博弈的均衡，博弈的均衡是指所有參與者的最優(yōu)策略的組合。動(dòng)態(tài)博弈的求解存在很大的難度，隨著雙方博弈次數(shù)增加，雙方的策略組合將呈指數(shù)增長(zhǎng)，如何求解各個(gè)階段動(dòng)態(tài)博弈的納什均衡，還需要進(jìn)行深入的研究與探索。
4.6 多要素綜合任務(wù)分配
武器裝備的不斷發(fā)展和作戰(zhàn)樣式的不斷轉(zhuǎn)變，使得無人機(jī)的任務(wù)類型日趨復(fù)雜化，隨著傳感器的使用、電子干擾等眾多因素相互融合，任務(wù)規(guī)劃問題從之前單一型規(guī)劃問題轉(zhuǎn)換為考慮多個(gè)因素的綜合型問題。而各要素間相對(duì)獨(dú)立的同時(shí)還相互影響，使得規(guī)劃問題的建模與求解比較困難。如何研究有效的多要素綜合任務(wù)規(guī)劃方法，保持每個(gè)要素求解過程相對(duì)獨(dú)立的同時(shí)，用比較高的效率規(guī)劃出合理、一致的任務(wù)計(jì)劃使得整體的任務(wù)效能達(dá)到最優(yōu)，還需要進(jìn)行深入研究與探索。
5 結(jié)束語
隨著無人機(jī)任務(wù)規(guī)劃技術(shù)的發(fā)展，不斷出現(xiàn)任務(wù)分配的新理論、新方法，無人機(jī)任務(wù)規(guī)劃技術(shù)越來越成熟，研究的對(duì)象越來越復(fù)雜，研究的內(nèi)容越來越深化，研究的范圍也越來越擴(kuò)大，與實(shí)際應(yīng)用聯(lián)系越來越緊密。研究無人機(jī)任務(wù)規(guī)劃技術(shù)對(duì)提高多無人機(jī)的作戰(zhàn)效能具有極為重要的理論和實(shí)際意義。
參考文獻(xiàn)(References)：
[1]何凡,吳文海,曲建嶺.美國(guó)海軍無人機(jī)系統(tǒng)的發(fā)展現(xiàn)狀、趨勢(shì)及關(guān)鍵技術(shù)[J].飛機(jī)設(shè)計(jì)，2007，27(1):62-65.
[2]李春錦,文涇.無人機(jī)系統(tǒng)的運(yùn)行管理[M].北京:北京航空航天大學(xué)出版社,2011.
[3]馬巧云.基于多Agent系統(tǒng)的動(dòng)態(tài)任務(wù)分配研究[D].武漢:華中科技大學(xué),2006.
[4]李煒,張偉.基于粒子群算法的多無人機(jī)任務(wù)分配方法[J].控制與決策,2010,25(9):1359-1364.
[5]邸斌,周銳,丁全心.多無人機(jī)分布式協(xié)同異構(gòu)任務(wù)分配[J].控制與決策,2013,28(2):274-278.
[6]朱毅,張濤,程農(nóng),等.多 UAV協(xié)同任務(wù)規(guī)劃研究[J].系統(tǒng)仿真學(xué)報(bào),2009(20):194-199.
[7]劉躍峰,張安.有人機(jī) /無人機(jī)編隊(duì)協(xié)同任務(wù)分配方法[J].系統(tǒng)工程與電子技術(shù),2010,32(3):584-588.
[8]蘇菲,陳巖,沈林成.基于蟻群算法的無人機(jī)協(xié)同多任務(wù)分配[J].航空學(xué)報(bào),2008(29):184-191.
[9]林林,孫其博,王尚廣,等.基于時(shí)間窗的多無人機(jī)聯(lián)盟任務(wù)分配方法研究[J].電子與信息學(xué)報(bào),2013,35(8):1983-1988.
[10]譚何順,曹雷,彭輝,等.一種多無人機(jī)層次化任務(wù)分配方法[J].解放軍理工大學(xué)學(xué)報(bào)(自然科學(xué)版),2014,15(1):18-24.
[11]孫小雷,齊乃明,董程,等.無人機(jī)任務(wù)分配與航跡規(guī)劃協(xié)同控制方法[J].火力與指揮控制,2015,37(12):2772-2776.
[12]陳俠,唐婷.不確定環(huán)境下多無人機(jī)動(dòng)態(tài)任務(wù)分配方法.火力與指揮控制[J].2013,38(1):45-49.
[13]KAUSHIK R.Task allocation and scheduling of concurrent applications to multiprocessor systems[C].Electrical Engineering and Computer Sciences University of California at Berkeley,2007.
[14]BUI H,HAN X,M ANDAL S,et al.Optimization-based decision support algorithms for a team-in-loop planning experiment[C]∥Proceedings of the 2009 IEEE International Conference on System s,M an,and Cybernetics,San Antonic,TX,USA,2009:4684-4689.
[15]SECREST B R.Traveling salesman problem for surveillance mission using particel swarm optimization[D].Wright-Patterson AFB:Air Force Institute of Technology,2003.
[16]O′ROURKE K P,BAILEY T G,HILL R,et al.Dynamic routing of unmanned aerial vehicles using reactive tabusearch[J].Military Operations Research Journal,2001(6):5-30.
[17]ALIGHANBARI M.Taskassignment algorithms for teams of UAVs in dynamic environments[D].Cambridge:Massachusetts Institute of Technology,2004.
[18]NYGARD K E,CHANDLER P R,PACHTER M.Dynamic network flow optimization modles for air vehicle resourceallocation[C]//Proceedingsofthe 2001 American Control Conference,2001,3:1853-1858.
[19]ALVARO E G.Stability Analysis of Network-based Cooperative Resource Allocation Strategies[D].Columbus:Ohio State University,2003.
[20]RASMUSSEN S,CHANDLER P,MITCHELL J W,et al.Optimalvs.Heuristic assignment of cooperative autonomous unmanned air vehicles,AIAA-2003-5586[R].Reston:AIAA,2003.
[21]葉媛媛,閔春平,沈林成,等.基于滿意決策的多UAV協(xié)同目標(biāo)分配方法[J].2005,27(4):116-120.
[22]FUJITA S,M ASUKAWA M,TAGASHIRA S.A Fast Branch-and-bound schemewith an improved lower bound for solving the multiprocessor scheduling problem [C]∥In Proc.of The International Conference on Parallel and Distributed Systems(ICPADS),2002:611-616.
[23]常朝穩(wěn),李黎.基于約束規(guī)劃的旅游多車輛行程路線研究[J].計(jì)算機(jī)應(yīng)用,2006,26(12):202-204.
[24]陳英武,方炎申,李菊芳,等.衛(wèi)星任務(wù)調(diào)度問題的約束規(guī)劃模型[J].國(guó)防科技大學(xué)學(xué)報(bào),2006,28(5):126-132.
[25]EKELIN C,JONSSON J.Solving embedded system scheduling problems using constraint programming [J].In IEEE Real-Time Systems Symposium,O rlando,Florisa,USA,Nov,2000(8):26-30.
[26]STONE H.Multiprocessor scheduling with the aid of network flow A lgorithms[J].IEEE Transactions on Software Engineering,1977,SE-3(1):85-93.
[27]LEVCHUK G M,LEVCHUK Y N,PATTIPATI K R,et al.Mapping flows onto networks to optimize organizational processes [C]//Proceedings of the 7-th Command&Control Research& Technology Symposium,2002,M onterey,CA,2002.
[28]LEVCHUK,G M,LEVCHUK Y N,LUO J,et al.Normative design of organizations-part I:mission planning [J].IEEE Transactions on Systems,M an,and Cybernetics,2002,32(3):346-359.
[29]SIH G,LEE E.A Compile-time scheduling heuristic for interconnection constrained heterogeneous processor architectures [J].IEEE Transactions on Parallel and Distributed Systems,1993,4(2):175-187.
[30]陽東升,張維明,劉忠,等.戰(zhàn)役任務(wù)計(jì)劃的數(shù)學(xué)描述與求解算法研究[J].系統(tǒng)工程理論與實(shí)踐,2006,6(1):26-34.
[31]KIM S J,BROWNE J C.A general approach to mapping of parallel computation upon multiprocessor architectures [C]∥In Proceedings of the International Conference on Parallel Processing,1988.
[32]HOANG P D,RABAEY J M.Scheduling of DSP programs onto multiprocessors for maximum throughput [J].IEEE Transactions on Signal Processing,1993,41(6):2225-2235.
[33]張杰勇,姚佩陽,周翔翔等.基于DLS和GA的作戰(zhàn)任務(wù)-平臺(tái)資源匹配方法[J].系統(tǒng)工程與電子技術(shù),2012,34(5):947-954.
[34]張聰,馬義忠.異構(gòu)計(jì)算系統(tǒng)中基于遺傳算法的任務(wù)分配與調(diào)度[J].微電子學(xué)與計(jì)算機(jī)器,2004,21(6):74-79.
[35]王瑞琪,張承慧,李珂.基于改進(jìn)混沌優(yōu)化的多目標(biāo)遺傳算法[J].控制與決策,2001,26(9):1391-1397.
[36]李玥,孫建國(guó).基于遺傳算法的航空發(fā)動(dòng)機(jī)多目標(biāo)優(yōu)化PID控制[J].航空動(dòng)力學(xué)報(bào),2008,23(1):174-178.
[37]J.KENNEDY,R.EBERHART,Particle sw arm optimization[C].Proc.IEEE Int.Conf.on Neural Networks,Perth,Australia,1995:1942-1948.
[38]余廷芳，彭青華.遺傳粒子群混合算法在電廠機(jī)組負(fù)荷組合優(yōu)化中的應(yīng)用[J].電氣自動(dòng)化設(shè)備，2010，30(10):22-26.
[39]李志潔,劉向東,段曉東.改進(jìn)粒子群算法在網(wǎng)絡(luò)資源分配中的優(yōu)化[J].計(jì)算機(jī)集成制造系統(tǒng),2009,15(12):2375-2382.
[40]葉文,朱愛紅,歐陽中輝,范洪達(dá).基于混合離散粒子群算法的多無人作戰(zhàn)飛機(jī)協(xié)同目標(biāo)分配[J].兵工學(xué)報(bào),2010,31(3):331-336.
[41]施展,陳慶偉.基于改進(jìn)的多目標(biāo)量子行為粒子群優(yōu)化算法的多無人機(jī)協(xié)同任務(wù)分配[J].南京理工大學(xué)學(xué)報(bào),2012,36(6):945-951.
[42]蔣建春,汪同慶,曾素華.求解異構(gòu)并行系統(tǒng)任務(wù)分配的混合離散粒子群算法[J].控制與決策,2011,26(9):1315-1320.
[43]張新貴,武小悅.基于自適應(yīng)粒子群算法的航天測(cè)控系統(tǒng)任務(wù)可靠性分配[J].航空動(dòng)力學(xué)報(bào),2012,27(9):2147-2154.
[44]霍霄華,陳巖,朱華勇,等.多UCAV協(xié)同控制中的任務(wù)分配模型及算法[J].國(guó)防科技大學(xué)學(xué)報(bào),2006,28(3):83-88.
[45]SM ITH R G.The Contractnet Protocol:High-Level Communication and Control in a Distributed roblem Solver [J].IEEE Transaction on Computers,1980,C-29(12):1104-1113.
[46]高黎,沙基昌.基于合同網(wǎng)的分布式衛(wèi)星系統(tǒng)任務(wù)優(yōu)化分配研究[J].宇航學(xué)報(bào),2009,30(2):815-820.
[47]陳華東,王航宇,王樹宗,等.基于合同機(jī)制的協(xié)同作戰(zhàn)分布式目標(biāo)分配研究[J].系統(tǒng)仿真學(xué)報(bào),2009,21(16):5116-5119.
[48]PALMER D,KIRSCHENBAUM M,ZAJAC K,et al.Decentralized cooperative auction for multiple agent task allocation using synchronized random number cenerators[C]∥Proceedings of the 2003 IEEE /RSJ Intl Conference on Intelligent Robots and System s.LasVegas,Nevada:IEEE Press,2003:1963-1968.
[49]WOOSUN A,PARK C,PATTIPATI K,et al.HMM and auction-based formulations of ISR coordination mechanism s for the expeditionary strike group missions[C]∥Proceedings of the 14th International Command and Control Research and Technology Symposium,W ashington,D.C.,June 2009.
[50]翁楚良,陸鑫達(dá).一種基于雙向拍賣機(jī)制的計(jì)算網(wǎng)格資源分配方法[J].計(jì)算機(jī)學(xué)報(bào),2006,29(6):1004-1009.
(責(zé)任編輯：陳素清 英文審校：齊義文)
CHEN Xia,QIAO Yan-zhi
(College of Automation,Shenyang Aerospace University,Shenyang 110136,China)
Abstract：As part of mission planning,task allocation is an important guarantee for the unmanned aerial vehicle(UAV)to accomplish military tasks and has been an active research topic in UAV combat systems.First,the basic concept of UAV task allocation was introduced.Then,the task allocation of UAV was summarized from centralized,distributed and hierarchical distributed allocations.Finally,the key technologies and future development trend of UAV task allocation were analyzed.Suggestion on the future study was put forward in terms of the cooperative task allocation of heterogeneous multi-type UAV,task allocation under uncertain conditions,static game,dynamic game,dynamic real-time task allocation,and multi-factor integrated task allocation.
Key words：task allocation;centralized;distributed;hierarchical distributed
收稿日期：2016-09-25
基金項(xiàng)目：國(guó)家自然科學(xué)基金(項(xiàng)目編號(hào)：61503255);沈陽科技資助項(xiàng)目(項(xiàng)目編號(hào)：14042200，14231129)
作者簡(jiǎn)介：陳 俠(1962-),女,遼寧新民人,教授,博士(后),主要研究方向:航空航天器任務(wù)規(guī)劃,E-mail:xiachen1108@163.com。
文章編號(hào)：2095-1248(2016)06-0001-07
中圖分類號(hào)：TP391.41
文獻(xiàn)標(biāo)志碼：A
doi：10.3969/j.issn.2095-1248.2016.06.001
http://www.ah3158.cn/admin.php