【正文】 國防科學技術(shù)大學本科畢業(yè)論文本 科 畢 業(yè) 論 文 題目： 基于RRT的無人機實時避障算法實現(xiàn) 學員姓名： 王琳 專業(yè)： 仿真工程 培養(yǎng)類型： 工程技術(shù)類 學號： 200803012039 所屬學院： 機電工程與自動化學院年級： 2008級 指導教員姓名： 牛軼峰 職稱： 講師 所屬單位： 機電工程與自動化學院自動化研究所 國防科學技術(shù)大學訓練部制ii目　錄目　錄 I圖表目錄 III摘　要 iAbstract ii第一章 緒　論 1 課題研究背景 2 國內(nèi)外研究進展 5 3 3 6第二章 無人機實時避障路徑規(guī)劃問題分析與建模 7 7 9，優(yōu)劣分析 10第三章 基于改進RRT的無人機實時避障路徑規(guī)劃 21 RRT基本原理及其應用 21 結(jié)合問題特性的RRT 22 基于RRT的避障路徑規(guī)劃 37 改進算法的實時性 37第四章 Matlab仿真實驗驗證 43 實驗方案 算例測試第五章 結(jié)論致　謝 44參考文獻 45附　錄 47圖表目錄 無人機自主空中防撞系統(tǒng)主要功能模塊 11圖22 多種算法的特征提取流程 12 RRT的節(jié)點擴展示意圖 14 改進的RRT節(jié)點擴展 16 基于改進RRT的航跡規(guī)劃算法描述 RRT算法，控制避障安全距離實驗結(jié)果 21 改進RRT算法，控制避障安全距離實驗結(jié)果 22 RRT算法，控制搜索步長實驗結(jié)果 24 改進 RRT算法，控制搜索步長實驗結(jié)果 25，步長與擴展節(jié)點數(shù)的關(guān)系 26，步長與規(guī)劃時間的關(guān)系 27 搜索步長為5，避碰安全距離與擴展節(jié)點數(shù)的關(guān)系 2829 搜索步長為5，避碰安全距離與規(guī)劃時間的關(guān)系 2930 31 無人機重規(guī)劃的航跡與威脅航跡 323重規(guī)劃的航跡與威脅航跡 3435 摘　要在預定路徑下，自主避障式的航跡規(guī)劃是無人機執(zhí)行區(qū)域飛行任務的有效保證。航跡規(guī)劃算法是無人機關(guān)鍵技術(shù)之一，也是任務規(guī)劃系統(tǒng)核心之一。本文闡述了無人機三維航路規(guī)劃面臨的關(guān)鍵性問題及發(fā)展趨勢，針對非協(xié)助式的三維障礙規(guī)避問題，提出了一種基于快速隨機擴展樹（RRT）方法的三維路徑規(guī)劃算法。由于無人機避障的空間搜索范圍大，三維航跡規(guī)劃一直是航跡規(guī)劃中的難點，而只有進行三維規(guī)劃才能提高避障的實時性和靈活性。本文在RRT的基礎(chǔ)上，通過改進隨機擴展樹的節(jié)點選擇，引入啟發(fā)式信息，結(jié)合考慮無人機的性能特點等方法降低了航跡規(guī)劃的時間代價和擴展的節(jié)點數(shù)，取得了較好的效果。仿真測試結(jié)果表明，算法簡單、快速、有效地規(guī)劃出了三維可行航跡。關(guān)鍵詞：實時避障；三維路徑規(guī)劃；快速隨機擴展樹（RRT）AbstractOn condition that the scheduled path given , Autonomous Route Planning is the prerequisite for Unmanned Aerial Vehicles (UAVs) to perform area search mission effectively . Path planning is essential of both UAVs and mission planning system . A conclusion of the key problems and the development trend of them are elaborated . With regard to the noncooperant 3D route planning , a modified (Rapidlyexploring Random Tree) RRTbased UAV route planning algorithm is proposed . It is very difficult to implement 3D route planning of Unmanned Air Vehicle (UAV)because of the large searching space .Precise 3D route planning can increase the realtime planning and flexibility . Based on RRT algorithm , the modified RRT method has introduced heuristic information , improved the extension of RRT node , and took UAV’s properties into consideration , which can reduce the node number in search tree and time cost .It has been proved to be successful . Keywords: realtime planning , 3D route planning , Rapidlyexploring Random Tree第一章 緒　論　課題研究背景無人機（Unamanned Aerial Vehicle，UAV）是一種無人駕駛、動力驅(qū)動、可重復使用的飛行器。目前，無人機已廣泛使用于情報偵察、通信中繼、目標搜索與跟蹤和對地攻擊等各種作戰(zhàn)任務中，并發(fā)揮了重大作用。無人機實時避障是無人機在感知周圍靜態(tài)與動態(tài)障礙的基礎(chǔ)上，為避免發(fā)生碰撞，或者產(chǎn)生沖突事件，而進行實時規(guī)避機動的行為。在避開障礙之后，無人機重新恢復到安全狀態(tài)，按預先規(guī)劃的航線飛行，或者執(zhí)行既定的作戰(zhàn)任務。無人機飛行途中遇到的障礙可分為協(xié)作式障礙和非協(xié)作式障礙。協(xié)作式障礙是指可以通過信息共享來實現(xiàn)避碰和防撞。非協(xié)作式障礙是指無人機通過自身傳感器自主檢測到的障礙，并且無法通過信息共享來避開這類障礙。隨著無人機系統(tǒng)技術(shù)的不斷發(fā)展，眾多功能各異的無人機被廣泛應用于各種軍事和非軍事行動中。因此，對無人機實時感知并避開飛行途中的障礙和威脅的研究，作為無人機安全飛行的保障及實現(xiàn)其自主能力的關(guān)鍵技術(shù)之一，正引起各國重視。然而，現(xiàn)有的避障技術(shù)并不能滿足無人機實現(xiàn)高等級自主控制的需求，迫切需要研究面向無人機的實時避障算法。針對未來無人機自主控制的發(fā)展以及無人機避障行為決策技術(shù)的需求，利用RRT算法實現(xiàn)無人機的實時避障路徑規(guī)劃問題是本課題的重點?！鴥?nèi)外研究現(xiàn)狀無人機感知規(guī)避系統(tǒng)可以劃分為五個主要功能模塊：察覺、檢測、感知、生成逃逸機動， 無人機自主空中防撞系統(tǒng)主要功能模塊（1） 察覺功能。系統(tǒng)監(jiān)視環(huán)境，并收集入侵者當前合適的狀態(tài)信息，例如，飛機位置、速度、朝向等。（2） 檢測功能。系統(tǒng)獲取察覺數(shù)據(jù)，并處理得到有用信息，發(fā)現(xiàn)并管理無人機可能遇到的碰撞風險。（3） 感知功能。監(jiān)視環(huán)境態(tài)勢，在危急情況下取得飛機管控權(quán)，并在情況恢復正常時歸還控制權(quán)。（4） 生成逃逸航線。探測到將可能發(fā)生沖突碰撞時，生成逃逸航線和實現(xiàn)逃逸機動的功能被激活，并決定采取什么行為如何機動規(guī)避。（5） 實現(xiàn)逃逸機動。考慮無人機平臺的性能，完成規(guī)避機動行為。圍繞第四和第五個功能模塊，目前，國內(nèi)外研究的避障路徑規(guī)劃問題主要算法大致分為五類，即預定義避障方法，基于協(xié)議的分布式避障方法，逃逸航線優(yōu)化方法，勢場方法，基于視覺的避障方法等。（1）預定義避障方法這類方法基于一套固定的預定義規(guī)則實施避障，優(yōu)點是避障反應時間短，缺點是規(guī)劃處的逃逸機動動作并不很有效，也不夠優(yōu)化。當出現(xiàn)未預料到的障礙時，很難改變已經(jīng)下指令機動的動作。（2）基于協(xié)議的分布式避障方法這類方法很好的解決了多無人機編隊的避碰航行問題。多機間共享位置、速度、航向等信息，基于一套事先定好的規(guī)則進行決策。這類方法是分布式的，能保證飛行安全，但是可能生成不必要的較長航線，從而延長完成任務的時間（3）逃逸航線優(yōu)化方法這類方法將避障問題建模為優(yōu)化問題，從而各種優(yōu)化方法可用于解決此類問題。這類方法將無人機機的運動學模型與一套約束條件相結(jié)合，然后基于優(yōu)化約束計算出最優(yōu)的策略。防撞系統(tǒng)并不是試圖給出一條逃逸航線，相反，而是請求一個爬升或俯沖機動。這種思想意味著，系統(tǒng)知道不考慮威脅的路徑不安全，但它只在發(fā)現(xiàn)障礙威脅時才尋找一條避障航線，否則就一直向著目的地飛行。此外，還有其他一些優(yōu)化方法，例如遺傳算法，專家系統(tǒng)，模糊控制等，都更為復雜，需要大量的規(guī)則來覆蓋所有可能的情形。因此，可能導致需要強大的計算處理能力。（4）勢場算法勢場算法最早由Khatib提出，這類方法在飛行器之間建立勢場，將飛行器看做一個帶電粒子，利用飛行器間的斥力生成逃逸航線。這類方法也被視為一類路徑規(guī)劃算法，通過對先前的路徑進行濾波來生成新的航線。但這類方法可能使機動動作在執(zhí)行過程中突然中斷，而且需要極高精度的飛行導航，導致增加了問題的復雜性。（5）基于視覺的避障方法這類方法主要基于圖像特征和光流分布等實現(xiàn)障礙規(guī)避。Brandon采用圖像特征跟蹤方法研究小型無人機的避障問題。他首先利用遺傳算法生成一條可以避開所有已知障礙的航路，然后在無人機飛行過程中，利用機載前視攝像機檢測障礙。通過圖像的三維成像粗略估計障礙位置，利用滑模控制原理控制飛行器避開障礙。研究結(jié)果顯示，避障成功率達到96%。國外？國內(nèi)西北工業(yè)大學王振華等人進行了基于改進概率地圖的無人機實時避障研究。針對無人機路徑規(guī)劃問題，以等高線地圖作為任務空間，提出了一種新的采樣模型，在該模型框架下，依據(jù)適當?shù)囊?guī)則構(gòu)造臨近點集，便可以避免相交檢驗，提高了路徑規(guī)劃速度。姚遠等人針對不同屬性的障礙物所構(gòu)成的威脅分布模型，提出了一種基于稀疏A*搜索算法預規(guī)劃和改進人工勢場相結(jié)合的無人機動態(tài)避障算法。仿真結(jié)果表明，該方法能夠規(guī)劃出給定威脅指標下的全局最優(yōu)路徑并達到良好的動態(tài)規(guī)避性能。李耀軍等人基于多源信息融合對無人機感知與規(guī)避做了深入研究。通過多傳感器信息融合技術(shù)結(jié)算并共享無人機與有人機的坐標和實時運動狀態(tài)，利用多模態(tài)圖像的優(yōu)勢互補，實現(xiàn)晝夜、遠距離、高分辨率的目標檢測、識別與跟蹤，提高無人機感知與規(guī)避的實時性與可靠性。除此之外，周煒等人提出了基于層次分解策略無人機編隊避障的方法。張躍東等人提出了基于單目視覺的無人機障礙探測算法。王一凡等人提出了一種用于小型無人機避障的快速視差測距方法。宗玲蓓等人提出了基于MAS的無人機編隊飛行智能優(yōu)化控制。 無人機實時避障路徑規(guī)劃技術(shù)的發(fā)展趨勢針對無人機實時避障路徑規(guī)劃問題，主要在兩方面開展研究，一方面，研發(fā)適用于無人機的新型避障系統(tǒng)，提高無人機自主感知能力；另一方面，基于不同類型的傳感器，對規(guī)避問題進行數(shù)學建模，深入研究問題和關(guān)鍵技術(shù)，實現(xiàn)效率較高的規(guī)避控制算法。另外，基于各類先進的無人機飛行平臺，國外的研究已經(jīng)進行了一些實驗驗證，而不僅僅停留在仿真階段。國內(nèi)研究無人機感知與規(guī)避問題并沒有完全滿足無人機進入民用空域飛行的需求，關(guān)鍵在于無人機自主決策的智能性仍受到質(zhì)疑。隨著人工智能、機器視覺、機器人、傳感器技術(shù)的發(fā)展，無人機感知與規(guī)避問題有望得到更好的解決，從而為大幅度提升無人機自