無(wú)人機(jī)組群巡檢滅火系統(tǒng)設(shè)計(jì)說(shuō)明書(shū)

1、題 目：無(wú)人機(jī)組群巡檢滅火系統(tǒng)設(shè)計(jì)學(xué)院：機(jī)電工程學(xué)院專(zhuān)業(yè)：機(jī)械設(shè)計(jì)制造及其自動(dòng)化姓 名：學(xué) 號(hào)：指導(dǎo)教師：2016年5月28日隨著無(wú)人機(jī)執(zhí)行任務(wù)的環(huán)境日益復(fù)雜，任務(wù)類(lèi)型日益多樣，無(wú)人機(jī)己經(jīng)開(kāi)始 從單架次獨(dú)立任務(wù)的方式向著多架次、多類(lèi)型的機(jī)群作戰(zhàn)方向發(fā)展。通過(guò)對(duì)多無(wú) 人機(jī)協(xié)同任務(wù)分配的研宂，可以使系統(tǒng)完成的任務(wù)類(lèi)型更為多樣，同時(shí)任務(wù)完成 的質(zhì)量和效率也獲得較大程度的提高。本文研究了集中式多類(lèi)型無(wú)人機(jī)編隊(duì)任務(wù)分配方法。集中式指的是任務(wù)分配 過(guò)程中，無(wú)人機(jī)處于從屬地位，不具有自主能力，完全受控制站中人的控制。多 類(lèi)型指的是無(wú)人機(jī)類(lèi)型和執(zhí)行能力的不同。本文首先介紹了無(wú)人機(jī)的應(yīng)用現(xiàn)狀，討論了幾種任務(wù)分配

2、算法，分析了他們 的優(yōu)缺點(diǎn)。其次，在靜態(tài)環(huán)境下基于平面網(wǎng)格坐標(biāo)系，建立了一個(gè)多無(wú)人機(jī)任務(wù) 分配數(shù)學(xué)模型，設(shè)計(jì)了一種有人參與的靜態(tài)分配算法。然后利用了一個(gè)無(wú)人機(jī)森 林滅火的實(shí)例，通過(guò)matlab仿真和分析說(shuō)明了算法的可行性和實(shí)用性。最后，在 動(dòng)態(tài)環(huán)境中，根據(jù)無(wú)人機(jī)狀態(tài)改變和任務(wù)改變兩種情況，對(duì)動(dòng)態(tài)任務(wù)進(jìn)行了動(dòng)態(tài) 重分配。關(guān)鍵字：無(wú)人機(jī)；任務(wù)分配；靜態(tài)分配；動(dòng)態(tài)重分配abstractwith the increasingly complex environment，the missions of the uav grow variously. the operational manner of u

3、av changes from the independence towards the multi-way, more types of uav. through the research of the assignation of the multi-type uav, you can make the types of completed tasks more diversely and the quality and efficiency improved greatly.this paper addresses the problem of task allocation in th

4、e centralized and multi-type uav fleets. centralized refers to in the task allocation process, uav is in a subordinate position，uav do not have independent ability，completely under control of human in control base. multi-type uav refers to the different abilities of uav.first of all，this paper intro

5、duces the present situation of the applications of uav, discussed some kinds of task allocation algorithms and analyzed their advantages and disadvantages. whats more, in a static environment, based on the planar grid coordinate system，we set up a multi-uav task allocation mathematical model and des

6、igned a static allocation algorithm with humans attended. then use an example of forest outfire to show the feasibility and practicability of the algorithm by the simulation analysis of matlab. finally, according to two situations: uav changed or tasks changed, the task allocation changes to dynamic

7、 redistribution, in dynamic environment.keywords： uav ； task allocation ; static allocation ； dynamic redistribution目錄第一章緒論371.1任務(wù)分配的研宂背景371.2國(guó)內(nèi)外無(wú)人機(jī)應(yīng)用現(xiàn)狀372. 1應(yīng)用在軍事上371.2.2應(yīng)用在自然災(zāi)害的防護(hù)上371.3論文的主要內(nèi)容371.4論文組織結(jié)構(gòu)37第二章無(wú)人機(jī)任務(wù)分配問(wèn)題研宄現(xiàn)狀及發(fā)展趨勢(shì)371無(wú)人機(jī)任務(wù)分配問(wèn)題的定義及解決步驟372.1.1 uav任務(wù)分配問(wèn)題的定義372. 1.2 uav任務(wù)分配問(wèn)題的描述372. 1.3解決u

8、av任務(wù)分配問(wèn)題的步驟372. 2無(wú)人機(jī)任務(wù)分配控制方法372.2. 1集中式控制372.2.2分布式控制373無(wú)人機(jī)任務(wù)分配模型分類(lèi)371多旅行商問(wèn)題模型372.3. 2通用分配問(wèn)題模型372.3. 3車(chē)輛路徑問(wèn)題模型372. 3. 4混合整數(shù)線性規(guī)劃模型372.3.5 cmtai）通用模型372. 4靜態(tài)任務(wù)分配算法372.4. 1群算法372. 4. 2市場(chǎng)類(lèi)算法372.4. 3進(jìn)化理論算法372. 5動(dòng)態(tài)環(huán)境中多任務(wù)重分配算法372. 5. 1合同網(wǎng)算法372.5. 2拍賣(mài)算法372. 5. 3聚類(lèi)算法37第三章靜態(tài)環(huán)境下無(wú)人機(jī)任務(wù)分配373. 1任務(wù)分配場(chǎng)景和限制條件373. 1.

9、1任務(wù)分配的場(chǎng)景371.2任務(wù)分配限制條件373. 2多無(wú)人機(jī)任務(wù)分配的數(shù)學(xué)模型373.2. 1無(wú)人機(jī)任務(wù)集描述373. 2. 2平面網(wǎng)格坐標(biāo)系37第四章動(dòng)態(tài)環(huán)境下無(wú)人機(jī)任務(wù)分配374. 1動(dòng)態(tài)任務(wù)重分配374. 1. 1動(dòng)態(tài)任務(wù)重分配的觸發(fā)條件371.2任務(wù)動(dòng)態(tài)再分配采用的策略374. 1.3任務(wù)重分配的流程374. 1.4任務(wù)動(dòng)態(tài)再分配需要考慮的因素374. 1.5任務(wù)改變時(shí)的任務(wù)動(dòng)態(tài)再分配算法374. 1.6無(wú)人機(jī)狀態(tài)改變時(shí)的任務(wù)再分配37i侖36參考文獻(xiàn)36至夂i射37第一章緒論1. 1任務(wù)分配的研究背景無(wú)人機(jī)(uninhabited aerial vehicle, uav)是指由迅程

10、遙控或自主控制操作的無(wú)人駕駛的飛機(jī)。采用無(wú)人駕駛的方式使飛機(jī)擺脫了駕駛員自身生理?xiàng)l件的限制，能夠完成一般飛機(jī)不能完成的任務(wù)。無(wú)人機(jī)具有重量輕、維護(hù)成本低、機(jī)動(dòng)性能 高等明顯優(yōu)勢(shì)，同吋無(wú)人駕駛的方式使操作人員遠(yuǎn)離危險(xiǎn)的任務(wù)環(huán)境，極大地降 低了操作人員的危險(xiǎn)程度。uav協(xié)同任務(wù)規(guī)劃是現(xiàn)代戰(zhàn)爭(zhēng)中提出的新課題。隨著無(wú)人機(jī)的出現(xiàn)，利用無(wú) 人機(jī)執(zhí)行任務(wù)逐步成為了現(xiàn)實(shí)，目前uav協(xié)同任務(wù)規(guī)劃得到了越來(lái)越多的關(guān)注， 因?yàn)楸M管單無(wú)人機(jī)可以無(wú)需合作完成某個(gè)環(huán)境的搜索，但是一個(gè)更有效的搜索需 要合作來(lái)減少重s覆蓋，通常多無(wú)人機(jī)任務(wù)規(guī)劃可以分成兩大部分：上層的任務(wù) 分配 hask assignment or task

11、 a1 locat ion)和下層的路徑規(guī)劃(path planning), 任務(wù)分配考慮各種約束條件，以總體任務(wù)有效達(dá)成為r標(biāo)，將具體目標(biāo)和行動(dòng)任務(wù)分配 給各機(jī)，而各機(jī)根裾分配的任務(wù)再進(jìn)行具體的作戰(zhàn)路徑規(guī)劃。路徑規(guī)劃的功能是 在滿足如最大線性速度、最大轉(zhuǎn)角速度、操作的安全性、時(shí)間和環(huán)境變量等自身 或外部限制的前提下在一系列位置之間設(shè)計(jì)或生成路徑。本文我們主要討論uav 任務(wù)分配w題。1. 2國(guó)內(nèi)外無(wú)人機(jī)應(yīng)用現(xiàn)狀(1) 2. 1.應(yīng)用在軍事上uav任務(wù)規(guī)劃技術(shù)主要還是應(yīng)用在軍事上。無(wú)人作戰(zhàn)飛機(jī)(uninhabited combat aerial vehicle, ucav)指的是無(wú)人機(jī)攜帶武器

12、或者彈藥，可對(duì)地面目標(biāo)進(jìn)行攻擊 和轟炸。在軍事發(fā)達(dá)國(guó)家，尤其美國(guó)、英國(guó)以及法國(guó)對(duì)無(wú)人作戰(zhàn)機(jī)研宂深入，美 國(guó)對(duì)于無(wú)人機(jī)任務(wù)分配問(wèn)題在軍事上的研究最為深入，在上世紀(jì)70年代就開(kāi)始對(duì) 無(wú)人機(jī)任務(wù)分配問(wèn)題進(jìn)行描述并進(jìn)行實(shí)際應(yīng)用。在越南戰(zhàn)爭(zhēng)，海灣戰(zhàn)爭(zhēng)以及北約空 襲南斯拉夫等過(guò)往戰(zhàn)爭(zhēng)中，無(wú)人機(jī)經(jīng)常用于執(zhí)行一些人不能完成的軍事任務(wù)。在這 些戰(zhàn)爭(zhēng)中雖然無(wú)人機(jī)不是主要執(zhí)行任務(wù)的飛機(jī)，但它卻成了決定戰(zhàn)爭(zhēng)導(dǎo)向的決定 因素之一。由于無(wú)人機(jī)的無(wú)人駕駛特點(diǎn)，可以被派往危險(xiǎn)的環(huán)境中執(zhí)行一些人不能 執(zhí)行的任務(wù)，因而成為重要的軍事力量受各國(guó)關(guān)住。無(wú)人機(jī)可以用來(lái)完成對(duì)戰(zhàn)場(chǎng)實(shí) 時(shí)的偵察和監(jiān)視、對(duì)目標(biāo)位置的確定、任務(wù)目標(biāo)的評(píng)估、電子

13、對(duì)抗等。無(wú)人機(jī)最 早的開(kāi)發(fā)是在第一次世界大戰(zhàn)之后。到了第二次世界大戰(zhàn)后，很多軍事實(shí)力較強(qiáng)的 國(guó)家將退役下來(lái)的飛機(jī)進(jìn)行改裝，使人與飛機(jī)脫離，這樣就促成了近代無(wú)人機(jī)的發(fā)展。隨著信息化技術(shù)的發(fā)展，無(wú)人機(jī)在執(zhí)行偵察任務(wù)的過(guò)程屮的作用越來(lái)越明 顯。例如，在越南戰(zhàn)爭(zhēng)期間，美國(guó)就大量使用無(wú)人機(jī)對(duì)價(jià)值較高的軍事設(shè)施和通信 設(shè)施進(jìn)行預(yù)先偵察。無(wú)人機(jī)不僅僅應(yīng)用于偵察，還應(yīng)用在具體的作戰(zhàn)任務(wù)執(zhí)行中。 在對(duì)阿富汗的戰(zhàn)爭(zhēng)巾，美國(guó)“捕食者”無(wú)人機(jī)首次發(fā)射“海爾法”導(dǎo)彈擊中地面 目稱(chēng)，打破了無(wú)人機(jī)傳統(tǒng)的作戰(zhàn)保障角色，使之成為一種作戰(zhàn)兵器1982年以色列 航空工業(yè)公司首創(chuàng)的無(wú)人機(jī)能進(jìn)行偵察、信息收集、跟蹤和相互通訊等。199

14、1年， 海灣戰(zhàn)爭(zhēng)中，美國(guó)軍方己經(jīng)推出了特別設(shè)計(jì)的，具有雷達(dá)系統(tǒng)的小型無(wú)人機(jī)為誘 餌，這種無(wú)人機(jī)在其它國(guó)家也進(jìn)行了一些研究。無(wú)人機(jī)在海灣戰(zhàn)爭(zhēng)之后很快的發(fā) 展起來(lái)并在很多任務(wù)中應(yīng)川。以美國(guó)為首的西方國(guó)家要力了增加對(duì)實(shí)現(xiàn)無(wú)人機(jī)在 戰(zhàn)爭(zhēng)的作用，將最新的高科技技術(shù)應(yīng)用到無(wú)人機(jī)的研宂和開(kāi)發(fā)當(dāng)中去，不僅增加無(wú) 人機(jī)飛行時(shí)間，提高了閣像，文字等信息的傳輸速度，還考慮了無(wú)人機(jī)具體的避開(kāi) 危險(xiǎn)區(qū)域能力，以順利完成任務(wù)。和美國(guó)等西方國(guó)家相比，我國(guó)的無(wú)人機(jī)研究水平差距還是很大。雖然國(guó)a從 80年代末開(kāi)始，對(duì)路徑規(guī)劃問(wèn)題進(jìn)行過(guò)許多研宂，發(fā)表了許多論文，但大多數(shù)的 文獻(xiàn)僅僅是對(duì)單無(wú)人機(jī)所進(jìn)行的路徑規(guī)劃問(wèn)題的研究，目的是避

15、幵無(wú)人機(jī)在飛行 過(guò)程中遇到的危險(xiǎn)區(qū)域，很少有關(guān)于無(wú)人機(jī)任務(wù)分配問(wèn)題解答的研究成果。當(dāng)前 我們國(guó)家無(wú)人機(jī)反的研究還處在起步階段。由于我國(guó)的無(wú)人機(jī)功能簡(jiǎn)單，自主能 力較差，耑要地面控制站進(jìn)行任務(wù)分配的規(guī)劃。而當(dāng)前的無(wú)人機(jī)發(fā)展趨勢(shì)是無(wú)人 機(jī)的智能化，將無(wú)人機(jī)看成一個(gè)個(gè)智能體，我國(guó)在這方面的研宂成果很少。功能 上也只能進(jìn)行簡(jiǎn)單的圖像，數(shù)字傳輸，任務(wù)分配、路徑規(guī)劃的能力很差。尚不具 備執(zhí)行復(fù)雜戰(zhàn)術(shù)任務(wù)的能力。近年來(lái)我國(guó)的國(guó)防科技大學(xué)、兩北工業(yè)大學(xué)等高等 院校和科研單位在無(wú)人機(jī)任務(wù)分配m題上也進(jìn)行了一些理論分析和實(shí)際悶題的研 宂，可以說(shuō)取得了不錯(cuò)的成就。但從現(xiàn)階段己經(jīng)得到的理論和實(shí)際成果來(lái)看，目 前我國(guó)對(duì)

16、無(wú)人機(jī)任務(wù)分配問(wèn)題的研宄還處有很多不足和局限。例如無(wú)人機(jī)的自主 性較差，無(wú)人機(jī)的決策大都是由地面控制站決定的。對(duì)于無(wú)人機(jī)所處的動(dòng)態(tài)環(huán)境 考慮不足，無(wú)人機(jī)的尺寸、吋間窗函數(shù)等考慮較少。(2) 2應(yīng)用在自然災(zāi)害的防護(hù)上和平和發(fā)展當(dāng)今世界的兩大主題，所以無(wú)人機(jī)的應(yīng)用也由軍用慢慢轉(zhuǎn)14民用。 其中最主要的民用用途是在自然災(zāi)害的防護(hù)上。2001年以來(lái)，世界各國(guó)都在大力 發(fā)展各種用途的無(wú)人飛行器。目前世界上32個(gè)國(guó)家己研制出了多種無(wú)人機(jī)。美國(guó)、 以色列、俄羅斯、北約等國(guó)家非常重視多用途無(wú)人機(jī)的研制、生產(chǎn)和應(yīng)用。森林 火災(zāi)的現(xiàn)場(chǎng)溫度高，對(duì)飛機(jī)的抗熱性能高?，F(xiàn)場(chǎng)的煙塵大，能見(jiàn)度不高，盡管有 人飛機(jī)能飛至火場(chǎng)上

17、課，飛機(jī)屮的人也不能清除地了解火場(chǎng)當(dāng)前的具體情況。這時(shí)無(wú)人機(jī)的優(yōu)勢(shì)就體現(xiàn)出來(lái)，通過(guò)在無(wú)人機(jī)上配置攝像機(jī)和數(shù)字圖像傳輸設(shè)備， 可輕易完成對(duì)火場(chǎng)的偵察，火火和火火評(píng)估。美國(guó)航天局最新研制的無(wú)人火火機(jī) “工khema"。這款無(wú)人滅火機(jī)由“捕食者b" (predator b)改進(jìn)而來(lái)?！安妒痴?b”原木是美國(guó)空軍用于戰(zhàn)時(shí)監(jiān)視和偵察的，現(xiàn)在它的改進(jìn)版“工khana”被用作另 一個(gè)領(lǐng)域，那就是森林滅火。在火場(chǎng)中，由于火勢(shì)的動(dòng)態(tài)性和不確定性以及協(xié)同 控制的復(fù)雜性，使得任務(wù)開(kāi)始后山現(xiàn)許多無(wú)法預(yù)料的情況，必須根據(jù)火場(chǎng)火勢(shì)和 編隊(duì)狀態(tài)的變化快速調(diào)整uav編隊(duì)的任務(wù)計(jì)劃，通過(guò)動(dòng)態(tài)重調(diào)度實(shí)現(xiàn)任務(wù)的

18、重分 配。我國(guó)也有無(wú)人機(jī)應(yīng)用在災(zāi)害防護(hù)上的實(shí)例lllo該實(shí)例描述了無(wú)人機(jī)在國(guó)內(nèi)地 震巾的應(yīng)用。重大自然災(zāi)害如地震、水災(zāi)、冰雪等具有突發(fā)性強(qiáng)、災(zāi)害范圍廣、破 壞性大特點(diǎn)，往往會(huì)造成重災(zāi)區(qū)信息通訊中斷和道路交通破壞，災(zāi)情信息不暢將 導(dǎo)致?lián)岆U(xiǎn)救災(zāi)盲目部署，繼而造成更大的損失和次生災(zāi)害。2008年漢川8.。級(jí)地震，極重災(zāi)區(qū)北川縣城出現(xiàn)大范圍建筑物倒塌和重大人員傷亡，通訊和交通 系統(tǒng)遭到毀滅性破壞，傳山特大災(zāi)情己是震后的第2天，在親歷和目睹漢川地震 搶險(xiǎn)救災(zāi)過(guò)程之后，全社會(huì)己經(jīng)収得共識(shí)，通過(guò)各種手段有效獲取災(zāi)情是開(kāi)展重 大自然災(zāi)害搶險(xiǎn)救災(zāi)首要問(wèn)題。漢川地震之后，在我國(guó)有一些單位應(yīng)用無(wú)人機(jī)獲 取遙感閣像，

19、進(jìn)行震害分析，做出了探索性工作。無(wú)人機(jī)組定位于獲取高分辨率 圖像，進(jìn)行災(zāi)害識(shí)別并直接應(yīng)用于搶險(xiǎn)救災(zāi)。無(wú)人機(jī)組在北川縣曲山鎮(zhèn)等地進(jìn)行 了地震災(zāi)區(qū)實(shí)驗(yàn)，并在2010年玉樹(shù)地震搶險(xiǎn)救災(zāi)工作中成功實(shí)現(xiàn)了高原災(zāi)區(qū)酋次 航空攝影，獲収的高清影像為劃分災(zāi)區(qū)范圍提供了重要的依據(jù)。本文我們著重討 論無(wú)人機(jī)在森林還火災(zāi)中的應(yīng)用。1. 3論文的主要內(nèi)容無(wú)人機(jī)如何在復(fù)雜的環(huán)境中順利地完成所需執(zhí)行的任務(wù)，并且能夠使得任務(wù) 執(zhí)行的效率最高，收獲的利益最大，付出的代價(jià)最小，是多無(wú)人機(jī)任務(wù)分配所要 考慮的問(wèn)題。本文的主要工作是通過(guò)對(duì)各種任務(wù)分配算法的研宂，引出了一種有人參與的多無(wú)人機(jī)任務(wù)分配算法并進(jìn)行了理論研究和仿真分析。主

20、要步驟是：首先 建立了一個(gè)任務(wù)分配在森林火災(zāi)防護(hù)的應(yīng)用場(chǎng)景，設(shè)置了關(guān)于實(shí)際問(wèn)題的限制條 件，然后建立了一個(gè)基于六元組的任務(wù)描述，使用了平面網(wǎng)格坐標(biāo)系對(duì)任務(wù)分配 問(wèn)題進(jìn)行建模，在以上的基礎(chǔ)了最后利用了一個(gè)無(wú)人機(jī)森林滅火的實(shí)例，通過(guò) matlab仿真結(jié)合算法說(shuō)明了該算法的可行性和實(shí)用性。因?yàn)闊o(wú)人機(jī)任務(wù)分配所 處環(huán)境是動(dòng)態(tài)的，所以對(duì)動(dòng)態(tài)環(huán)境下無(wú)人機(jī)任務(wù)重分配問(wèn)題也進(jìn)行了一些算法研 究和實(shí)例分析。(1) 4論文組織結(jié)構(gòu)本文主要介紹多無(wú)人機(jī)的任務(wù)分配算法，在介紹了傳統(tǒng)的任務(wù)分配的算法的 基礎(chǔ)上，分析了它們的優(yōu)缺點(diǎn)，引出了一種有人參與的多無(wú)人機(jī)任務(wù)分配算法，為無(wú)人機(jī)的任務(wù)分配算法提供了新的思想。并結(jié)合了一

21、個(gè)無(wú)人機(jī)在森林滅火中的 應(yīng)用實(shí)例，利用matllab進(jìn)行仿真研究。第一章：緒論。介紹了論文選題的背景，國(guó)內(nèi)外無(wú)人機(jī)任務(wù)分配的應(yīng)用現(xiàn)狀。 簡(jiǎn)述了論文的主要a容以及論文的組織結(jié)構(gòu)。第二章：無(wú)人機(jī)任務(wù)分配的現(xiàn)狀及發(fā)展趨勢(shì)。首先給出了無(wú)人機(jī)任務(wù)分配問(wèn) 題的定義并對(duì)無(wú)人機(jī)任務(wù)分配問(wèn)題進(jìn)行了描述。其次，說(shuō)明了解決任務(wù)分配問(wèn)題 的基本步驟，包括任務(wù)分配數(shù)學(xué)模型的建立和具體算法的設(shè)計(jì)。然后介紹了任務(wù) 分配的體系結(jié)構(gòu)和當(dāng)前幾種任務(wù)分配模型，接著介紹了幾種靜態(tài)任務(wù)分配算法和 動(dòng)態(tài)任務(wù)分配算法并分析了它們的優(yōu)缺點(diǎn)。最后指出了當(dāng)前無(wú)人機(jī)任務(wù)分配方法 研究存在的一些問(wèn)題。第三章：討論了靜態(tài)環(huán)境下無(wú)人機(jī)任務(wù)分配問(wèn)題。酋先

22、建立了一個(gè)無(wú)人機(jī)森 林滅火的應(yīng)用場(chǎng)景，設(shè)置了一些限制條件。在此場(chǎng)景下設(shè)計(jì)了一個(gè)六元組的任務(wù) 描述并使用平面網(wǎng)格坐標(biāo)系完成了對(duì)任務(wù)分配問(wèn)題數(shù)學(xué)模型的建立。其次，設(shè)計(jì) 了一種有人參與的多無(wú)人機(jī)任務(wù)靜態(tài)分配算法。最后應(yīng)用一個(gè)無(wú)人機(jī)森林滅火的 實(shí)例，通過(guò)matlab仿真分析，驗(yàn)證了該算法的可行性和實(shí)用性。第四章：討論了動(dòng)態(tài)環(huán)境下無(wú)人機(jī)任務(wù)分配問(wèn)題。介紹了動(dòng)態(tài)任務(wù)再分配的 觸發(fā)條件，動(dòng)態(tài)任務(wù)重分配采川的策略以及任務(wù)動(dòng)態(tài)再分配耑要考慮的因素。分 別考慮任務(wù)改變、無(wú)人機(jī)狀態(tài)改變這兩種觸發(fā)條件，設(shè)計(jì)了兩種新的動(dòng)態(tài)任務(wù)再 分配算法。結(jié)合第三章的無(wú)人機(jī)森林滅火的實(shí)例，通過(guò)matlab仿真分析，驗(yàn)證了 這兩個(gè)算法的

23、可行性和實(shí)用性。第五章：總結(jié)與展望?？偨Y(jié)了本文的主要研究工作，指山了論文中的不足之 處，并對(duì)今后的工作提出若干自己的想法。第二章無(wú)人機(jī)任務(wù)分配同題研究現(xiàn)狀及發(fā)展趨勢(shì)(2) 1無(wú)人機(jī)任務(wù)分配問(wèn)題的定義及解決步驟2. 1. 1 uav任務(wù)分配問(wèn)題的定義uav任務(wù)分配問(wèn)題可以定義為：在己經(jīng)完成uav編隊(duì)分組的基礎(chǔ)上，基于一定 的環(huán)境和任務(wù)要求，為編隊(duì)中的uav分配一個(gè)或多個(gè)有序任務(wù)，以便在完成最大 可能任務(wù)的同時(shí)，使得uav編隊(duì)的整體效率最高。我們結(jié)合圖2. 1這個(gè)簡(jiǎn)單的例子來(lái)直觀地了解任務(wù)分配問(wèn)題的具體含義：首 先設(shè)置了任務(wù)集和無(wú)人機(jī)集：其中包含了叫個(gè)待執(zhí)行任務(wù)，無(wú)人機(jī)編隊(duì)由兩架無(wú) 人機(jī)組成。然后

24、設(shè)計(jì)具體的路徑和任務(wù)執(zhí)行順序來(lái)完成所設(shè)定的叫個(gè)任務(wù)。圖中 每個(gè)帶箭頭直線上的數(shù)字表示無(wú)人機(jī)在該段航路上所花費(fèi)的時(shí)間，四個(gè)任務(wù)用四 個(gè)圓圈來(lái)表示。圓圈中上半部分的數(shù)字表示的無(wú)人機(jī)任務(wù)集中任務(wù)的序號(hào)，下半 部分的數(shù)字表示完成這個(gè)任務(wù)需要的具體吋間。最后虛實(shí)線表示的是任務(wù)分配的 具體的方案。無(wú)人機(jī)分別沿著制定的虛線完成叫個(gè)所設(shè)定的任務(wù)，通過(guò)這種方法， 花費(fèi)時(shí)間要明顯小于單架無(wú)人機(jī)。2. 1. 2 uav任務(wù)分配問(wèn)題的描述給定一個(gè)uav編隊(duì)u,它包含數(shù)目力n二的無(wú)人機(jī)，v vl.v2. . . vnu。為 簡(jiǎn)化問(wèn)題，假設(shè)uav編隊(duì)在一個(gè)二維空間執(zhí)行任務(wù)，在任意時(shí)刻t,無(wú)人機(jī)u,的位置為 (xu tyu

25、 t)。每個(gè)uav都假設(shè)為質(zhì)點(diǎn)。同時(shí)，在任務(wù)區(qū)域內(nèi)包含有限數(shù)目的待 執(zhí)行任務(wù)，組成一個(gè)任務(wù)集t 仁.tz. . . tnt, n:為任務(wù)的數(shù)量，包含 唯一的任務(wù)td,對(duì)應(yīng)水平位置為(對(duì)了)但不同的任務(wù)允許有相同的水平位置23。在任務(wù)分配 前，以上的信息都是己知的。uav任務(wù)分配的結(jié)果是為編隊(duì)屮的任一無(wú)人機(jī)u,分 配一條任務(wù)執(zhí)行路線p,有: x ,y , x'm,y'm),，xt; yt;)(2)其巾，(xo 0，y0 0)表示無(wú)人機(jī)u,的出發(fā)位置，也就是說(shuō)，對(duì)應(yīng)無(wú)人機(jī)u;需要市。定一個(gè)有序任務(wù)集。：一 t1，t2，.，界。任務(wù)分配的一般原則如下：(1) 優(yōu)先分配價(jià)值高的一般原則

26、；(2) 將目標(biāo)分配給對(duì)其最有利的uav ;(3) 在盡可能短的時(shí)間內(nèi)盡可能多地訪問(wèn)目標(biāo)，并保證uav編隊(duì)飛行總路線 最短；(4) 參與任務(wù)的各uav的任務(wù)負(fù)載盡可能均衡。2. 1. 3解決uav任務(wù)分配問(wèn)題的步驟無(wú)人機(jī)任務(wù)分配方法的求解主要分為兩方謝：任務(wù)分配模型的建立以及具體 的任務(wù)分配算法的設(shè)計(jì)：(1) uav任務(wù)分配的數(shù)學(xué)模型的建立要對(duì)無(wú)人機(jī)進(jìn)行數(shù)學(xué)建模，首先要對(duì)無(wú)人機(jī)所處的空間環(huán)境進(jìn)行描述和表達(dá)。 通常我們以一個(gè)二維或者三維的變量來(lái)定義一個(gè)無(wú)人機(jī)和目標(biāo)點(diǎn)的位罝，為簡(jiǎn)便， 一般采用二維變量。得到了無(wú)人機(jī)和目標(biāo)點(diǎn)的位置，就能得到任一無(wú)人機(jī)的任務(wù) 執(zhí)行路線。然后我們?cè)O(shè)計(jì)一個(gè)二值決策變量，如

27、果無(wú)人機(jī)完成某個(gè)任務(wù)，二值變 量就為1,如果不完成那個(gè)任務(wù)，二值變量就為0。然后要沒(méi)定無(wú)人機(jī)任務(wù)分配的約束條件，如無(wú)人機(jī)最大航程、任務(wù)時(shí)間窗約束、任務(wù)執(zhí)行的先后順序、無(wú)人機(jī) 的載荷等。(2) uav任務(wù)分配算法的設(shè)計(jì)完成了對(duì)無(wú)人機(jī)任務(wù)分配的數(shù)學(xué)建模，我們就要來(lái)設(shè)計(jì)具體的算法。設(shè)計(jì)算 法我們首先要根據(jù)以往的算法和基本概念提出算法得出的理論依據(jù)，然后決定算 法的搜索策略，以較快較好為準(zhǔn)則，確定算法的搜索策略。因?yàn)闊o(wú)人機(jī)分配問(wèn)題 要用計(jì)算機(jī)進(jìn)行運(yùn)算仿真，必須對(duì)算法進(jìn)行編碼，所以得設(shè)計(jì)算法的編碼和解碼 方式。還應(yīng)設(shè)計(jì)一個(gè)評(píng)價(jià)函數(shù)，來(lái)評(píng)價(jià)任務(wù)分配方案的好壞，我們稱(chēng)其力適應(yīng)度 函數(shù)。適應(yīng)度函數(shù)要考慮的實(shí)際

28、因素主要包栝：任務(wù)完成的時(shí)間最短，任務(wù)分配 方案得到的收益最高以及無(wú)人機(jī)消耗能力最小。最后，我們還要對(duì)算法進(jìn)行性能 分析，包括算法能否得到最優(yōu)任務(wù)分配方案，算法的效率以及算法的實(shí)時(shí)性。2. 2無(wú)人機(jī)任務(wù)分配控制方法由于無(wú)人機(jī)執(zhí)行任務(wù)環(huán)境是動(dòng)態(tài)的，不是固定不變的，所以無(wú)人機(jī)的任務(wù)分 配控制方法也應(yīng)該根據(jù)不同的任務(wù)環(huán)境而區(qū)別對(duì)待。無(wú)人機(jī)任務(wù)分配控制方法選 取對(duì)無(wú)人機(jī)執(zhí)行任務(wù)的效率和質(zhì)量有很大關(guān)系。任務(wù)分配控制方法的選取應(yīng)該考 慮以下兒個(gè)因素：任務(wù)完成的快速性，任務(wù)的實(shí)時(shí)性，任務(wù)分配的計(jì)算時(shí)間和計(jì) 算復(fù)雜度，抗干擾能力等。無(wú)人機(jī)任務(wù)分配控制方法主要可以分為集中式控制 28(centralized c

29、ontrol)以及分布式控制(distributed control)這兩種。2. 2. 1集中式控制在集屮式控制方法屮，由地而控制站屮的操作人員制定任務(wù)分配方案和無(wú)人機(jī) 具體的飛行航路，無(wú)人機(jī)本身不具備決策能力，完全按照地面控制站發(fā)出的任務(wù) 指令和航路執(zhí)行任務(wù)。圖2. 2表示了集中式體系結(jié)構(gòu)圖28:在這種控制方式下，各無(wú)人機(jī)之間的協(xié)同控制存在以下問(wèn)題：(1) 實(shí)時(shí)性差因?yàn)闊o(wú)人機(jī)本身不具備決策能力，所以地面控制站中的操作人員要根據(jù)無(wú)人 機(jī)編隊(duì)通過(guò)數(shù)據(jù)傳輸返回的無(wú)人機(jī)狀態(tài)信息，任務(wù)狀態(tài)信息以所處的環(huán)境信息等, 對(duì)任務(wù)分配問(wèn)題進(jìn)行具體的決策。無(wú)人機(jī)編隊(duì)與地面控制站保持著聯(lián)系，當(dāng)返回 的數(shù)據(jù)量很大時(shí)

30、，有可能地面控制站收到的信息是不全的或者是錯(cuò)誤的，導(dǎo)致決 策錯(cuò)誤。地面控制綜合這些信息速度較慢，導(dǎo)致決策較慢，實(shí)吋性差。(2) 計(jì)算時(shí)間長(zhǎng)，算法復(fù)雜度高對(duì)于集中式控制方法，地面控制站對(duì)所有的無(wú)人機(jī)傳來(lái)的數(shù)據(jù)信息進(jìn)行總結(jié) 和分析，信息都集屮在任務(wù)控制站屮，解決問(wèn)題的具體計(jì)算過(guò)程復(fù)雜，計(jì)算信息 多，導(dǎo)致完成任務(wù)分配的計(jì)算時(shí)間很長(zhǎng)。對(duì)于多類(lèi)型任務(wù)的無(wú)人機(jī)編隊(duì)，例如無(wú) 人機(jī)編隊(duì)中無(wú)人機(jī)能夠執(zhí)行任務(wù)種類(lèi)的不同，無(wú)人機(jī)執(zhí)行任務(wù)能力不同，此吋更 凸顯了這個(gè)h題的嚴(yán)重。(3) 抗干擾能力較差由于地而控制站往往只有一個(gè)，如果在具體任務(wù)執(zhí)行過(guò)程中，地而控制因?yàn)?某些特定因素遭到毀壞甚至癱瘓，將造成的損失是巨大的。

31、同時(shí)無(wú)人機(jī)編隊(duì)屮的 無(wú)人機(jī)失效或者發(fā)現(xiàn)新的任務(wù)目標(biāo)，在原有基礎(chǔ)上的再分配也是很相當(dāng)復(fù)雜的。2. 2. 2分布式控制區(qū)別于集中式控制方法，分布式控制方法中無(wú)人機(jī)編隊(duì)中或者無(wú)人機(jī)編隊(duì)之 間的無(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èn)題的方案和 具體步驟。較之于集中式控制方法，無(wú)人機(jī)個(gè)體在分布式控制方法下具有較強(qiáng)的 實(shí)時(shí)性，抗干擾能力，計(jì)算量小，計(jì)算復(fù)雜度小等優(yōu)點(diǎn)。當(dāng)前，分布式控制方法 主要可以分為兩種：完全分布式控制方法和部分分布式控制方法。

32、(1) 完全分布式控制完全分布式控制方法是一種依靠無(wú)人機(jī)的自主性和相互協(xié)作的一種方法，由 于無(wú)人機(jī)任務(wù)分配w題的復(fù)雜性，該方法相當(dāng)于將復(fù)雜的問(wèn)題分解成為一個(gè)個(gè)相 對(duì)簡(jiǎn)單的小叫題，對(duì)每架無(wú)人機(jī)進(jìn)行任務(wù)分配，接著就是將各個(gè)無(wú)人機(jī)的信息進(jìn) 行交互，對(duì)任務(wù)進(jìn)行整體求解。如閣2. 3所示，完全分布式控制方法屮我們把無(wú) 人機(jī)看成具有決策能力的智能體，這樣無(wú)人機(jī)任務(wù)分配問(wèn)題就轉(zhuǎn)化成為各個(gè)智能 體之間任務(wù)的分配和決策。在這種結(jié)構(gòu)中，無(wú)人機(jī)相對(duì)于集中式控制有很強(qiáng)的自 主性，能夠?qū)θ蝿?wù)集信息和自身的信息進(jìn)行采集和分析，并進(jìn)行決策，在特定的 情況下通過(guò)數(shù)據(jù)鏈與其它無(wú)人機(jī)進(jìn)行數(shù)據(jù)交互，協(xié)作完成所需執(zhí)行的任務(wù)。tf:紐

33、tf:紐戾扦s1圖2. 3完全分布式控制結(jié)構(gòu)圖這種控制方法中，無(wú)人機(jī)編隊(duì)內(nèi)各個(gè)無(wú)人機(jī)對(duì)所得到的信息進(jìn)行相互的共享, 得到所有的關(guān)于任務(wù)執(zhí)行的信息，最后整理分析所得到的信息對(duì)無(wú)人機(jī)編隊(duì)屮的 每一架任務(wù)分配任務(wù)集。由于無(wú)人機(jī)編隊(duì)屮有多架無(wú)人機(jī)，在執(zhí)行任務(wù)中可能發(fā) 生交叉沖突，即碰撞沖突，所以需要對(duì)它們進(jìn)行考慮并消除。同吋在這種控制方 法中，無(wú)人機(jī)之間是通過(guò)數(shù)據(jù)鏈技術(shù)進(jìn)行任務(wù)集數(shù)據(jù)的傳輸和共享，為的是更好 的具有任務(wù)決策的實(shí)時(shí)性，所以數(shù)據(jù)量是相當(dāng)大的，將隨著編隊(duì)內(nèi)無(wú)人機(jī)的數(shù)量 呈指數(shù)增長(zhǎng)。所以應(yīng)用這種控制方法，編隊(duì)內(nèi)無(wú)人機(jī)的個(gè)數(shù)受到了很大的限制。(2) 部分分布式控制部分分布式控制方法吸取了無(wú)人機(jī)任

34、務(wù)分配控制方法中集中式控制和完全分 布式控制方法各自的優(yōu)勢(shì)，對(duì)于解決多類(lèi)型無(wú)人機(jī)編隊(duì)任務(wù)分配問(wèn)題更為合理。經(jīng)過(guò)對(duì)集中式控制方法和分布式控制方法的比較，我們得出分布是控制方法是一 種實(shí)時(shí)性較強(qiáng)的方法，能夠快速的對(duì)任務(wù)信息進(jìn)行采集和分析，得到解決任務(wù)分 配問(wèn)題的具體方案，獲得的方案往往是局部最優(yōu)的，但不能得到全局最優(yōu)方案。而集中式控制方法恰恰相反，由于所有信息都要返回地面控制站進(jìn)行匯總，所有 能夠進(jìn)行全面而詳細(xì)的規(guī)劃，從而獲得的方案一般都是全局最優(yōu)方案，但是實(shí)時(shí) 性就很差啦。當(dāng)前，國(guó)內(nèi)外很多院校和科研機(jī)構(gòu)對(duì)集中式控制和分布式控制方法 結(jié)合的問(wèn)題進(jìn)行了理論分析和實(shí)際驗(yàn)證，對(duì)兩種方法進(jìn)行了整合，得到了

35、部分分 布式控制方法，結(jié)構(gòu)閣如閣2. 4所示。在部分分布式控制方法屮，地而控制站屮的操作人員對(duì)無(wú)人機(jī)返回的信息進(jìn) 行歸納和分析，在靜態(tài)環(huán)境下給無(wú)人機(jī)編隊(duì)中的每架無(wú)人機(jī)都設(shè)計(jì)了初始任務(wù)分 配方案。在動(dòng)態(tài)環(huán)境下，例如無(wú)人機(jī)狀態(tài)的改變，任務(wù)的改變將導(dǎo)致任務(wù)的再分 配。此時(shí)，無(wú)人機(jī)編隊(duì)屮的無(wú)人機(jī)發(fā)揮自己的自主性，重新對(duì)任務(wù)0標(biāo)信息采集 并分析，在編隊(duì)中與其它無(wú)人機(jī)進(jìn)行信息的共享和交互。地面控制站中的操作人 員在某些特定的時(shí)候?qū)o(wú)人機(jī)編隊(duì)發(fā)送任務(wù)指令，大部分時(shí)候依靠的是無(wú)人機(jī)編 隊(duì)自身的協(xié)同分配。主要既提高了實(shí)時(shí)性，又大大減小了地面工作站的任務(wù)量， 得到的任務(wù)分配方案也是相對(duì)合理的。部分分布是控制方法對(duì)

36、集中式控制和分布 式控制方法進(jìn)行取長(zhǎng)補(bǔ)短，體現(xiàn)了人們的智慧，具有較強(qiáng)的實(shí)際應(yīng)用意義。2. 3無(wú)人機(jī)任務(wù)分配模型分類(lèi)根據(jù)任務(wù)分配建模分類(lèi)，現(xiàn)階段的模型主要有多旅行商問(wèn)題2 (multiple traveling sa-lesman problem, mtsp)模型，通用分配問(wèn)題3 (generalized assignmentproblem, gap)模型，車(chē)輛路徑問(wèn)題4 (vehicle routing problem, vrp)模型，混 合整數(shù)線性規(guī)劃s，6，s，9(mixed integer linear programming, milp)模型以及cmtap(cooperative mu

37、ltiple task assignment problem)模型。2. 3. 1多旅行商問(wèn)題模型通常，我們所說(shuō)的旅行商問(wèn)題是一個(gè)np完全問(wèn)題，具的定義如下：假設(shè)有a 個(gè)旅行商人，方個(gè)城市，每個(gè)旅行商人都要沿著城市之間的道路訪問(wèn)其中的一些城 市，最后所有的旅行商人都要返回初始的城市，限制每個(gè)城市都要被訪問(wèn)并且有 且僅有一次，問(wèn)題所要達(dá)到的目的是在完成對(duì)所有城市訪問(wèn)的同時(shí)，總距離最短、 完成任務(wù)時(shí)間最短、消耗最小、收益最大等。把旅行上問(wèn)題模型應(yīng)用到無(wú)人機(jī)任 務(wù)分配中去，我們假設(shè)有一個(gè)二架無(wú)人機(jī)的無(wú)人機(jī)編隊(duì)，有二個(gè)目標(biāo)任務(wù)的任務(wù) 集，無(wú)人機(jī)編隊(duì)從同一個(gè)基地出發(fā)，沿著預(yù)先設(shè)定的飛行航路，完成所有的任

38、務(wù)， 每個(gè)任務(wù)只能被完成一次，最后考慮無(wú)人機(jī)的總航程，無(wú)人機(jī)完成任務(wù)的時(shí)間， 無(wú)人機(jī)消耗的能力，完成任務(wù)的價(jià)值利益等。2. 3. 2通用分配問(wèn)題模型通用分配問(wèn)題模型考慮將二個(gè)任務(wù)分配給二個(gè)單體，每個(gè)任務(wù)只能給一個(gè)單 體并且單體的資源受到限制。相當(dāng)于二個(gè)任務(wù)分配給 給一個(gè)無(wú)人機(jī)執(zhí)行并且無(wú)人機(jī)的資源，如最大任務(wù)數(shù)，二個(gè)無(wú)人機(jī)，每個(gè)任務(wù)只能最大航程受到限制。2. 3. 3車(chē)輛路徑問(wèn)題模型我們對(duì)車(chē)輛路徑模型進(jìn)行如下描述：假設(shè)有二輛貨車(chē)，每輛車(chē)的負(fù)載能力不 同，它們從同一個(gè)基地出發(fā)，為二個(gè)目標(biāo)點(diǎn)輸送貨物，每個(gè)目標(biāo)點(diǎn)耑要送達(dá)的貨 物數(shù)量不同。最后，所有貨車(chē)回到出發(fā)點(diǎn)。車(chē)輛路徑問(wèn)題模型yo要考慮送達(dá)的時(shí) 間

39、，貨物送達(dá)的消耗，完成輸送的價(jià)值等，并保證所有的貨物安全送達(dá)。2. 3. 4混合整數(shù)線性規(guī)劃模型混合整數(shù)線性利用線性化函數(shù)建立模型，模型描述簡(jiǎn)潔、直接，有助于提高 無(wú)人機(jī)任務(wù)執(zhí)行效率和生存能力，達(dá)到了任務(wù)分配的目的和初衷而且可以通過(guò)對(duì) 約束條件的修正來(lái)滿足實(shí)際問(wèn)題需要，但是模型規(guī)模不能過(guò)大。問(wèn)題規(guī)模過(guò)大將 導(dǎo)致計(jì)算量指數(shù)型增長(zhǎng)，任務(wù)分配的實(shí)時(shí)性得不到保證。2. 3. 5 cmtap通用模型隨著無(wú)人機(jī)能力不斷增強(qiáng)，無(wú)人機(jī)執(zhí)行任務(wù)的復(fù)雜程度也隨之增強(qiáng)，不同任 務(wù)之間存在著復(fù)雜的時(shí)序以及時(shí)間約朿。對(duì)于這一類(lèi)復(fù)雜的任務(wù)集合，目前大多 數(shù)任務(wù)分配模型無(wú)法對(duì)其進(jìn)行有效的描述。一種cmtap模型川被引出，這

40、種模型 充分考慮一組無(wú)人機(jī)完成一系列針對(duì)地而目標(biāo)的連貫任務(wù)，包括任務(wù)目標(biāo)的識(shí)別、 攻擊、毀傷評(píng)估等。2. 4靜態(tài)任務(wù)分配算法在靜態(tài)環(huán)境中，無(wú)人機(jī)和任務(wù)都是確定的，不發(fā)生改變。在這樣的條件下，多無(wú)人機(jī)任務(wù)分配的算法主要有：群算法，市場(chǎng)機(jī)制算法和進(jìn)化算法。2. 4. 1群算法群算法主要模仿自然界中各種生物的群體化行為，例如蟲(chóng)群12和羊群。我 們通過(guò)對(duì)蟲(chóng)群群體化行為就行具體的研宂分析，從而來(lái)簡(jiǎn)單說(shuō)明群算法的具體特點(diǎn)： 所謂的昆蟲(chóng)群的群體行動(dòng)指的是昆蟲(chó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)屮昆蟲(chóng)主要遵循三個(gè)準(zhǔn)則：第一，實(shí)時(shí) 監(jiān)測(cè)與鄰近個(gè)體距離，防止產(chǎn)生交叉沖突，即

41、防止和其它個(gè)體產(chǎn)生碰撞；第二，采集鄰近個(gè)體的信息，如速度，位置等；第三，保證和其它昆蟲(chóng)的距離，不能太 遠(yuǎn)，而脫離群體。昆蟲(chóng)以上的這些行為都是個(gè)體的行為，不是群體的運(yùn)動(dòng)，不過(guò) 所有的個(gè)體都執(zhí)行這些準(zhǔn)則，就會(huì)產(chǎn)生整體的運(yùn)動(dòng)趨勢(shì)。群算法中fi前為止最為 經(jīng)典就是蟻群算法13, 14, 15, 16 （ant colony optimization） ,1991 年，意大利科學(xué)家dorigo首先在其發(fā)表的研究成果中提到了蟻群算法。蟻群算法遵循的基本規(guī) 則是：模仿生物界中螞蟻群體尋找食物的行為，螞蟻在尋找食物的時(shí)候，一般都 能夠在經(jīng)過(guò)的路徑上分泌并留下特定的激素。螞蟻個(gè)體往復(fù)的在路徑上留下激素， 激素的

42、濃度在較好的路徑上積累，濃度變大，從而使后來(lái)的螞蟻能快速的找到食 物所在的位置。一種改進(jìn)的蟻群算法川，該蟻群算法基于蟻群中各種類(lèi)型螞蟻的 分工機(jī)制，相對(duì)于多子蟻群算法有效地提高了算法的優(yōu)化能力。圖2. 5可簡(jiǎn)單說(shuō) 明蟻群算法的基本原理。支路二（蟻穴）a（食物）b支路一支路二支路一2. 5蟻群算法原理圖如圖所示，a點(diǎn)表示的是螞蟻的巢穴位置，別點(diǎn)表示的是食物的位置，有兩條 路徑在巢穴和食物之間。假定有兩組數(shù)h相同的螞蟻同時(shí)由a點(diǎn)出發(fā)，沿著兩條 路徑分別向著方點(diǎn)前進(jìn)，剛開(kāi)始沿著兩條路徑的概率是相等的，均為二分之一， 設(shè)定螞蟻爬行的速度相同，螞蟻單位時(shí)間分泌的激素量相同。螞蟻就這樣往復(fù)的 在這兩條路徑

43、上來(lái)回搬運(yùn)食物，但是由于路徑二明顯長(zhǎng)于路徑一，所以路徑二上 的激素的濃度將會(huì)明顯小于路徑一上的激素的濃度。巾于路徑二的上的激素濃度 較大，螞蟻就會(huì)越來(lái)越偏向于向路徑二前進(jìn)，這樣在路徑一上留下來(lái)的激素也越 來(lái)越多，激素的濃度不斷增加，直到最后，幾乎所有螞蟻都會(huì)沿著路徑一前進(jìn)去 尋找食物，這樣大大提高了螞蟻搬運(yùn)食物的效率。除了蟻群算法，常見(jiàn)的群算法還有kennedy和eberhart提出的粒子群算法2, 13 (particle swarm optimization)其最初是模仿鳥(niǎo)群覓食而設(shè)計(jì)的，在pso 算法中，每個(gè)任務(wù)分配方案都是“粒子”，所有的粒子都有適應(yīng)值函數(shù)決定的適應(yīng)值。 pso算法的基

44、本流程為：(1) 初始化一群大小為二的粒子，包括他的位貫和速度。(2) 設(shè)計(jì)適應(yīng)度函數(shù)并評(píng)價(jià)每個(gè)粒子的適應(yīng)度大小(3) 對(duì)每個(gè)粒子將其適應(yīng)度大小與歷史極值尸作比較，如果比歷史極值好，便將它作為新的pou)對(duì)每個(gè)粒子，將適應(yīng)值與尸作比較，如果較好，將它作為新的尸(5) 根據(jù)迭代公式，變化粒子的位置和速度。(6) 如達(dá)到結(jié)束條件(有足夠好的適應(yīng)值或者達(dá)到預(yù)設(shè)的迭代次數(shù))則結(jié)束， 否則返回步驟(2)0(7) 算法結(jié)朿。群算法作為一類(lèi)典型的解決靜態(tài)任務(wù)分配的方法，有其自身獨(dú)特的地方。相 對(duì)于其它任務(wù)分配算法，有很多的優(yōu)點(diǎn)，但是萬(wàn)事都有利有弊，群算法在存在優(yōu) 勢(shì)的同時(shí)還存在許多的不足之處。我們對(duì)先前研究

45、的蟻群算法和粒子群算法進(jìn)行 分析，結(jié)合國(guó)內(nèi)外對(duì)群算法在無(wú)人機(jī)任務(wù)分配中的應(yīng)用實(shí)例和理論研究，總結(jié)歸 納出群算法具體有以下四個(gè)優(yōu)勢(shì)：1. 隨機(jī)性強(qiáng)。2. 可以對(duì)較大規(guī)模的實(shí)際問(wèn)題進(jìn)行求解。3. 邏輯簡(jiǎn)單，適用于簡(jiǎn)單的任務(wù)判斷。4. 在搜索過(guò)程中消耗的能力少。四個(gè)缺點(diǎn)：(1) 實(shí)時(shí)性差，很難確定具體時(shí)間。(2) 理論依裾不夠充分。(3) 得到的解不一定是最優(yōu)的。(4) 對(duì)于多類(lèi)型的無(wú)人機(jī)不適用。群算法依據(jù)的是生物種群中生物個(gè)體的運(yùn)動(dòng)，每個(gè)生物個(gè)體的形態(tài)結(jié)構(gòu)和具 體能力基本是一樣的，近乎相同，所以具有很強(qiáng)的隨機(jī)性。在對(duì)于考慮無(wú)人機(jī)類(lèi) 型單一的任務(wù)分配問(wèn)題時(shí)是有優(yōu)勢(shì)的。但是當(dāng)無(wú)人機(jī)的類(lèi)型多樣時(shí)，如無(wú)人

46、機(jī)的 能力和性能的不同，群算法不能區(qū)別各個(gè)無(wú)人機(jī)，從而不能合理的對(duì)任務(wù)進(jìn)行分 配。其次，群算法的基礎(chǔ)是由生物種群中的個(gè)體行動(dòng)，但是任務(wù)分配的最終解決 方案是由生物種群的整體運(yùn)動(dòng)趨勢(shì)得來(lái)的。所以個(gè)體數(shù)目的多少對(duì)算法沒(méi)有很大 的影響，即可以對(duì)較大規(guī)模的實(shí)際任務(wù)分配問(wèn)題進(jìn)行求解，這又是它的一個(gè)優(yōu)勢(shì)。 另外，群算法的搜索方式是隨機(jī)搜索，以粒子群算法為例，其搜索空間是不確定 的，我們知道粒子群中的粒子是朝著一個(gè)方向移動(dòng)，但是沒(méi)有準(zhǔn)確的理論依裾，這是這類(lèi)©法最重要的缺點(diǎn)。并且由于隨機(jī)搜索的方法通常得到的是局部最優(yōu)解， 對(duì)于全局最優(yōu)解往往很難得到，容易“早熟”。所以我們?cè)谌核惴ㄋ阉鬟^(guò)程屮引 入正反

47、饋機(jī)制，大大提高了算法的收斂速度。2.4.2市場(chǎng)類(lèi)算法市場(chǎng)類(lèi)算法18 19, 20, 21是另一大類(lèi)靜態(tài)任務(wù)分配算法。它來(lái)源于市 資本主義社會(huì)市場(chǎng)經(jīng)濟(jì)體制。市場(chǎng)巾有許許多多的客戶(hù)，每個(gè)客戶(hù)依據(jù)自己的投資能力和預(yù) 期效益而對(duì)市場(chǎng)中的項(xiàng)目進(jìn)行投資，個(gè)別的客戶(hù)個(gè)體無(wú)法改變整個(gè)市場(chǎng)的走勢(shì)， 但是把所有的客戶(hù)看作一個(gè)統(tǒng)一的大集合，就可以通過(guò)投資對(duì)整個(gè)的市場(chǎng)的走勢(shì) 產(chǎn)生決定性的作用，即市場(chǎng)的發(fā)展或者是市場(chǎng)的消退。市場(chǎng)類(lèi)算法把市場(chǎng)中的每 個(gè)客戶(hù)可以看作智能體，在無(wú)人機(jī)的任務(wù)分配方法研宄中得到了很廣泛的應(yīng)用。czi 介紹了一種包含談判機(jī)制的市場(chǎng)類(lèi)算法，無(wú)人機(jī)通過(guò)數(shù)據(jù)鏈技術(shù)相互傳遞信息， 協(xié)商得出任務(wù)分配方案。

48、在該類(lèi)算法屮，每架無(wú)人機(jī)完成一個(gè)任務(wù)都會(huì)產(chǎn)生收益， 但是執(zhí)行時(shí)會(huì)消耗無(wú)人機(jī)的能力。得到與損失的差額就是無(wú)人機(jī)完成任務(wù)的利益， 每架無(wú)人機(jī)都為了利益最大化而執(zhí)行任務(wù)。通過(guò)對(duì)大量對(duì)市場(chǎng)類(lèi)算法在無(wú)人機(jī)任務(wù)分配方法求解的理論研究和實(shí)際應(yīng)用 中，我們總結(jié)歸納了市場(chǎng)類(lèi)算法的主要優(yōu)點(diǎn)。1)確保了每架無(wú)人機(jī)收獲的利益和消耗的能力相差不大。(2) 無(wú)人機(jī)的類(lèi)型可以不同。(3) 大大減少了無(wú)人機(jī)在空間內(nèi)搜索的時(shí)間。因?yàn)槭袌?chǎng)中每個(gè)單體所追求的是個(gè)體的利益，所以對(duì)于個(gè)體而言不僅要考慮 完成任務(wù)獲得的收益，還要考慮自身的執(zhí)行能力，也就是所謂的本錢(qián)。無(wú)人機(jī)在 任務(wù)分配過(guò)程屮，要考慮無(wú)人機(jī)本身執(zhí)行任務(wù)的能力，包括航程，航速

49、和負(fù)載載 荷等，這就保證了資源的均衡。其次考慮到市場(chǎng)中各個(gè)客戶(hù)的不同，符合無(wú)人機(jī) 任務(wù)分配的實(shí)際問(wèn)題，因?yàn)橥鶡o(wú)人機(jī)的類(lèi)型都是不一樣的。s后，由于市場(chǎng)類(lèi) 方法，只考慮個(gè)體的收益最大，而不是考慮整體的收益最大，不耑要對(duì)所有的情 況進(jìn)行全面的考慮，從而減少了空間中搜索的時(shí)間。但是由于市場(chǎng)中的盲fi性， 往往不能得到最佳的分配方案。2. 4. 3進(jìn)化理論算法最后一大類(lèi)靜態(tài)任務(wù)分配算法是進(jìn)化理論算法，該算法的理論依據(jù)是仿照自 然界中生物種群進(jìn)化，以?xún)?yōu)勝劣汰的進(jìn)化原則，將相對(duì)優(yōu)秀的生物個(gè)體保留下來(lái)， 而相對(duì)差點(diǎn)的個(gè)體剔除出種群。遺傳算法是這一大類(lèi)算法中使用最多，最為有名 的算法。1975年，美國(guó)密歇根大

50、學(xué)的教授首次在研宄成果屮提到了遺傳算法，之 后，全世界很多國(guó)家的科研工作者對(duì)遺傳算法進(jìn)行了理論研究和實(shí)際應(yīng)用。遺傳 ©法仿照生物進(jìn)化理論，才有染色體編碼方式進(jìn)行任務(wù)分配方法的最優(yōu)化選擇。遺傳算法以決策變量的編碼作為運(yùn)算對(duì)象，傳統(tǒng)的優(yōu)化算法往往直接采用決策變 量的實(shí)際值，這是它的一個(gè)很大的特點(diǎn)?；趗av多任務(wù)協(xié)同分配問(wèn)題特定染色 體編碼方式，遺傳算法采用兩種進(jìn)化操作：選擇操作和交叉操作。有研究者在傳 統(tǒng)的遺傳算法屮使用鄰域搜索算法m。基于鄰域搜索原理，運(yùn)用對(duì)稱(chēng)群結(jié)構(gòu)描述 uav任務(wù)分配的搜索空間，運(yùn)用右乘運(yùn)算構(gòu)造搜索鄰域，結(jié)禁忌搜索。相對(duì)于傳統(tǒng) 遺傳算法、爬山能力強(qiáng)和全局迭代尋優(yōu)，易

51、找到全局最優(yōu)點(diǎn)，實(shí)現(xiàn)了基于對(duì)稱(chēng)群 計(jì)算的uav任務(wù)分配算法。算法基本步驟：(2) 設(shè)罝演化代數(shù)ng,，種群規(guī)模nv ov,繁殖池子大小s,交叉概率p。，變 異概率p,n;(3) 隨機(jī)生成大小為no*的種群;(4) 評(píng)價(jià)uav任務(wù)分配種群屮的每一個(gè)個(gè)體；(5) 如果滿足終止，轉(zhuǎn)到12步，否則，進(jìn)入第_5步；(6) 利用選擇輪盤(pán)種群中選取s個(gè)個(gè)體組成繁殖池子；(7) 按交叉概率pc，采用pmx交叉方式進(jìn)行交叉操作(8) 按照變異概率pm，進(jìn)行變異操作；(9) 將新生成的個(gè)體加入到種群中；(10) 計(jì)算新個(gè)體的適應(yīng)值(11) 將擴(kuò)展的種群最差的s個(gè)個(gè)體刪除，使其恢復(fù)原來(lái)種群的大小；(12) 轉(zhuǎn)到第(

52、4)步(13) 從種群屮選出最好的個(gè)體作為所求航跡，進(jìn)化過(guò)程結(jié)束。算法染色體編碼方法如下：染色體表現(xiàn)形式與問(wèn)題越接近，進(jìn)化算法越能夠生成更好的解，對(duì)于最基本 的任務(wù)分配方法，采川了如下染色體編碼方案：進(jìn)化種群中每個(gè)個(gè)體川一個(gè)長(zhǎng)度 為z的任務(wù)點(diǎn)排列表示，這里z表示所有的任務(wù)點(diǎn)的數(shù)r。染色體的每個(gè)基因座上 隨機(jī)設(shè)定一個(gè)任務(wù)點(diǎn)的頂點(diǎn)。同時(shí)對(duì)于uav集中的所有uav，(i = l，.nu ),此染 色體還對(duì)應(yīng)一個(gè)隨機(jī)產(chǎn)生的非負(fù)整數(shù)n,的集合，集合中的元素表示該uav分配到的任 務(wù)點(diǎn)的數(shù)目，并保證藝 n. l( 2-2 )圖2. 6給出了任務(wù)分配種群屮某染色體的示意閣23。該染色體表示個(gè)uav組成的飛行

53、編隊(duì)，其中uav 1的航路為uav 1-2-3-uav 1,魷=2 ;uav2的航 路為 uav2-卜4-5-uav2,nz = 5。234_5uav 1uav2圖2. 6染色體編碼基于uav任務(wù)分配問(wèn)題特定的染色體編碼方式和適應(yīng)度函數(shù)，本文采用如下 的進(jìn)化操作：(1) 選擇操作進(jìn)化算法的選擇是建立在對(duì)個(gè)體適應(yīng)度的評(píng)價(jià)基礎(chǔ)之上的，本文采用經(jīng)典的 比例選擇算子來(lái)實(shí)現(xiàn)該操作來(lái)實(shí)現(xiàn)該操作。比例選擇是一種有退還的隨機(jī)采樣方法，其基本思想是：每個(gè)個(gè)體中被選中 的概率與其適應(yīng)度大小成正比，其具體的執(zhí)行過(guò)程如下a. 計(jì)算出種群屮每一個(gè)個(gè)體的評(píng)價(jià)函數(shù)的伉的，得到它們的總和；b. 分別計(jì)算總?cè)棺觽€(gè)體評(píng)價(jià)函數(shù)值的

54、相對(duì)值，即各個(gè)個(gè)體被選中作為父代遺傳 到下一子代的概率；c. 再使用類(lèi)似賭博輪盤(pán)的操作(即產(chǎn)生0-1之間的隨機(jī)數(shù))，從而分別確定每 個(gè)個(gè)體被選中遺傳到下一代的概率。(2) 交叉操作本文采用的交叉操作使用的是ea-pmx算法屮的pmx交叉算子。uav任務(wù) 分配問(wèn)題對(duì)交叉算子的設(shè)計(jì)要求是：對(duì)任意兩條染色體進(jìn)行交叉操作后，能得到 兩天新的，且具有實(shí)際意義的染色體序列。部分交叉映射(partially mapped crossover, pmx)算子是一種常見(jiàn)的交叉算子。pmx算子的主要思想是：整個(gè)交叉過(guò)程分兩步完成，首先對(duì)個(gè)體編碼進(jìn)行常規(guī)的雙點(diǎn)交叉操作，然后根據(jù)交叉區(qū)域a各基因值得映射關(guān)系來(lái)修改交叉

55、區(qū)域之 外的各基因座的基因值，按照染色體的編碼，種群中的任一染色體表示為 t=(t1, tz, . .tn)o由父代染色體雙，t、按照pmx方法產(chǎn)生兩個(gè)新子代染色體算法步驟如下：a. 隨機(jī)選取兩個(gè)基因插入點(diǎn)i和j后的位置為交叉點(diǎn)，即將第i + 1個(gè)基因插入 點(diǎn)和第j個(gè)基因插入點(diǎn)之間的各個(gè)基因點(diǎn)定義為相交區(qū)域。b. 相交區(qū)域內(nèi)的各個(gè)基因插入點(diǎn)p(p=i + l，i+2，. j)，在個(gè)體t中求出叮=叮的 基因座r,在個(gè)體兀中求出ty-y_的基因座：，然后互換基因值叮和 t yy和弓。 所得結(jié)果為tx和to.(3) 變異操作在uav任務(wù)分配的混合搜索算法中，將細(xì)菌覓食算法中的遷徙操作作為改進(jìn) 進(jìn)化算

56、法屮的變異算子使用，稱(chēng)之為遷徙變異算子。遷徙變異算子首先進(jìn)行遷徙 操作，以概率p隨機(jī)選擇種群中評(píng)價(jià)函數(shù)值較差的染色體，作為變異的初始染色 體，然后以概率pn隨機(jī)抽取初始染色體中的一位進(jìn)行變異操作。進(jìn)化理論算法的優(yōu)點(diǎn)主要有如下三點(diǎn)：(1) 以評(píng)價(jià)函數(shù)值為依據(jù)進(jìn)行判斷，不需要引入其他數(shù)學(xué)方法對(duì)數(shù)據(jù)進(jìn)行處 理。(2) 因?yàn)橛卸鄠€(gè)基因插入點(diǎn)，所以具有很強(qiáng)的隨機(jī)性。(3) 存在變異概率，可以跳出局部最優(yōu)。遺傳算法的算法速度快，通常很快就能得到比較好的局部最優(yōu)解，因?yàn)檫z傳 算法中變異的概率很小，所以很難跳出局部最優(yōu)解而得到全局最優(yōu)解，這是其主 要缺點(diǎn)。同時(shí)遺傳算法由于其本質(zhì)上的隨機(jī)性，求解過(guò)程屮存在較多劣

57、質(zhì)搜索過(guò)程, 導(dǎo)致其在大規(guī)模組合優(yōu)化問(wèn)題的求解中效率和精度不高。2. 5動(dòng)態(tài)環(huán)境中多任務(wù)重分配算法在具體環(huán)境中，由于環(huán)境的動(dòng)態(tài)性和不確定性以及協(xié)同控制的復(fù)雜性，使得 任務(wù)開(kāi)始后會(huì)出現(xiàn)許多無(wú)法預(yù)料的情況，因此，必須根據(jù)戰(zhàn)場(chǎng)態(tài)勢(shì)和編隊(duì)狀態(tài)的 變化快速調(diào)整uav編隊(duì)的任務(wù)計(jì)劃，通過(guò)動(dòng)態(tài)重調(diào)度實(shí)現(xiàn)uav之間的任務(wù)重分 配，以真正適應(yīng)復(fù)雜的作戰(zhàn)環(huán)境。因此，我們更多的使用到的是動(dòng)態(tài)分配算法。uav任務(wù)再分配的一般策略整個(gè)編隊(duì)的完全再分配局部調(diào)整分組基礎(chǔ)上的再分 配。動(dòng)態(tài)任務(wù)分配算法主要有：合同網(wǎng)算法、拍賣(mài)算法、聚類(lèi)算法。2. 5. 1合同網(wǎng)算法為了更好的解釋合同網(wǎng)的概念，我們首先簡(jiǎn)要介紹下什么是agent智能體)。通常我們認(rèn)為：agent主要應(yīng)用于動(dòng)態(tài)環(huán)境中，他具有先進(jìn)的設(shè)備，如傳感器，高 性能機(jī)載電腦，先進(jìn)的導(dǎo)航系統(tǒng)等，實(shí)吋獲取自身的狀態(tài)信息，如形態(tài)，位置，負(fù)載等；任務(wù)集信息，如0標(biāo)位置，0標(biāo)數(shù)量，任務(wù)目標(biāo)價(jià)值以及周?chē)沫h(huán)境信 息。通過(guò)對(duì)這些信息的總結(jié)，分析，與其他無(wú)人機(jī)進(jìn)行信息共享交互，制定出任 務(wù)分配方案并執(zhí)行。它具