無人智慧運載器航路規劃方法及其應用（簡體書）

無人智能運載器是一種無人操作的、全自主或半自主的、智能化的運載體，是一種特殊的智能機器人。無人智能運載器航路規劃技術主要解決運載器在任務執行前和執行過程中行進的問題，是決定無人智能運載器智能化、自主化水平高低的關鍵技術之一。《無人智能運載器航路規劃方法及其應用》整理作者課題組近年來的部分研究成果，深入全面介紹了基于蟻群優化的航路規劃方法、基于空間彈性繩算法的航路規劃方法、基于粒子群優化算法的航路規劃方法、基于協同進化的航路規劃方法、基于螢火蟲算法的航路規劃方法，詳細給出了各種航路規劃方法的基本思想、流程和仿真結果。

《無人智能運載器航路規劃方法及其應用》可供機器人、自動化、計算機、人工智能等領域科技人員參考，也可作為相關專業本科生或研究生的教材和參考書。

《智能科學技術著作叢書》序
前言
第1章　概述 1
1.1　引言 1
1.2　無人智能運載器 2
1.2.1　無人機 2
1.2.2　無人地面車 3
1.2.3　無人水面艇 3
1.2.4　無人潛器 4
1.3　航路規劃技術 5
1.4　本書結構 7
第2章　基于蟻群優化的航路規劃方法 8
2.1　蟻群算法 8
2.1.1　產生與發展 8
2.1.2　生物學原理 9 《智能科學技術著作叢書》序
前言
第1章　概述 1
1.1　引言 1
1.2　無人智能運載器 2
1.2.1　無人機 2
1.2.2　無人地面車 3
1.2.3　無人水面艇 3
1.2.4　無人潛器 4
1.3　航路規劃技術 5
1.4　本書結構 7
第2章　基于蟻群優化的航路規劃方法 8
2.1　蟻群算法 8
2.1.1　產生與發展 8
2.1.2　生物學原理 9
2.1.3　蟻群優化元啟發式算法 11
2.1.4　蟻群算法與其他仿生優化算法的比較 17
2.2　水下運載器三維空間航路規劃問題描述 18
2.3　環境建模 20
2.3.1　三維海底地形的構造 20
2.3.2　三維環境空間的抽象建模 22
2.4　基于離散域蟻群算法的三維空間航路規劃方法 24
2.4.1　算法設計 24
2.4.2　算法仿真與分析 30
2.5　基于連續域蟻群算法的三維空間航路規劃方法 39
2.5.1　算法設計 40
2.5.2　算法仿真與分析 43
第3章　基于空間彈性繩算法的航路規劃方法 49
3.1　空間彈性繩算法建模 49
3.1.1　彈性繩的定義 49
3.1.2　運動性質建模 50
3.1.3　彈性繩算法流程 52
3.1.4　收斂性分析 53
3.1.5　收斂速度分析 60
3.2　球形障礙環境下航路規劃方法 66
3.2.1　球形障礙環境空間模型 67
3.2.2　收縮、滑動和碰撞的計算 67
3.2.3　彈性繩算法的計算步驟 69
3.3　海底地形障礙環境下航路規劃方法 71
3.3.1　真實海底地形環境空間模型 71
3.3.2　收縮、滑動和碰撞的計算 72
3.3.3　彈性繩算法的計算步驟 75
3.4　仿真實驗及分析 77
3.4.1　收斂性仿真實驗 77
3.4.2　收斂速度仿真實驗 84
3.4.3　球形障礙環境下航路規劃 91
3.4.4　海底地形障礙環境下航路規劃 95
第4章　基于粒子群優化算法的航路規劃方法 99
4.1　粒子群優化算法 99
4.1.1　算法原理 99
4.1.2　算法特點及研究現狀 101
4.1.3　PSO在航路規劃中的應用 103
4.2　一種極坐標環境下的粒子群航路規劃方法 108
4.2.1　極坐標環境建模 108
4.2.2　航路規劃方法設計 113
4.2.3　仿真實驗及分析 118
4.3　動態已知環境下的局部航路規劃方法 121
4.3.1　動態環境建模方法 121
4.3.2　局部航路規劃避障模型 122
4.3.3　基于PSO算法的避碰策略及分析 125
4.3.4　仿真實驗及分析 127
4.4　動態未知環境的局部航路規劃 128
4.4.1　滾動窗口航路規劃方法 129
4.4.2　基于觀測窗口的局部航路規劃方法 131
4.4.3　仿真實驗及分析 136
4.5　基于PSO的多航路規劃方法 138
4.5.1　算法的基本思想 139
4.5.2　多航路規劃算法設計 139
4.5.3　粒子群的多樣化 140
4.5.4　多群體的隔離進化 142
4.5.5　仿真實驗及分析 143
第5章　基于協同進化的航路規劃方法 145
5.1　協同進化算法 145
5.1.1　算法基本特征與類型 145
5.1.2　算法基本框架 150
5.1.3　算法動力學描述 151
5.1.4　協同進化算法與其他進化算法的對比分析 152
5.2　多飛行器協同航路規劃問題建模 154
5.2.1　問題描述 154
5.2.2　問題建模 154
5.3　多飛行器協同航路規劃方法設計 156
5.3.1　協同航路規劃基本流程 156
5.3.2　航路編碼和種群初始化 158
5.3.3　適應度函數設計 159
5.3.4　進化操作算子設計 162
5.3.5　算法流程 168
5.3.6　仿真實驗與分析 169
第6章　基于螢火蟲算法的航路規劃方法 172
6.1　螢火蟲算法 172
6.1.1　基本思想 172
6.1.2　數學描述 173
6.1.3　算法流程 174
6.1.4　算法性能分析 174
6.2　螢火蟲算法改進研究 181
6.2.1　基本螢火蟲算法問題分析 181
6.2.2　參數自適應調整策略 181
6.2.3　自主飛行策略 184
6.2.4　隨機步長改進方法 184
6.2.5　改進算法描述 185
6.2.6　仿真實驗 186
6.3　基于螢火蟲的三維航路規劃方法 192
6.3.1　航路表達 192
6.3.2　評價函數設計 194
6.3.3　螢火蟲算法編碼 194
6.3.4　航路規劃流程設計 195
6.3.5　仿真實驗 196
6.4　基于混合算法的運載器三維航路規劃方法 201
6.4.1　混合算法描述 201
6.4.2　算法編碼與執行流程 201
6.5　仿真實驗 203
6.5.1　算法有效性測試 203
6.5.2　迭代次數對規劃結果影響實驗 205
6.5.3　種群規模對規劃結果影響實驗 206

第1章　概 述
1.1　引 言
1920年，捷克斯洛伐克作家卡雷爾?恰佩克在他的科幻小說《羅薩姆的機器人萬能公司》中，根據捷克文robota（原意為“勞役、苦工”）和波蘭文robotnik（原意為“工人”），創造出了機器人robot這個詞，其表達的意思是使用一種機器代替人做苦工、服勞役，來減輕人的勞動強度和痛苦。1967年，在日本召開的第一屆機器人學術會議上，森政弘與合田周平提出“機器人是一種具有移動性、個體性、智能性、通用性、半機械半人性、自動性、奴隸性等7個特征的柔性機器”。1987年，國際標準化組織將工業機器人定義為“工業機器人是一種具有自動控制的操作和移動功能，能完成各種作業的可編程操作機”。中國科學家對機器人的定義是“機器人是一種自動化的機器，所不同的是這種機器具備一些與人或生物相似的智能能力，如感知能力、規劃能力、動作能力和協同能力，是一種具有高度靈活性的自動化機器”。
現代機器人的研究始于20世紀中期。1954年，美國的德沃爾最早提出了工業機器人的概念；1959年，美國英格伯格和德沃爾制造出世界上第一臺工業機器人，取名為“尤尼梅遜”，其含義為“萬能自動”；1962年，美國AMF公司推出了“Verstran”，UNIMATION公司推出了“Unimate”，這是機器人產品最早的實用機型。這一階段的機器人主要用于工業領域，稱為工業機器人。隨著傳感器的應用，提高了機器人的可操作性，產生了有“感覺”的機器人。1962年，托莫維奇和博尼在“靈巧手”上使用了壓力傳感器；1963年，麥卡錫在機器人中加入視覺傳感系統，并在1965年幫助MIT推出了世界上第一個帶有視覺傳感器，能識別并定位積木的機器人系統。隨著計算機技術、電子技術、智能理論的不斷進步，機器人開始向著智能化、自主化方向發展，人們逐步認識到機器人技術的本質是感知、決策、行動和交互技術的結合。隨著人們對機器人技術智能化本質認識的加深，機器人技術開始源源不斷地向人類活動的各個領域滲透。結合這些領域的應用特點，人們發展了各式各樣的具有感知、決策、行動和交互能力的特種機器人和各種智能機器。
無人智能運載器是一種無人操作的、全自主或半自主的、智能化的運載體。它是一種特殊的智能機器人，最早由于軍事應用需求而提出，主要包括無人機（unmanned aerial vehicle，UAV）、無人地面車（unmanned ground vehicle，UGV）、無人水面艇（unmanned surface vessel，USV）和無人潛器（unmanned underwater vehic，UUV）等多種類型。在近幾次的局部戰爭中，無人系統漸漸發揮越來越重要的作用，其突出表現受到了各方普遍關注。近些年，無人智能運載器已開始由軍事應用轉向社會安全、大地測繪、海洋監測、海底勘探和救援等民用領域，漸漸走進了人們的日常生活。航路規劃技術是決定無人智能運載器智能化、自主化水平高低的關鍵技術之一，主要解決無人智能運載器在任務執行前和執行過程中的行進問題。該技術目前已經受到越來越多國內外學者和工程研究人員的關注，并已成為無人智能運載器研究的熱點問題之一。
1.2　無人智能運載器
1.2.1　無人機
無人機是一種利用無線電遙控設備和機載程序控制裝置操縱的不載人飛機，如圖1.1和圖1.2所示。機上無駕駛艙，但安裝有自動駕駛儀、程序控制裝置等設備。地面、艦艇上或母機遙控站人員可以通過雷達等設備對其進行跟蹤、定位、遙控、遙測和數字傳輸。無人機目前已廣泛用于空中偵察、監視、通信、反潛和電子干擾等。

圖1.1　美國捕食者無人機 圖1.2　中國ASN-206
無人機的誕生可以追溯到1914年。第一次世界大戰期間，英國的卡德爾和皮切爾兩位將軍向英國軍事航空學會提出了一項建議：研制一種不用人駕駛，而用無線電操縱的小型飛機，使它能夠飛到敵方某一目標區上空，將事先裝在小飛機上的炸彈投下去。1915年，美國的斯佩里公司和德爾科公司就研制出第一架無人機，取名為“空中魚雷”。該無人機不僅成功地進行了試飛，而且裝有136kg炸藥，成功地進行了攻擊目標試驗。在第二次世界大戰中，美國陸軍航空隊曾大量使用無人靶機，并在太平洋戰場上使用過攜帶重型炸彈的活塞式發動機無人機對日軍目標進行轟炸。第二次世界大戰結束后，隨著航空技術的飛速發展，無人機家族也逐漸步入其鼎盛時期。時至今日，世界上研制生產的各類無人機已達近百種，還有一些新型號正在研制中。
1.2.2　無人地面車
無人地面車（圖1.3和圖1.4）是集環境感知、動態決策與規劃、智能控制與執行多功能于一體的綜合系統。從構成上可分為四部分：用來提供機動性能的車輛底盤、集成有多種傳感器和電子設備的硬件平臺、具有人工智能的系統軟件、適應不同需求的任務載荷等。目前，無人地面車輛主要參加或承擔如爆炸物等危險品的探測與處理、戰場偵察與監視、目標搜索與定位、后勤運輸和物資裝卸、工程作業、清除障礙物、危險區傷員救援后送等任務。

圖1.3　美國Talon無人地面車 圖1.4　以色列MTGR無人地面車
無人地面車早在第二次世界大戰期間就已經出現。納粹德國在東線戰場上投入了幾類無人戰車用于爆破地雷。20世紀50年代后期開始，蘇聯展開了大規模的無人地面車輛研究。20世紀80年代初，在政府部門的支持下，美國斯坦福大學、麻省理工學院等研究機構開展了無人地面車輛的研究。21世紀初，機器人技術、計算機技術和傳感器技術取得長足進步，英國、法國、日本、韓國、以色列等國也都展開了無人地面車輛的研制，并取得了一定成果。目前，德國在無人地面車輛環境感知技術方面較突出，新加坡在視覺信息處理技術、自動駕駛控制技術方面具有一定優勢，美國則在無人地面車輛的總體發展水平上領先于其他國家。無人地面車輛的進步和發展需要感知、導航、信息融合、規劃、通信、控制、決策和機械制造等眾多技術領域發展的推動，它是信息技術與工業技術高度復合發展的產物。
1.2.3　無人水面艇
無人水面艇（圖1.5和圖1.6）是一種具有自主規劃、自主航行能力，并可自主完成環境感知、目標探測等任務的無人操縱水面運動平臺。主要用于執行危險以及不適于有人船只執行的任務。一旦配備先進的控制系統、傳感器系統、通信系統和武器系統，無人水面艇就可以執行偵察、巡邏、排雷、反潛作戰、反恐攻擊等軍事任務，還可進行搜救、導航、水文地理勘察等非軍事任務。

圖1.5　美國“斯巴達偵察兵”USV 圖1.6　中國天象1號USV
美國海軍從20世紀90年代開始研究無人水面艇。2007年，美國海軍發布了《海軍無人水面艇主計劃》。該計劃從滿足美國海軍戰略計劃、艦隊發展以及國防部到2020年部隊轉型的需求等方面，詳細介紹了美國海軍未來無人水面艇的發展計劃，賦予無人水面艇7項任務，同時還界定了無人水面艇的船型、尺寸和標準等要素，這標志著美國無人水面艇走上正規發展階段。以色列在無人水面艇技術方面也一直處于領先地位。其研制的“保護者”型無人水面艇已經開始批量生產，并裝備部隊。新加坡海軍是它的第一個海外用戶，在一次演習中，他們利用登陸艦搭載兩艘“保護者”無人水面艇進行海上保衛和封鎖行動，據新加坡國防部稱，“保護者”無人水面艇是“非常高效的”。目前，德國、法國、英國、中國、日本、意大利和葡萄牙等國也在積極投入無人水面艇的研究中，并已取得了一定的成果。
1.2.4　無人潛器
無人潛器（unmaned underwater vehicle，UUV）是將人工智能、自動控制、模式識別、信息融合和系統集成等技術應用于傳統的載體上，在無人駕駛的情況下自主地完成復雜海洋環境中預定任務的水下航行器，如圖1.7所示。按照航行控制方式的不同，UUV可以分為兩大類：一類是有纜UUV，又稱為水下遙控運載工具（remotely operated vehicle，ROV）；另一類是無纜UUV，又稱為水下自主式無人運載工具（autonomous underwater vehicle，AUV），AUV代表了UUV的發展方向。按用途的不同，UUV又可分為反潛型無人潛航器、偵察監視型無人潛航器、反水雷型無人潛航器、通信型無人潛航器和多用途無人潛航器等。

圖1.7　ECA公司的K-STER無人潛艇
UUV發展初期主要是用于深水勘探、沉船打撈、水下電纜鋪設和維修等民用領域。近年來，隨著平臺、推進器、導航和控制系統的發展，以及傳感器技術的進步，無人平臺的軍事應用得到高度重視，UUV在水下偵察、水下通信和反潛、反水雷作戰、信息作戰等領域的應用得到了空前發展。目前，針對某種特殊需求，配置專用設備，完成特定任務的UUV仍是無人潛航器發展的主流。但是，專用UUV在續航能力、操控靈活性等方面難以兼顧，無法全面滿足軍事應用領域多層面的作戰需求。隨著傳感器技術、智能控制技術和精密儀器技術的發展，多功能通用型UUV將成為新的熱點。另外，利用傳感器組合和配置技術，通過建立大范圍的通信網絡，UUV相互間及UUV與其他平臺之間的通信，可以實現綜合任務管理、遠程智能控制和態勢協同等。通過群體作業共同完成復雜任務，將成為UUV的發展方向。
1.3　航路規劃技術
航路規劃是在一定的障礙物環境中給定初始位置 和目標位置 ，按照一定的尋優策略規劃出從初始位置 無碰撞地到達目標位置 的路徑。它屬于人工智能的范疇，其實質是基于抽象環境模型搜索優化路徑的過程。根據對環境的掌握情況，航路規劃可分為全局規劃和局部規劃。全局規劃又稱離線規劃，是根據先驗知識（如地圖等），按一定的優化準則規劃出一條從起點到達目標點的無碰撞路徑。局部規劃又稱為動態避碰規劃，是以全局規劃的結果為指導，利用傳感器在線得到的局部環境信息，在盡可能短的時間內，避開出現的未知障礙物，從而產生可行路徑的過程。航路規劃算法借鑒了許多其他領域的方法，從本質上說與數學的許多分支密切相關，如傳統幾何、拓撲學、圖論、代數幾何和組合數學中的一些工具都被應用于航路規劃。目前對航路規劃問題的研究主要集中在機器人航路規劃方面。圖1.8記錄了航路規劃研究領域中先后出現的一些具有代表性的方法。

圖1.8　航路規劃研究發展概況
1）柵格法
柵格法是將機器人的規劃空間分解為相互連接且不重疊的空間柵格單元，每一個柵格單元都使用一個累積值表示此方格存在障礙物的可信度，累積值越高則表示存在障礙物的可能性越大。這些空間柵格會構成一個連通圖，依據各柵格累積值大小，使用優化算法即可在該連通圖上搜索一條從起始柵格到目標柵格無碰撞的最優路徑。在柵格法中，柵格的大小會直接影響環境信息存儲量的大小和規劃時間的長短。柵格劃分大了，環境信息存儲量小，規劃速度快，但分辨率下降，在密集環境下發現路徑的能力減弱；柵格劃分小了，環境分辨率高，在密集環境下發現路徑的能力強，但環境信息存儲量大，規劃時間長。
2）可視圖法
可視圖法是由麻省理工學院的Lozano-Perez和IBM研究院的Wesley于1979年提出的。該方法先將障礙物依據機器人的尺寸放大，而機器人理論上被縮成一點，然后將所有障礙物的頂點和機器人起始點及目標點用直線相連，要求機器人和障礙物各頂點之間、目標點和障礙物各頂點之間以及各障礙物頂點與頂點之間的連線都不能穿越障礙物，即直線可視。這樣搜索最短路徑問題就轉化為從起始點到目標點經過這些可視直線的最短距離問題。用Dijkistra法或A*搜索算法等對可行路徑圖進行搜索，就可以找到一條最短路徑。這類方法雖然實現簡單，且能夠求得最優路徑，但搜索時間長而且會出現組合爆炸問題。
3）拓撲法
拓撲法是根據環境信息和運動物體的幾何特點，將組成空間劃分成若干具有拓撲特征的一致的自由空間。根據彼此間的連通性建立拓撲網，從該網中搜索一條拓撲路徑，即完成了航路規劃的任務。該方法的優點在于，利用拓撲特征而大大縮小了搜索空間，其算法復雜性只與障礙物的數目相關，在理論上是完備的。