無人機組群巡檢滅火系統(tǒng)設計【說明書+CAD+SOLIDWORKS】,說明書+CAD+SOLIDWORKS,無人,機組,巡檢,滅火,系統(tǒng),設計,說明書,仿單,cad,solidworks 本科畢業(yè)設計 題 目： 無人機組群巡檢滅火系統(tǒng)設計 學 院： 機電工程學院 專 業(yè)： 機械設計制造及其自動化 姓 名： 學 號： 指導教師： 2016年5月28日 摘 要 隨著無人機執(zhí)行任務的環(huán)境日益復雜，任務類型日益多樣，無人機己經(jīng)開始 從單架次獨立任務的方式向著多架次、多類型的機群作戰(zhàn)方向發(fā)展。通過對多無 人機協(xié)同任務分配的研究，可以使系統(tǒng)完成的任務類型更為多樣，同時任務完成 的質量和效率也獲得較大程度的提高。 本文研究了集中式多類型無人機編隊任務分配方法。集中式指的是任務分配 過程中，無人機處于從屬地位，不具有自主能力，完全受控制站中人的控制。多 類型指的是無人機類型和執(zhí)行能力的不同。 本文首先介紹了無人機的應用現(xiàn)狀，討論了幾種任務分配算法，分析了他們 的優(yōu)缺點。其次，在靜態(tài)環(huán)境下基于平面網(wǎng)格坐標系，建立了一個多無人機任務 分配數(shù)學模型，設計了一種有人參與的靜態(tài)分配算法。然后利用了一個無人機森林滅火的實例，通過MATLAB仿真和分析說明了算法的可行性和實用性。最后，在動態(tài)環(huán)境中，根據(jù)無人機狀態(tài)改變和任務改變兩種情況，對動態(tài)任務進行了動態(tài)重分配。 關鍵字:無人機；任務分配；靜態(tài)分配；動態(tài)重分配 Abstract With the increasingly complex environment, the missions of the UAV grow variously. The operational manner of UAV 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 the 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 introduces the present situation of the applications of UAV, discussed some kinds of task allocation algorithms and analyzed their advantages and disadvantages. What's more, in a static environment, based on the planar grid coordinate system, we set up a multi-UAV task allocation mathematical model and designed 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 redistribution, in dynamic environment. Keywords: UAV ；Task allocation ；Static allocation ；Dynamic redistribution 目 錄 第一章 緒論 1 1.1任務分配的研究背景 2 1.2國內(nèi)外無人機應用現(xiàn)狀 2 1.2.1應用在軍事上 2 1.2.2應用在自然災害的防護上 3 1.3論文的主要內(nèi)容 4 第二章 無人機任務分配問題研究現(xiàn)狀及發(fā)展趨勢 4 2.1無人機任務分配問題的定義及解決步驟 4 2.1.1 UAV任務分配問題的定義 5 2.1.2 UAV任務分配問題的描述 5 2.1.3解決UAV任務分配問題的步驟 5 2.2無人機任務分配控制方法 5 2.2.1集中式控制 5 2.2.2分布式控制 6 2.3無人機任務分配模型分類 7 2.3.1多旅行商問題模型 7 2.3.2通用分配問題模型 8 2.3.3車輛路徑問題模型 8 2.3.4混合整數(shù)線性規(guī)劃模型 9 2.3.5 CMTAP通用模型 9 2.4靜態(tài)任務分配算法 10 2.4.1群算法 10 2.4.2市場類算法 11 2.4.3進化理論算法 11 2.5動態(tài)環(huán)境中多任務重分配算法 11 2.5.1合同網(wǎng)算法 11 2.5.2拍賣算法 12 II 2.5.3聚類算法 12 第三章 靜態(tài)環(huán)境下無人機任務分配 12 3.1任務分配場景和限制條件 13 3.1.1任務分配的場景 14 3.1.2任務分配限制條件 14 3.2多無人機任務分配的數(shù)學模型 14 3.2.1無人機任務集描述 15 3.2.2平面網(wǎng)格坐標系 16 第四章 動態(tài)環(huán)境下無人機任務分配 17 4.1動態(tài)任務重分配 18 4.1.1動態(tài)任務重分配的觸發(fā)條件 18 4.1.2任務動態(tài)再分配采用的策略 19 4.1.3任務重分配的流程 21 結 論 23 參考文獻 24 致 謝 25 第一章 緒論 1.1任務分配的研究背景 無人機(Uninhabited Aerial Vehicle, UAV)是指由遠程遙控或自主控制操作的無人駕駛的飛機。采用無人駕駛的方式使飛機擺脫了駕駛員自身生理條件的限制， 能夠完成一般飛機不能完成的任務。無人機具有重量輕、維護成本低、機動性能 高等明顯優(yōu)勢，同時無人駕駛的方式使操作人員遠離危險的任務環(huán)境，極大地降 低了操作人員的危險程度。 UAV協(xié)同任務規(guī)劃是現(xiàn)代戰(zhàn)爭中提出的新課題。隨著無人機的出現(xiàn)，利用無 人機執(zhí)行任務逐步成為了現(xiàn)實，目前UAV協(xié)同任務規(guī)劃得到了越來越多的關注， 因為盡管單無人機可以無需合作完成某個環(huán)境的搜索，但是一個更有效的搜索需 要合作來減少重復覆蓋，通常多無人機任務規(guī)劃可以分成兩大部分:上層的任務 分配(Task Assignment or Task Allocation)和下層的路徑規(guī)劃(Path Planning)，任務分配考慮各種約束條件，以總體任務有效達成為目標，將具體目標和行動任務分配給各機，而各機根據(jù)分配的任務再進行具體的作戰(zhàn)路徑規(guī)劃。路徑規(guī)劃的功能是在滿足如最大線性速度、最大轉角速度、操作的安全性、時間和環(huán)境變量等自身 或外部限制的前提下在一系列位置之間設計或生成路徑。本文我們主要討論UAV 任務分配問題。 1.2國內(nèi)外無人機應用現(xiàn)狀 1.2.1應用在軍事上 UAV任務規(guī)劃技術主要還是應用在軍事上。無人作戰(zhàn)飛機((Uninhabited Combat Aerial Vehicle, UCAV)指的是無人機攜帶武器或者彈藥，可對地面目標進行攻擊 和轟炸。在軍事發(fā)達國家，尤其美國、英國以及法國對無人作戰(zhàn)機研究深入，美國對于無人機任務分配問題在軍事上的研究最為深入，在上世紀70年代就開始對無人機任務分配問題進行描述并進行實際應用。在越南戰(zhàn)爭，海灣戰(zhàn)爭以及北約空襲南斯拉夫等過往戰(zhàn)爭中，無人機經(jīng)常用于執(zhí)行一些人不能完成的軍事任務。在這些爭中雖然無人機不是主要執(zhí)行任務的飛機，但它卻成了決定戰(zhàn)爭導向的決定因素之一。由于無人機的無人駕駛特點，可以被派往危險的環(huán)境中執(zhí)行一些人不能執(zhí)行的任務，因而成為重要的軍事力量受各國關住。無人機可以用來完成對戰(zhàn)場實時的偵察和監(jiān)視、對目標位置的確定、任務目標的評估、電子對抗等。無人機最早的開發(fā)是在第一次世界大戰(zhàn)之后。和美國等西方國家相比，我國的無人機研究水平差距還是很大。雖然國內(nèi)從80年代末開始，對路徑規(guī)劃問題進行過許多研究，發(fā)表了許多論文，但大多數(shù)的文獻僅僅是對單無人機所進行的路徑規(guī)劃問題的研究，目的是避開無人機在飛行過程中遇到的危險區(qū)域，很少有關于無人機任務分配問題解答的研究成果。當前我們國家無人機反的研究還處在起步階段。由于我國的無人機功能簡單，自主能力較差，需要地面控制站進行任務分配的規(guī)劃。而當前的無人機發(fā)展趨勢是無人機的智能化，將無人機看成一個個智能體，我國在這方面的研究成果很少。功能上也只能進行簡單的圖像，數(shù)字傳輸，任務分配、路徑規(guī)劃的能力很差。尚不具備執(zhí)行復雜戰(zhàn)術任務的能力。近年來我國的國防科技大學、西北工業(yè)大學等高等院校和科研單位在無人機任務分配問題上也進行了一些理論分析和實際問題的研究，可以說取得了不錯的成就。但從現(xiàn)階段己經(jīng)得到的理論和實際成果來看，目前我國對無人機任務分配問題的研究還處有很多不足和局限。例如無人機的自主性較差，無人機的決策大都是由地面控制站決定的。對于無人機所處的動態(tài)環(huán)境考慮不足，無人機的尺寸、時間窗函數(shù)等考慮較少。 2.2應用在自然災害的防護上 和平和發(fā)展當今世界的兩大主題，所以無人機的應用也由軍用慢慢轉向民用。 其中最主要的民用用途是在自然災害的防護上。2001年以來，世界各國都在大力 發(fā)展各種用途的無人飛行器。目前世界上32個國家己研制出了多種無人機。美國、 以色列、俄羅斯、北約等國家非常重視多用途無人機的研制、生產(chǎn)和應用。森林 火災的現(xiàn)場溫度高，對飛機的抗熱性能高?，F(xiàn)場的煙塵大，能見度不高，盡管有 人飛機能飛至火場上課，飛機中的人也不能清除地了解火場當前的具體情況。這時無人機的優(yōu)勢就體現(xiàn)出來，通過在無人機上配置攝像機和數(shù)字圖像傳輸設備，可輕易完成對火場的偵察，滅火和滅火評估。美國航天局最新研制的無人滅火機“工khana"。這款無人滅火機由“捕食者B" (Predator B)改進而來?！安妒痴連”原本是美國空軍用于戰(zhàn)時監(jiān)視和偵察的，現(xiàn)在它的改進版“工khana”被用作另一個領域，那就是森林滅火。在火場中，由于火勢的動態(tài)性和不確定性以及協(xié)同控制的復雜性，使得任務開始后出現(xiàn)許多無法預料的情況，必須根據(jù)火場火勢和編隊狀態(tài)的變化快速調整UAV編隊的任務計劃，通過動態(tài)重調度實現(xiàn)任務的重分配。 1.3論文的主要內(nèi)容 無人機如何在復雜的環(huán)境中順利地完成所需執(zhí)行的任務，并且能夠使得任務執(zhí)行的效率最高，收獲的利益最大，付出的代價最小，是多無人機任務分配所要考慮的問題。本文的主要工作是通過對各種任務分配算法的研究，引出了一種有人參與的多無人機任務分配算法并進行了理論研究和仿真分析。主要步驟是:首先建立了一個任務分配在森林火災防護的應用場景，設置了關于實際問題的限制條件，然后建立了一個基于六元組的任務描述，使用了平面網(wǎng)格坐標系對任務分配問題進行建模，在以上的基礎了最后利用了一個無人機森林滅火的實例，通過MATLAB仿真結合算法說明了該算法的可行性和實用性。因為無人機任務分配所處環(huán)境是動態(tài)的，所以對動態(tài)環(huán)境下無人機任務重分配問題也進行了一些算法研究和實例分析。 第二章 無人機任務分配問題研究現(xiàn)狀及發(fā)展趨勢 2.1無人機任務分配問題的定義及解決步驟 2.1.1 UAV任務分配問題的定義 UAV任務分配問題可以定義為:在己經(jīng)完成UAV編隊分組的基礎上，基于一定的環(huán)境和任務要求，為編隊中的UAV分配一個或多個有序任務，以便在完成最大可能任務的同時，使得UAV編隊的整體效率最高。 我們結合圖2. 1這個簡單的例子來直觀地了解任務分配問題的具體含義:首先設置了任務集和無人機集:其中包含了四個待執(zhí)行任務，無人機編隊由兩架無人機組成。然后設計具體的路徑和任務執(zhí)行順序來完成所設定的四個任務。圖中每個帶箭頭直線上的數(shù)字表示無人機在該段航路上所花費的時間，四個任務用四個圓圈來表示。圓圈中上半部分的數(shù)字表示的無人機任務集中任務的序號，下半部分的數(shù)字表示完成這個任務需要的具體時間。最后虛實線表示的是任務分配的具體的方案。無人機分別沿著制定的虛線完成四個所設定的任務，通過這種方法，花費時間要明顯小于單架無人機。 2.1.2 UAV任務分配問題的描述 給定一個UAV編隊U，它包含數(shù)目為N二的無人機。 2.1.3解決UAV任務分配問題的步驟 無人機任務分配方法的求解主要分為兩方面:任務分配模型的建立以及具體 的任務分配算法的設計: (1) UAV任務分配的數(shù)學模型的建立 要對無人機進行數(shù)學建模，首先要對無人機所處的空間環(huán)境進行描述和表達。通常我們以一個二維或者三維的變量來定義一個無人機和目標點的位置，為簡便，一般采用二維變量。得到了無人機和目標點的位置，就能得到任一無人機的任務 執(zhí)行路線。然后我們設計一個二值決策變量，如果無人機完成某個任務，二值變 量就為1，如果不完成那個任務，二值變量就為0。然后要設定無人機任務分配的 約束條件，如無人機最大航程、任務時間窗約束、任務執(zhí)行的先后順序、無人機 的載荷等。 2.2無人機任務分配控制方法 由于無人機執(zhí)行任務環(huán)境是動態(tài)的，不是固定不變的，所以無人機的任務分配控制方法也應該根據(jù)不同的任務環(huán)境而區(qū)別對待。無人機任務分配控制方法選取對無人機執(zhí)行任務的效率和質量有很大關系。任務分配控制方法的選取應該考慮以下幾個因素:任務完成的快速性，任務的實時性，任務分配的計算時間和計算復雜度，抗干擾能力等。無人機任務分配控制方法主要可以分為集中式控制(Centralized Control)以及分布式控制(Distributed Control)這兩種。 2.2.1集中式控制 在集中式控制方法中，由地面控制站中的操作人員制定任務分配方案和無人機 具體的飛行航路，無人機本身不具備決策能力，完全按照地面控制站發(fā)出的任務指令和航路執(zhí)行任務。圖2.2表示了集中式體系結構圖: 2.2.2分布式控制 區(qū)別于集中式控制方法，分布式控制方法中無人機編隊中或者無人機編隊之間的無人機是具有獨自決策能力的智能體，它們具有很強的協(xié)同能力和自治性。無人機之間以數(shù)據(jù)鏈技術為支撐，對無人機所處環(huán)境，任務目標集信息，無人機狀態(tài)信息進行交互，綜合考慮各種因素，提出具體的解決任務分配問題的方案和具體步驟。較之于集中式控制方法，無人機個體在分布式控制方法下具有較強的實時性，抗干擾能力，計算量小，計算復雜度小等優(yōu)點。當前，分布式控制方法主要可以分為兩種:完全分布式控制方法和部分分布式控制方法。 (1)完全分布式控制 完全分布式控制方法是一種依靠無人機的自主性和相互協(xié)作的一種方法，由于無人機任務分配問題的復雜性，該方法相當于將復雜的問題分解成為一個個相對簡單的小問題，對每架無人機進行任務分配，接著就是將各個無人機的信息進行交互，對任務進行整體求解。如圖2. 3所示，完全分布式控制方法中我們把無人機看成具有決策能力的智能體，這樣無人機任務分配問題就轉化成為各個智能體之間任務的分配和決策。在這種結構中，無人機相對于集中式控制有很強的自主性，能夠對任務集信息和自身的信息進行采集和分析，并進行決策，在特定的情況下通過數(shù)據(jù)鏈與其它無人機進行數(shù)據(jù)交互，協(xié)作完成所需執(zhí)行的任務。 圖2.3完全分布式控制結構圖 這種控制方法中，無人機編隊內(nèi)各個無人機對所得到的信息進行相互的共享，得到所有的關于任務執(zhí)行的信息，最后整理分析所得到的信息對無人機編隊中的每一架任務分配任務集。由于無人機編隊中有多架無人機，在執(zhí)行任務中可能發(fā)生交叉沖突，即碰撞沖突，所以需要對它們進行考慮并消除。同時在這種控制方法中，無人機之間是通過數(shù)據(jù)鏈技術進行任務集數(shù)據(jù)的傳輸和共享，為的是更好的具有任務決策的實時性，所以數(shù)據(jù)量是相當大的，將隨著編隊內(nèi)無人機的數(shù)量呈指數(shù)增長。所以應用這種控制方法，編隊內(nèi)無人機的個數(shù)受到了很大的限制。 (2)部分分布式控制 部分分布式控制方法吸取了無人機任務分配控制方法中集中式控制和完全分布式控制方法各自的優(yōu)勢，對于解決多類型無人機編隊任務分配問題更為合理。經(jīng)過對集中式控制方法和分布式控制方法的比較，我們得出分布是控制方法是一種實時性較強的方法，能夠快速的對任務信息進行采集和分析，得到解決任務分配問題的具體方案，獲得的方案往往是局部最優(yōu)的，但不能得到全局最優(yōu)方案。而集中式控制方法恰恰相反，由于所有信息都要返回地面控制站進行匯總，所有能夠進行全面而詳細的規(guī)劃，從而獲得的方案一般都是全局最優(yōu)方案，但是實時性就很差啦。當前，國內(nèi)外很多院校和科研機構對集中式控制和分布式控制方法結合的問題進行了理論分析和實際驗證，對兩種方法進行了整合，得到了部分分布式控制方法，結構圖如圖2. 4所示。 2.3無人機任務分配模型分類 根據(jù)任務分配建模分類，現(xiàn)階段的模型主要有多旅行商問題[}2}(MultipleTraveling Sa-lesman Problem, MTSP)模型，通用分配問題[3}(Generalized AssignmentProblem, GAP)模型，車輛路徑問題[4}(Vehicle Routing Problem, VRP)模型，混合整數(shù)線性規(guī)劃[s},}6},}}},}s},}9}(Mixed Integer Linear Programming, MILP)模型以及CMTAP(Cooperative Multiple Task Assignment Problem)模型。 2.3.1多旅行商問題模型 通常，我們所說的旅行商問題是一個NP完全問題，具的定義如下:假設有a個旅行商人，方個城市，每個旅行商人都要沿著城市之間的道路訪問其中的一些城市，最后所有的旅行商人都要返回初始的城市，限制每個城市都要被訪問并且有且僅有一次，問題所要達到的目的是在完成對所有城市訪問的同時，總距離最短、完成任務時間最短、消耗最小、收益最大等。把旅行上問題模型應用到無人機任務分配中去，我們假設有一個二架無人機的無人機編隊，有二個目標任務的任務集，無人機編隊從同一個基地出發(fā)，沿著預先設定的飛行航路，完成所有的任務，每個任務只能被完成一次，最后考慮無人機的總航程，無人機完成任務的時間，無人機消耗的能力，完成任務的價值利益等。 2.3.2通用分配問題模型 通用分配問題模型考慮將二個任務分配給二個單體，每個任務只能給一個單體并且單體的資源受到限制。相當于二個任務分配給給一個無人機執(zhí)行并且無人機的資源，如最大任務數(shù)，二個無人機，每個任務只能最大航程受到限制。 2.3 3車輛路徑問題模型 我們對車輛路徑模型進行如下描述:假設有二輛貨車，每輛車的負載能力不同，它們從同一個基地出發(fā)，為二個目標點輸送貨物，每個目標點需要送達的貨物數(shù)量不同。最后，所有貨車回到出發(fā)點。車輛路徑問題模型[yo]要考慮送達的時間，貨物送達的消耗，完成輸送的價值等，并保證所有的貨物安全送達。 2.3.4混合整數(shù)線性規(guī)劃模型 混合整數(shù)線性利用線性化函數(shù)建立模型，模型描述簡潔、直接，有助于提高無人機任務執(zhí)行效率和生存能力，達到了任務分配的目的和初衷而且可以通過對約束條件的修正來滿足實際問題需要，但是模型規(guī)模不能過大。問題規(guī)模過大將導致計算量指數(shù)型增長，任務分配的實時性得不到保證。 2.3.5 CMTAP通用模型 隨著無人機能力不斷增強，無人機執(zhí)行任務的復雜程度也隨之增強，不同任務之間存在著復雜的時序以及時間約束。對于這一類復雜的任務集合，目前大多數(shù)任務分配模型無法對其進行有效的描述。一種CMTAP模型「川被引出，這種模型充分考慮一組無人機完成一系列針對地面目標的連貫任務，包括任務目標的識別、攻擊、毀傷評估等。 2.4靜態(tài)任務分配算法 在靜態(tài)環(huán)境中，無人機和任務都是確定的，不發(fā)生改變。在這樣的條件下，多無人機任務分配的算法主要有:群算法，市場機制算法和進化算法。 2.4.1群算法 群算法主要模仿自然界中各種生物的群體化行為，例如蟲群「12]和羊群。我們通過對蟲群群體化行為就行具體的研究分析，從而來簡單說明群算法的具體特點:所謂的昆蟲群的群體行動指的是昆蟲個體根據(jù)一些規(guī)律進行個別的運動，從而導致整個群體顯現(xiàn)出一種運動規(guī)則，在運動中昆蟲主要遵循三個準則:第一，實時監(jiān)測鄰近個體距離，防止產(chǎn)生交叉沖突，即防止和其它個體產(chǎn)生碰撞;第二，采集鄰近個體的信息，如速度，位置等;第三，保證和其它昆蟲的距離，不能太遠，而脫離群體。昆蟲以上的這些行為都是個體的行為，不是群體的運動，不過所有的個體都執(zhí)行這些準則，就會產(chǎn)生整體的運動趨勢。群算法中目前為止最為經(jīng)典就是蟻群算法[13],[14],[15],[16] (Ant Colony Optimization) , 1991年，意大利科學家Dorigo首先在其發(fā)表的研究成果中提到了蟻群算法。圖2.5可簡單說明蟻群算法的基本原理。 2.5蟻群算法原理圖 如圖所示，a點表示的是螞蟻的巢穴位置，別點表示的是食物的位置，有兩條路徑在巢穴和食物之間。假定有兩組數(shù)目相同的螞蟻同時由a點出發(fā)，沿著兩條路徑分別向著方點前進，剛開始沿著兩條路徑的概率是相等的，均為二分之一，設定螞蟻爬行的速度相同，螞蟻單位時間分泌的激素量相同。螞蟻就這樣往復的在這兩條路徑上來回搬運食物，但是由于路徑二明顯長于路徑一，所以路徑二上的激素的濃度將會明顯小于路徑一上的激素的濃度。由于路徑二的上的激素濃度較大，螞蟻就會越來越偏向于向路徑二前進，這樣在路徑一上留下來的激素也越來越多，激素的濃度不斷增加，直到最后，幾乎所有螞蟻都會沿著路徑一前進去尋找食物，這樣大大提高了螞蟻搬運食物的效率。 2.4.2市場類算法 市場中有許許多多的客戶，每個客戶依據(jù)自己的投資能力和預期效益而對市場中的項目進行投資，個別的客戶個體無法改變整個市場的走勢，但是把所有的客戶看作一個統(tǒng)一的大集合，就可以通過投資對整個的市場的走勢產(chǎn)生決定性的作用，即市場的發(fā)展或者是市場的消退。市場類算法把市場中的每個客戶可以看作智能體，在無人機的任務分配方法研究中得到了很廣泛的應用。Czil介紹了一種包含談判機制的市場類算法，無人機通過數(shù)據(jù)鏈技術相互傳遞信息，協(xié)商得出任務分配方案。在該類算法中，每架無人機完成一個任務都會產(chǎn)生收益，但是執(zhí)行時會消耗無人機的能力。得到與損失的差額就是無人機完成任務的利益，每架無人機都為了利益最大化而執(zhí)行任務。 2.4.3進化理論算法 最后一大類靜態(tài)任務分配算法是進化理論算法，該算法的理論依據(jù)是仿照自然界中生物種群進化，以優(yōu)勝劣汰的進化原則，將相對優(yōu)秀的生物個體保留下來，而相對差點的個體剔除出種群。遺傳算法是這一大類算法中使用最多，最為有名的算法。1975年，美國密歇根大學的教授首次在研究成果中提到了遺傳算法，之后，全世界很多國家的科研工作者對遺傳算法進行了理論研究和實際應用。遺傳算法仿照生物進化理論，才有染色體編碼方式進行任務分配方法的最優(yōu)化選擇。遺傳算法以決策變量的編碼作為運算對象，傳統(tǒng)的優(yōu)化算法往往直接采用決策變量的實際值，這是它的一個很大的特點。基于UAV多任務協(xié)同分配問題特定染色體編碼方式，遺傳算法采用兩種進化操作:選擇操作和交叉操作。有研究者在傳統(tǒng)的遺傳算法中使用鄰域搜索算法[m?；卩徲蛩阉髟?，運用對稱群結構描述UAV任務分配的搜索空間，運用右乘運算構造搜索鄰域，結禁忌搜索。相對于傳統(tǒng)遺傳算法、爬山能力強和全局迭代尋優(yōu)，易找到全局最優(yōu)點，實現(xiàn)了基于對稱群計算的UAV任務分配算法。 基于UAV任務分配問題特定的染色體編碼方式和適應度函數(shù)，本文采用如下 的進化操作: (1)選擇操作 進化算法的選擇是建立在對個體適應度的評價基礎之上的，本文采用經(jīng)典的比例選擇算子來實現(xiàn)該操作來實現(xiàn)該操作。比例選擇是一種有退還的隨機采樣方法，其基本思想是:每個個體中被選的概率與其適應度大小成正比，其具體的執(zhí)行過程如下 a.計算出種群中每一個個體的評價函數(shù)的值的，得到它們的總和; b.分別計算總裙子個體評價函數(shù)值的相對值，即各個個體被選中作為父代遺傳 到下一子代的概率; c.再使用類似賭博輪盤的操作(即產(chǎn)生0-1之間的隨機數(shù))，從而分別確定每 個個體被選中遺傳到下一代的概率。 (2)交叉操作 本文采用的交叉操作使用的是EA-PMX算法中的PMX交叉算子。UAV任務分配問題對交叉算子的設計要求是:對任意兩條染色體進行交叉操作后，能得到兩天新的，且具有實際意義的染色體序列。部分交叉映射(Partially MappedCrossover, PMX)算子是一種常見的交叉算子。 PMX算子的主要思想是:整個交叉過程分兩步完成，首先對個體編碼進行常規(guī)的雙點交叉操作，然后根據(jù)交叉區(qū)域內(nèi)各基因值得映射關系來修改交叉區(qū)域之外的各基因座的基因值，按照染色體的編碼，種群中的任一染色體表示為T=(tl,tZ,...tn)。 2.5動態(tài)環(huán)境中多任務重分配算法 在具體環(huán)境中，由于環(huán)境的動態(tài)性和不確定性以及協(xié)同控制的復雜性，使得任務開始后會出現(xiàn)許多無法預料的情況，因此，必須根據(jù)戰(zhàn)場態(tài)勢和編隊狀態(tài)的變化快速調整UAV編隊的任務計劃，通過動態(tài)重調度實現(xiàn)UAV之間的任務重分配，以真正適應復雜的作戰(zhàn)環(huán)境。因此，我們更多的使用到的是動態(tài)分配算法。UAV任務再分配的一般策略整個編隊的完全再分配局部調整分組基礎上的再分配。動態(tài)任務分配算法主要有:合同網(wǎng)算法、拍賣算法、聚類算法。 2.5.1合同網(wǎng)算法 為了更好的解釋合同網(wǎng)的概念，我們首先簡要介紹下什么是Agent智能體)。通常我們認為:Agent主要應用于動態(tài)環(huán)境中，他具有先進的設備，如傳感器，高性能機載電腦，先進的導航系統(tǒng)等，實時獲取自身的狀態(tài)信息，如形態(tài)，位置，負載等;任務集信息，如目標位置，目標數(shù)量，任務目標價值以及周圍的環(huán)境信息。通過對這些信息的總結，分析，與其他無人機進行信息共享交互，制定出任務分配方案并執(zhí)行。它具有高度的自治性和行動力，在分布式控制中被廣泛地應用。合同網(wǎng)一般有三大類任務執(zhí)行角色:招標者，投標者，中標者。 我們對合同網(wǎng)的一般理解為:首先是任務招標者有任務需要其他任務執(zhí)行者的能力來完成所需完成的任務，因此招標者就會向投標者通過信息交互發(fā)布任務請求，即所謂的招標行為;接著收到任務信息的投標者們先是評估自己的執(zhí)行能力和想要得到的收益，給出自己的投標值，即所謂的投標行為;最后招標者，整理分析投標者給出的投標值，遴選出最適合完成任務的投標者作為中標者。如下 圖表示了一個合同網(wǎng)方法的簡單框圖: 圖2.7 我們將合同網(wǎng)算法的具體步驟總結如下: (1)招標者傳送任務信息給投標者，包括任務數(shù)量，任務完成期限等; (2)投標者對招標者傳送的任務信息實時監(jiān)測，并對自己感興趣的任務進 行投標成為投標者; (3)管理Agent在一定的時間段內(nèi)對所收集的應標進行評估，根據(jù)評估結果 向其滿意的投標者分配任務; (4)任務執(zhí)行Agent確認該任務分配者提出的合同完成分配，形成承諾監(jiān)督 關系。 2.5.2拍賣算法 拍賣算法[ass]是在動態(tài)環(huán)境中分布式控制方法分配任務方法的又一種重要方法。拍賣法算法模擬具體的拍賣過程，在拍賣過程中各個智能體計算每一個任務的收益，消耗的能力，評價函數(shù)等。拍賣算法首先給出一個拍賣的具體先后次序，各個智能體按照次序去完成自己拍賣得到的任務集，最后得到整體的任務分配方案。在智能體能力范圍和約束條件之內(nèi)，拍賣法重新給出一個拍賣次序進行又一次的拍賣，根據(jù)評價函數(shù)評價新方案和舊方案，將較優(yōu)的方案留下來，如此周而往復，得到較好的解。 對于動態(tài)環(huán)境無人機任務分配方法中，我們主要關心的還是算法的實時性，算法的實時性不是說完成任務的時間越短越好，而是當任務環(huán)境改變的時候，包括任務集的改變和無人機集的改變，能夠快速的給出新的分配方案。而拍賣算法恰恰具有這種能力。 2.5.3聚類算法 聚類算法[[22],[23]主要研究的是如何根據(jù)目標位置、功能等屬性值將其分若干類別，以揭示目標之間的相互關系和差別，使得一個類別中的對象樣本有較高的相似度，而不同類別中對象樣本的屬性值差別較大。 聚類的定義如下: 給定一組數(shù)據(jù)D，把它劃分為若干聚類或者稱為簇 }C,} C2}..., CkI Ci}(2-4) 使得不同聚類中的數(shù)據(jù)盡可能的不相似而通一聚類中的數(shù)據(jù)盡可能地相似。K均值算法(也稱K-means算法)是一種最常用的動態(tài)聚類算法，它是一種基于劃分的迭代算法，在求解過程中，通過反復修改分類來達到最滿意的聚類結果;該算法的基本思想是:首先以一些初始點為聚類中心，對樣本集進行初始分類;判定分類結果是否能使一個確定的準則函數(shù)取得極值:如能，聚類算法結束;如不能，改變聚類中心，重新進行分類，并重復判定，所使用的準則一般是誤差平方和準則。[24]是一種基于ISODATA約束聚類。ISODATA算法是動態(tài)聚類的一種。動態(tài)聚類的特點在于，聚類過程通過不斷地迭代來完成，且在迭代中通常允許樣本從一個聚合類中轉移到另一個聚類中。ISODATA聚類的基本思想是，假定樣本集中的全體樣本分為m類，并選定K為初始聚類中心，然后根據(jù)最小距離原則將每個樣本分配到某一類中，之后不斷迭代，計算各類的聚類中心，并以新的聚類中心調整聚類情況，并在迭代過程中，根據(jù)聚類情況自動地進行類的合并和分裂。經(jīng)典K均值算法介紹 K均值算法(也稱K-means算法)是一種最常用的動態(tài)聚類算法，它是一種基于 劃分的迭代算法，在求解過程中，通過反復修改分類來達到最滿意的聚類結果; 第三章 靜態(tài)環(huán)境下無人機任務分配 對于給定任務和現(xiàn)有的無人機資源，確定參與執(zhí)行任務的偵察無人機、滅火無人機的數(shù)量，組成無人機編隊。無人機的任務分配可以定義為，基于一定的環(huán)境知識(例如，任務目標位置、威肋、區(qū)域位置等)和任務要求，為編隊中的各架無人機分配一個或一組有序的任務集(或目標、空間位置)，以便在完成最大任務的同時，使無人機編隊的整體效率達到最優(yōu)。無人機任務分配問題的解是任務區(qū)域各任務(或目標位置)的一個排列。由于其明顯的優(yōu)化組合特征，求解無人機任務分配的有效方法是設計出能在合理的計算時間內(nèi)找到最優(yōu)或近似最優(yōu)解的啟發(fā)式算法。 靜態(tài)環(huán)境指的是無人機集，任務目標集以及任務環(huán)境都保持不變。在這種情 況下，我們對無人機任務分配問題進行研究。 3.1任務分配場景和限制條件 3.1.1任務分配的場景 由于無人機在自然災害中的應用越來越廣泛，本文設定的任務分配場景就是多無人機協(xié)同森林滅火。在一個二維空間平面中，含有N1架偵察機和NZ架滅火機的小型無人機(每架無人機只能執(zhí)行一種任務，偵察或滅火)編隊對M處靜止目標，假定目標對無人機無威肋、，進行“偵察一滅火一滅火評估”。 3.1.2任務分配限制條件 在3.1.1無人機任務分配的場景下，并考慮實際情況，我們設定了以下限制條 件: (1)每架無人機只能執(zhí)行單一任務，任務包括偵察(監(jiān)視)或滅火; (2)無人機與地面控制站通過無線數(shù)據(jù)鏈路進行信息交互，無人機之間無通 信聯(lián)系; (3)各架無人機的任務分配和再分配由地面控制站執(zhí)行，有人參與方式; (4)各架無人機的航線規(guī)劃由地面控制站執(zhí)行，并將含有時間信息，任務信 息等的各航線點坐標發(fā)送給無人機，無人機嚴格按此航線飛行和執(zhí)行任務; 3.2多無人機任務分配的數(shù)學模型 3.2.1無人機任務集描述 無人機任務集TS可以用以下一個6元組來描述: TS=(ID, Act, Location, Min, Max/duration, State}(3一1) 在以上任務集當中:ID表示無人機的標識符，采用前綴+數(shù)字方式來標識編隊中的每一架無人機。前綴R表示偵察機，F(xiàn)表示滅火機。數(shù)字表示序號。例如R1表示1號偵察機，F(xiàn)2表示2號滅火機，依此類推; Act表示無人機執(zhí)行的動作，包括: (1)起飛(Take-off:無人機在時間窗口「Min, Max]起飛并到達指定位置Location ; (2)著陸CLand):無人機在時間窗口「Min, Max]返航至指定位置Location并 著陸; 3.2.2平面網(wǎng)格坐標系 設置一個Lx X Ly尺寸的平面網(wǎng)格，其中包含無人機編隊的整個飛行區(qū)域和 待滅火的目標。并假設 (1)在任意的時刻t，如果某個網(wǎng)格被填空，表示無人機可以安全地飛臨其 位置。 (2)在任意的時刻t，如果某個網(wǎng)格被填黑，表示無人機在其位置受到威脅， 無人機規(guī)劃航線應避免穿過該網(wǎng)格。例如，如圖1所示，網(wǎng)格(2, 4 )被填黑，網(wǎng) 格(2,4 )位置是一個危險位置。 第四章 動態(tài)環(huán)境下無人機任務分配 由于實際的環(huán)境是動態(tài)的，無人機，任務目標，和周圍環(huán)境都會發(fā)生改變，所以我們在無人機靜態(tài)任務分配的基礎上，需要對動態(tài)環(huán)境下無人機任務重新分配進行研究，無人機任務重分配，主要考慮的是任務重分配的“實時性”。 4.1動態(tài)任務重分配 4.1.1動態(tài)任務重分配的觸發(fā)條件 任務分配使得編隊中的每架無人機分配到一個有序任務集，它們通過在時間和空間上的協(xié)調，共同配合完成任務。隨著任務的執(zhí)行，戰(zhàn)場環(huán)境以及無人機編 隊的狀態(tài)可能發(fā)生改變，如: (1)任務改變 無人機編隊在執(zhí)行任務過程中，其任務集并不一定會是固定不變的。例如，一些在任務執(zhí)行前未被發(fā)現(xiàn)的新目標出現(xiàn)，如果這些新出現(xiàn)的任務被地面控制站操作人員確認為應納入無人機編隊的優(yōu)先任務時，則需進行任務再分配。又例如，編隊中的偵察機發(fā)現(xiàn)了新的危險，地面控制站須對無人機進行航線再規(guī)劃，如果新規(guī)劃的航線導致原先的制定的任務分配不能執(zhí)行時，則須進行任務再分配。 (2)無人機狀態(tài)改變 由于各種不確定因素(如無人機故障)，編隊中的各架無人機可能退出任務的 執(zhí)行，而它原先分配到的任務需要分配給其它無人機，這時，需要進行任務再分 酉己。 (3)地面控制站 地面控制站可在任何時刻對正在執(zhí)行的任務進行干預而觸發(fā)任務再分配。 4.1.2任務動態(tài)再分配采用的策略 可以采用三種形式進行任務動態(tài)再分配，包括: (1)整個編隊的完全再分配 此種方案如同起飛前的任務靜態(tài)分配，優(yōu)點是保證了全局最優(yōu);缺點是問題 規(guī)模較大時，計算時間長。 (2)局部調整 此種方案是任務再分配針對每架無人機單獨調整，優(yōu)點是任務再分配快速; 缺點是最優(yōu)性難于保證。 (3)分組基礎上的再分配 此種方案是上述兩種方案的折中，它首先對無人機和任務進行分組，然后進 行組內(nèi)任務再分配。 在我們的方案中，地面控制站操作人員可在三種方案中進行選擇，以最有利 于任務動態(tài)再分配。 4.1.3任務重分配的流程 靜態(tài)任務分配完成后，系統(tǒng)處于穩(wěn)定的任務執(zhí)行狀態(tài)，這時的任務不會發(fā)生變更。當條件發(fā)生變化，一些任務需要變更時，將觸發(fā)任務重分配，之后系統(tǒng)又回到穩(wěn)定狀態(tài)，等待整個系統(tǒng)任務完成或下一次重分配。整個重分配過程中系統(tǒng)狀態(tài)發(fā)生變化，同時系統(tǒng)中各執(zhí)行者的狀態(tài)也將受到影響。變化過程如圖4. 1:圖4.1任務重分配流程圖 4.1.4任務動態(tài)再分配需要考慮的因素 假設任務動態(tài)再分配只在現(xiàn)有無人機編隊中進行，即不給現(xiàn)有無人機編隊增 加新的無人機。這時，需要考慮的因素包括: (1)編隊中現(xiàn)有可執(zhí)行任務的無人機的種類及其數(shù)量 (2)主要考慮編隊中現(xiàn)有可執(zhí)行任務的無人機的種類及其數(shù)量是否滿足任務 分配的要求，例如，需要執(zhí)行新的攻擊任務時，但是，當前編隊中現(xiàn)有可執(zhí)行任 務的無人機無攻擊機，則不能完成任務。當然，也無需再進行任務分配工作。 (3)編隊中現(xiàn)有可執(zhí)行任務的無人機的當前位置和續(xù)航時間 4.1.5任務改變時的任務動態(tài)再分配算法 任務改變時的任務動態(tài)再分配算法如下: (1)由地面控制站操作人員確定參加新任務的無人機; (2)被確定參加新任務的無人機停止執(zhí)行現(xiàn)行任務，原地等待; (3)由地面控制站操作人員選擇任務動態(tài)再分配策略; 4.1.6無人機狀態(tài)改變時的任務再分配 當某一架無人機狀態(tài)異常時的任務動態(tài)再分配算法如下: (1)安排該架無人機返航并著陸; (2)確定該架無人機狀態(tài)改變使得該無人機不能繼續(xù)執(zhí)行的任務是哪一個任 務; (3)判斷該編隊小組中是否有同類無人機可以替代退出的無人機?若有，轉 下一步;否則，轉(5); 結 論 本次畢業(yè)設計的題目是無人機組群巡檢滅火系統(tǒng)的設計，直到今天，畢業(yè)設計總算接近尾聲了，通過這次對于無人機組群巡檢滅火系統(tǒng)的設計，使我們充分把握的設計方法和步驟，不僅復習所學的知識，而且還獲得新的經(jīng)驗與啟示，在各種軟件的使用找到的資料或圖紙設計，會遇到不清楚的作業(yè)，老師和學生都能給予及時的指導，確保設計進度，本文所設計的是無人機組群巡檢滅火系統(tǒng)的設計，通過初期的方案的制定，查資料和開始正式做畢設，讓我系統(tǒng)地了解到了所學知識的重要性，從而讓我更加深刻地體會到做一門學問不易，需要不斷鉆研，不斷進取才可要做的好，總之，本設計完成了老師和同學的幫助下，在大學研究的最感謝幫助過我的老師和同學，是大家的幫助才使我的論文得以通過。 參考文獻 [1] 徐灝等.機械設計手冊(第2、3冊)[M](第二版）.北京：機械工業(yè)出版社，2003:98—100? [2] 程悅蓀.無人機組群巡檢滅火系統(tǒng)的設計[M].北京：中國農(nóng)業(yè)出版社，1981:67—69?? [3] 周紀良.傳動系統(tǒng)的設計[M].北京：機械工業(yè)出版社，1991:102—105?? [4] 吉林工業(yè)大學教研室編.無人機的構造[M].北京：中國農(nóng)業(yè)出版社，1982:209—211? [5] 成大先主編.機械設計手冊——減（變）速器·電機與電器[M].北京：化學工業(yè)出版社，1999:81—83? [6] 朱冬梅.畫法幾何及機械制圖[M].北京：高等教育出版社，2000:303—305? [7] 陳立德.機械設計基礎[M].北京：高等教育出版社，2002:222—225? [8] 陳立德.機械設計基礎課程設計指導書[M].北京：高等教育出版社，2002:44—46? [9] 劉勁.機械制圖國家標準[M].北京：機械工業(yè)出版社，2000:59—61? [10] 陳立周.機械優(yōu)化設計方法[M].北京：冶金工業(yè)出版社，1985:77—79?? [11]《拖拉機》編輯部主編.無人機組群巡檢滅火系統(tǒng)的設計和計算[M].上海：上海科學技術出版社，1980:109—114 [12] 周紀良.無人機組群巡檢滅火系統(tǒng)結構型式和結構圖譜[J].農(nóng)業(yè)機械學報，1979：47—63? [13] 周紀良，孔維恭，于瑞璽.無人機組群巡檢滅火系統(tǒng)的優(yōu)化的研究[J].農(nóng)業(yè)機械學報，1988:32—39? [14] 高象平，李齊隆等.無人機組群巡檢滅火系統(tǒng)的零部件優(yōu)化設計[M].廣州：廣東科技出版社，1987:66—70?? [15] Charles W. Beardsly, Mechanical Engineering, ASME, Regents Publishing Company,Inc,1998.45—49 [16] Queen Y. Beardsly, Mechanical Engineering, Regents Publishing Company,Inc,2003.99—103 致 謝 在此論文完成之際，我的心里感到特別高興和激動，在這里，我打心里向我的導師和同學們表示衷心的感謝！因為有了老師的諄諄教導，才讓我學到了很多知識和做人的道理，由衷地感謝我親愛的老師，您不僅在學術上對我精心指導，在生活上面也給予我無微不至的關懷支持和理解，在我的生命中給予的靈感，所以我才能順利地完成大學階段的學業(yè)，也學到了很多有用的知識，同時我的生活中的也有了一個明確的目標。知道想要什么，不再是過去的那個愛玩的我了。導師嚴謹?shù)闹螌W態(tài)度，創(chuàng)新的學術風格，認真負責，無私奉獻，寬容豁達的教學態(tài)度都是我們應該學習和提倡的。通過近半年的設計計算，查找各類無人機組群巡檢滅火系統(tǒng)的相關資料，論文終于完成了，我感到非常興奮和高興。雖然它是不完美的，是不是最好的，但在我心中，它是我最珍惜的，因為我是怎么想的，這是我付出的汗水獲得的成果，是我在大學四年的知識和反映。四年的學習和生活，不僅豐富了我的知識，而且鍛煉了我的個人能力，更重要的是來自老師和同學的潛移默化讓我學到很多有用的知識，在這里，謝謝老師以及所有關心我和幫助我的人，謝謝大家。 另外也感謝我的父母，朋友和同學們的幫助。在做設計感覺受挫，枯燥與迷茫時，是他們在悉心的為我釋放壓力，鼓勵我不要氣餒，勇敢面對。每周一次和父母的通話，與朋友和同學的長談后都使我精神放松，斗志倍增，以飽滿的熱情重新投入到工作中去，感謝他們，正是他們的不懈支持和充分理解才能使我順利完成畢業(yè)設計。 19