面向城市飛行安全的無人機離散型多路徑規劃方法

胡莘婷，吳宇

1. 中國民航大學 空中交通管理學院，天津 300300

2. 重慶大學 航空航天學院，重慶 400044

由于無人機的運行對基礎設施要求低、靈活性高，且具有能夠精準完成“點”對“點”作業任務的優點，在城市中被廣泛用于物流貨運、航拍攝影、管線巡查、疫情防護等方面[1-3]，有效緩解了地面交通壓力和提高了任務完成率，對公眾生活產生了廣泛影響[4]。在以上應用中，都需要為無人機規劃一條從起點到終點的路徑，保證無人機順利完成任務。

為提高無人機的自主飛行能力，相關學者對于無人機在城市環境中運行的路徑規劃方法已進行部分研究。城市環境中障礙物數量眾多且分布不均，無人機在運行過程中需要規避障礙物[5]，文獻[6-8]將障礙物視為影響無人機運行的危險源，為避免無人機與障礙物相撞，研究了城市障礙物對無人機飛行路徑的影響。除了以不可穿越的障礙物為研究對象以外，部分學者考慮到無人機在可穿越區域的運行風險，提出了基于風險規避的路徑規劃方法[9-11]。文獻[9]研究了基于風險規避的離線和在線兩種路徑規劃策略；文獻[10]研究了無人機在城市環境中運行的風險因素；文獻[11] 提出一種基于風險圖的無人機四維航跡規劃方法。

在城市環境無人機路徑規劃的算法方面，文獻[6]提出了一種城市環境中小型無人機多障礙快速規劃算法，對固定翼無人機運動學方程進行了合理簡化，用螺旋線與直線組合構建近似最優航跡；文獻[7]通過將航路規劃分為全局規劃和局部規劃兩個階段, 使用A*算法進行全局路徑規劃引導無人機全局飛行, 使用廣度優先算法和局部回溯思想綜合進行局部航路規劃。文獻[8]針對城市空間的密集不規則障礙環境對無人機飛行安全的挑戰，研究了面向城市環境的快速擴展隨機樹算法。然而，由于城市環境的復雜性，無人機飛行前很難獲取全部的環境信息，并且考慮多架無人機同時在空中飛行時，可能會有沖突發生，使得規劃出的一條路徑不可用，導致該無人機的飛行任務被取消。在飛行計劃階段規劃出多條備選路徑，飛行時根據空中交通情況從多條備選路徑中選擇一條合適的路徑，減少無人機飛行任務被取消的概率，是在保證安全的前提下增加空域容量的有效解決方案[12]。針對復雜環境下的多路徑規劃問題，文獻[13-14]分別提出了基于加權K-均值聚類的粒子群算法和基于分級規劃策略的A*算法。

城市環境中無人機的路徑規劃問題既要滿足避障要求，又要考慮到無人機運行時對人產生的安全風險。上述研究缺少對避障和風險管理的綜合考慮，且在安全性分析方面的研究不足。城市作為人們生產和生活的環境集合，人員密集。由于無人機運行時存在對地撞擊的可能性，會對地面人員造成安全威脅，因此需要對地面人員建立風險分析模型[4,15-16]，并將其運用于無人機路徑規劃問題的研究中。在路徑規劃算法方面，已有的研究大都在連續型空間內以距離最短為目標，尋找一條最優路徑，少有適合于離散型空間的多路徑規劃算法。因此，有必要提出一種面向城市飛行安全的無人機離散型多路徑規劃方法，使無人機在城市中運行既不與障礙物碰撞，又能減少對行人的安全風險，并且還能同時生成多條備選路徑以提高無人機的任務完成率。

針對以上問題，本文研究離散型城市環境下的無人機多路徑規劃問題，根據定義的城市環境模型、無人機飛行規則和安全性原則，建立安全性分析模型和離散型多路徑規劃問題的數學模型；并對基本蟻群算法進行改進，提出改進聚類蟻群算法。本文的貢獻主要有以下3點：

1) 本文考慮無人機在城市上空運行時對地面人員造成的安全威脅，綜合人群密度、環境遮蔽等因素建立安全性分析模型。

2) 基于城市環境與無人機飛行規則，建立離散城市環境下無人機多路徑規劃數學模型，包括無人機飛行范圍、障礙物規避準則、航路間差異的定義等。

3) 針對基本蟻群算法收斂速度慢、易陷入局部最優的缺點，對基本蟻群算法進行改進，設計聚類算子，提出改進聚類蟻群算法，使其能夠同時產生多條安全性較高的路徑。

1 多路徑規劃模型

本文對無人機離散型多路徑規劃模型的3個關鍵要素——決策變量、適應度函數和約束條件做如下研究。本問題中，根據定義的城市環境模型，決策變量為無人機飛行途經的航路點；與安全性原則相對應的，適應度函數為與安全風險相關的表達式；設計無人機飛行規則，并據此制定相應的約束條件。

1.1 城市環境模型和無人機飛行規則

本文將城市空域環境網格化為尺寸相同的正方體，構建無人機城市飛行環境三維模型。無人機朝著正方體的各個頂點飛行，飛行航段由正方體的邊、面對角線或體對角線組成，如圖1所示。

圖1 無人機飛行規則示意圖

與無人機當前位置相鄰的航路點有26個，無人機每次位移均為沿著由相鄰航路點連接的航段直線飛行。因無人機在城市飛行過程中需規避障礙物，故每次位移的可選航路點可能小于26個。

1.2 安全性分析模型

目前無人機飛行安全性分析的主流研究方法是以事故致死率作為衡量指標[17-19]：文獻[17]搜集整理了國際上常用的無人機對地撞擊風險評判標準，指出以無人機墜機導致的地面人員致死率作為其運行風險的衡量指標。在此基礎上，相關研究者對無人機墜落致死情形展開了研究，文獻[18]通過實驗研究了無人機墜落時的重量和高度與事故致死率之間的關系；文獻[19]考慮了環境遮蔽對無人機墜機事故的影響程度，建立了行人受撞擊致死概率的數學表達式。本文基于以上考慮建立以事故致死情形為評判標準的安全性分析模型。設無人機在人群上空高度為h處飛行，如圖2所示。

圖2 無人機對地面人群的安全威脅

本文將無人機危害地面人員生命安全的事故發生過程分為3個階段：① 無人機在人群上空運行時發生墜機，② 墜機砸中地面人員，③ 人員因受到強烈撞擊而身亡。與上述3階段對應的數學模型表達式為

R=PNF

(1)

式中：P為無人機每飛行1 h發生墜機的事故率；N為與無人機發生碰撞的人數，數值大小取決于墜落區域的人口密度，人群越密集，無人機對地撞擊時砸中人的概率越大，風險越高；F為地面人員受撞擊時的致死率，致死率大小與碰撞動能有關?；诖?，地面人群上方空域無人機飛行安全性分析模型的建立過程如下。

與無人機發生碰撞的人數N與墜落區域的人口密度正相關

N=AρH

(2)

式中：A為無人機對地撞擊時的面積分量；ρH為無人機墜落區域的人口密度。

無人機的質量越大、飛行高度越高，根據動能定理，對地撞擊時的動能越大，造成地面人員死亡的可能性越高，風險越高，反之亦然。同時考慮到城市環境中存在的建筑物和樹木等，它們在無人機墜機時會對地面人員產生遮蔽和緩沖的作用。因此綜合考慮無人機撞擊動能和環境遮蔽的影響，Dalamagkidis等[19]建立了撞擊致死概率F的定量表達式

(3)

式中：S為遮蔽指數，對應于地面人群的暴露程度，借鑒Primatesta等[10]的研究，遮蔽指數取值如表1所示；λ為S=0.5時致死率達50%所需的撞擊能量；μ為當S趨于0時致死所需的撞擊能量閾值。E為碰撞動能，結合文獻[19]的研究，通過式(4)可求得。

表1 遮蔽指數

(4)

式中：m為無人機的質量；g為重力加速度；q為阻力系數；ρA為空氣密度。式(3)和式(4)表明無人機事故致死率與無人機的飛行高度呈正相關關系。

1.3 適應度函數

城市環境對無人機運行而言可分為如下兩類：① 障礙物占據的空間為不可穿越區域，無人機須與之保持一定的安全距離，通過繞行的方式規避碰撞風險；② 無障礙物占用的空間為無人機可穿越區域，但無人機在可穿越區域飛行時需考慮其對地面人員造成的安全威脅。為使無人機在不與障礙物發生碰撞的前提下，盡可能降低運行時產生的安全風險，適應度函數定義為與風險有關的表達式。

為突出不同區域的風險差異，引入比例因子ω調整式(1)數量級，將一個區域內的風險表示為

C=ωR

(5)

按照1.1節所述的城市環境模型，可對城市空域內各正方體區域的風險進行量化，表示為

(6)

式中：(m,n,l)為圖1所示的城市環境模型中各正方體的位置編號。

無人機飛行路徑的信息可表示為

(7)

進而本文從安全風險角度建立適應度函數為

(8)

式中：CL為無人機飛行路徑L的總風險，其值為無人機途徑各區域風險值的加和，總風險值越低的路徑越優。

1.4 約束條件

根據1.1節描述的城市環境模型和無人機飛行規則，制定如下約束條件。

1) 無人機飛行范圍的約束

無人機飛行經過的每個航路點都必須位于指定的空域范圍內，即

(9)

式中：xmin、xmax、ymin、ymax、zmin、zmax分別為城市空域的邊界范圍；a為正方體的邊長；xi、yj、zk為無人機可選的航路點坐標集。

為提高模型的計算速度、縮小航路點的搜索范圍，可將式(9)轉化為

(10)

式中：XU=min {xmax,(xNmax+ab)}和XL=max {xmin,(x1-ab)}分別為無人機可飛空域在x軸方向的上/下界，x1和xNmax分別為無人機飛行任務在x軸方向的起/終點坐標，同理可得y軸和z軸方向的參數符號；b為擴張系數，使無人機可飛空域由原起/終點為界所圍的立方體沿各軸方向各擴大2ab的長度。

2) 無人機避免與障礙物相撞的約束

無人機途經各航路點與障礙物邊緣的距離應不小于正方體邊長a，避免與障礙物碰撞。

(11)

3) 無人機飛行路徑不折返的約束

任一條完整路徑所經過的各航路點均不重復。航路點重復表明無人機飛行過程出現折返現象，所生成的路徑必不是最優路線。

(xn1,yn1,zn1)≠(xn2,yn2,zn2)

(12)

式中：n1、n2為同一條路徑中的兩個航路點。

4) 無人機飛行路徑長度的約束

受無人機續航能力的限制，為避免出現路徑長度過長的情況，需要對無人機的路徑長度做出約束。該約束條件可表示為對途經航路點數量的限制。任意一條完整路徑所經過的航路點總數應不超過限制的最大數量

Nmax≤Npermit

(13)

式中：Nmax為一條路徑中的航路點總數；Npermit為一條路徑限制的最大航路點數量。

5) 無人機多條備選路徑差異程度的約束

無人機從起點飛至終點有多條路徑可以實現，對于多路徑規劃問題，需要明確不同路徑間的差異。任意兩條不同路徑的差異程度表示為其各航段風險差值的總和

(14)

圖3 不同路徑的差異示意圖

規定無人機多條備選路徑間的差異程度需大于閾值DT，當DLm,Ln>DT時，視為兩條路徑具有明顯差異。

2 多路徑規劃算法設計

首先對求解路徑規劃問題的算法進行選擇。由于本文目標是同時獲得多條路徑，算法需要從多個初始解開始迭代，將聚類算法與群智能優化算法結合能夠很好地實現上述要求。目前群智能優化算法多用于求解連續型優化問題，如差分進化算法、粒子群算法、人工蜂群算法等；但仍有少數的群智能優化算法適用于求解離散型優化問題，如遺傳算法和蟻群算法。其中，遺傳算法對決策變量的數量有一定要求，不易編碼實現；因本文求解的各路徑航路點數量不一，采用對航路點數量無要求的蟻群算法更為合適。

本節針對基本蟻群算法收斂速度慢、易陷入局部最優的缺陷，對蟻群算法進行改進。為了能夠同時生成多條路徑，設計聚類算子，與改進的蟻群算法結合，提出一種改進聚類蟻群算法。

2.1 改進的蟻群算法

為了提高標準蟻群算法(Ant Colony Optimization algorithm, ACO)的收斂速度和路徑尋優能力，本文將對蟻群算法進行如下改進，提出改進的蟻群算法(Improved Ant Colony Optimization algorithm, IACO)。

1) 航路點的選擇策略

從當前航路點轉移到下一航路點時，蟻群算法在所有符合約束條件的備選航路點中，某個航路點被選中的概率由式(15)決定。

(15)

式中：pn(t)為航路點n在第t代被選中的概率；τn(t)為航路點n在第t代的信息素濃度；ηn為航路點n的啟發項，標準蟻群算法的啟發值為從該點到終點的距離的倒數；link為所有符合約束條件的備選航路點的集合；tmax為最大迭代次數；α和β分別為信息素因子和啟發項因子，表示信息素濃度和啟發值對航路點選擇的重要程度。式(15) 表明備選航路點與終點的距離越短，該備選點被選中的概率越大。標準蟻群算法以尋求最短路徑為導向，但從安全風險角度考慮，應使所求得路徑的總風險較低。因此，與本文研究問題相對應的，將啟發項改為

(16)

式中：Cn,x、Cn,y、Cn,z分別為從備選航路點到終點的x、y、z3個方向的風險預估值。上述設計的原理為從備選點中為無人機選擇一個從當前位置到終點的安全性較高的位移方向，以使無人機沿著風險較低的路徑飛行，提高無人機在城市環境中運行的安全性。

基于概率的航路點選擇方法雖在一定程度上能避免路徑搜索陷入局部最優，但同時也降低了算法的收斂速度。為解決此問題，本文通過隨機輪盤賭的方式選擇下一個航路點。引入隨機數rand，規定當rand大于設置的閾值時，航路點的選擇由式(15)確定，否則直接將被選擇概率最高的備選航路點作為下一個航路點。本文在算法迭代的初期，設置較小的閾值，在迭代的后期設置較大的閾值。隨機輪盤賭法是基于標準輪盤賭算法與貪婪算法的一種改良方法，該方法相較于標準輪盤賭法具有更快的收斂速度，同時又能克服貪婪算法易陷入局部最優的缺陷。

2) 算法參數自適應策略

一個好的優化算法應當在迭代初期具備較強的全局搜索能力，而在迭代的后期應有良好的局部搜索能力。標準蟻群算法中的信息素強度Q在迭代過程中保持不變，但設置為常數的Q并不能滿足上述要求：較小的Q值會增加算法的全局搜索能力，但會降低收斂速度，而較大的Q則會因增加重復搜索到先前已經出現過的解的概率而陷入局部最優。因此，在算法迭代的初期設置Q為較小的值以避免算法陷入局部最優，并讓Q值隨著迭代次數的增加而增大，以增強算法的局部搜索能力，即

Q(t)=Q0+ln(t)c

(17)

式中：Q0為信息素強度初始值；c為信息素強度增長系數。

3) 信息素濃度更新策略

在當代路徑生成完畢之后，標準的蟻群算法會對各路徑所含航路點的信息素濃度進行更新，如式(18)所示。下一代的螞蟻依據上一代螞蟻留下的信息素進行路徑點的選擇。

(18)

式中：ρ為信息素濃度蒸發系數；Γa為螞蟻a在第t代走過的航路點的集合；Δτa為信息素濃度增加值；CL(a)為螞蟻a所走路徑的總風險；s為種群規模。

為增強優質解的影響，本文對上述信息素濃度更新機制進行改進，在迭代初期，僅對當代最優航路所包含的航路點的信息素濃度進行更新；并且，為利于算法收斂，在迭代的后期僅更新歷史最優航路所含航路點的信息素濃度。

此外，為防止因某個航路點的信息素大量堆積而導致算法陷入局部最優，本文將信息素濃度限制在一定范圍內

τn(t)=max{τmin,min{τn(t),τmax}}

(19)

式中：τmax、τmin分別為信息素濃度的上、下限。

2.2 聚類算法設計

為了同時求解出多條路徑，需要先通過聚類機制將具有明顯差異的路徑歸為不同類別，在每個類別中，可行解隨著蟻群算法的迭代過程朝著不同的進化方向不斷更新和優化，最終獲得具有一定差異的多條路徑。

聚類的關鍵是確定聚類中心，合理的聚類中心能夠加快算法的收斂速度，且能避免陷入局部最優。本文將初始路徑按照風險值進行排序，選取風險值較低且差異明顯的幾條初始路徑作為聚類中心，其他路徑依據其與聚類中心的差異程度歸類。聚類算法的流程如圖4所示。

圖4 聚類算法流程圖

首先初始化s條路徑，作為初始解。各初始解的適應度函數值由式(8)計算得出，并將其按照由小到大的方式排序。排序為第1的解作為第1類的聚類中心，排序為第2的解根據式(14)計算其與聚類中心的差異值，若差異值小于DT，則認為二者差異不大，將其歸為第1類。排序在其后的解也按照同樣的方法依次與排序第一的解進行比較，以判斷是否歸為第1類，直到初始解全部檢測完畢。在所有未被歸為第1類的解中，適應度函數值最低的解作為第2類的聚類中心。重復上述檢測過程，直到所有解都歸類完畢。

上述具有排擠機制的聚類過程具有如下特點：① 初始路徑中適應度函數值較小且差異明顯的幾條路徑作為聚類中心，使得每類中至少存在一條適應度函數值較小的路徑，便于算法在后續迭代過程中獲得較優的解，且利于算法收斂；② 類 別的數量不能提前確定，與初始路徑的適應度函數值有關。與固定類別數量的聚類方法相比，自適應類別數量的聚類算法使得各聚類中心之間均有較大差異，為迭代過程奠定了不同的進化方向，能夠保證算法最終輸出的多條路徑間的差異性。

2.3 改進聚類蟻群算法

常規的蟻群算法基于給定的適應度函數，通過種群迭代過程輸出一個最優解。為能夠同時生成多條備選路徑，使無人機在復雜城市環境中能夠順利完成作業任務，本文將設計的聚類算子與改進的蟻群算法相結合，提出求解離散型多路徑規劃問題的改進聚類蟻群(Clustering Improved Ant Colony Optimization, CIACO)算法。算法流程如圖5所示。

圖5 改進聚類蟻群算法流程圖

與標準蟻群算法不同，改進聚類蟻群算法在迭代前增加了初始化過程。初始化s條路徑，計算各初始解的適應度函數值，將其按優劣次序排列。通過2.2節所述的具有排擠機制的聚類算法確定k個聚類中心，聚類中心為后續蟻群迭代過程指出大致的進化方向。聚類過程結束后按照類別更新各自的信息素濃度矩陣，迭代過程正式開始。與標準蟻群算法每次僅依據一個信息素濃度矩陣進行更新和進化不同的是，改進聚類蟻群算法有k個不同的信息素濃度矩陣。不同的信息素濃度矩陣在每次迭代過程中能夠同時發揮作用，使得原本只能生成一條路徑的蟻群算法最終能夠同時輸出多條路徑。

結合2.1節改進的蟻群算法的第1)點航路點選擇策略，按照類別分別為每只螞蟻尋找一條可行路徑，并計算其適應度函數值，尋路完畢之后依據第3)點信息素濃度更新策略更新各類別的信息素濃度矩陣。迭代過程中根據第2)點算法參數自適應策略動態更新信息素強度值。迭代過程結束后，每一類的最優路徑，即該類適應度函數值最小的解，作為該類的最終結果輸出。

3 仿真實驗與結果分析

為驗證本文提出的模型與算法在求解離散型城市環境下基于無人機飛行安全的多路徑規劃問題的合理性和有效性，分別進行如下仿真實驗。首先搭建仿真環境，量化實驗區域的風險值，在3.1節用本文以低風險為優化目標的方法與追求距離最短的方法對比，對本文所建風險模型的安全性和有效性進行分析；3.2節對比算法改進前后的性能，對算法改進的合理性進行分析。

3.1 風險模型合理性驗證

設置實驗空域在x、y、z方向上的范圍分別為[0,1 800] m, [0,1 800] m和[0,90] m，正方體邊長為30 m[20]，隨機生成300個障礙物，人群密度為范圍在[15×10-3,35×10-3]人/m2之間的隨機數。根據常見的無人機機型大疆精靈4和文獻[10,15,18,21]，風險模型相關參數的取值如表2所示，實驗中用到的算法參數如表3所示，根據式(5)和表2參數生成的風險圖如圖6所示。

表2 風險模型參數

表3 蟻群算法參數表

圖6 各飛行高度層對應的風險圖

在同樣的城市環境模型和無人機飛行規則下，追求距離最短的方法與本文根據安全性原則設計的方法類似，二者模型的差別只在于適應度函數的設置上，其他的內容如決策變量、約束條件均相同。若以飛行距離為衡量指標，適應度函數值即為其路徑的長度；路徑間的差異值計算方法為同樣將每條路徑等分為Nsegment段，然后對兩條路徑對應等分點之間的距離求和作為其路徑間的差異值。采用IACO算法對二者進行仿真實驗，結果如圖7所示。

圖7 IACO算法中兩種指標下的風險對比

由圖7可見，距離最短的路徑不一定是最安全的飛行路徑。以距離最短為尋優目標的路徑規劃方法，沒有考慮到無人機運行時的風險，所求解出的路徑風險值較高。根據本文所建的風險模型，以遵循安全性原則求解出的路徑在安全性方面的表現具有明顯優勢。

3.2 不同路徑規劃算法的對比

分別用標準蟻群算法(ACO)、改進的蟻群算法(IACO)和改進聚類蟻群算法(CIACO)求解同一離散型多路徑規劃問題。在ACO算法基礎上，按照第2.1節所述方法進行改進，得到IACO算法；IACO算法和CIACO算法的差別在于沒有采用聚類機制，兩種算法的其他內容均相同。根據仿真結果比較各算法在收斂速度、路徑多樣性和解的優質性上的差異。

空域搜索范圍的擴張系數b取值為2，各路徑限制的最大航路點數量Npermit=500，每條路徑被等分為10段，即Nsegment=10，差異閾值DT=25。

設置起點(120,90,60) m，終點(1 590,1 620,90) m，Q0取為從起點到終點x、y、z3個方向風險預估值的總和，ACO算法中的信息素強度保持初值不變。信息素矩陣中所有元素初值設為1。ACO、IACO和CIACO 3種算法的對比結果如圖8所示。

圖8 3種算法的收斂曲線

從圖8可以看出，ACO算法收斂速度緩慢，在經過614次迭代后才收斂，收斂時適應度函數值為602，遠高于其他兩種算法；IACO算法和CIACO算法收斂較快，分別在第57代和第47代達到收斂狀態，且適應度函數值也較低，分別為507和482。

算法改進后收斂速度提升的原因是，本文在航路點的選擇上以一定概率引導螞蟻選擇安全性較高的位移方向，避免因螞蟻隨機行走造成算法收斂緩慢；僅更新最優路徑的信息素，避免下一代螞蟻在根據以往螞蟻留下的信息素進行路徑搜索時受到歷代質量不高的路徑信息的影響；同時，所設計的自適應參數調整策略也能夠對算法收斂起到促進作用。并且，因算法改進措施中對信息素濃度做了限幅操作，避免出現因某些航路點信息素大量堆積使算法重復搜索到已出現過的解，該策略提高了算法搜索到優質解的可能性。在采用本文第2.1節所述的策略對ACO算法進行改進之后，IACO和CIACO算法不論是在收斂速度還是在解的優質性上都相較ACO算法顯示出了明顯優勢，證明了本文所提算法改進策略的有效性。此外，CIACO算法和IACO算法相比，之所以在迭代初期適應度函數值下降較慢、但在迭代后期產生質量更優的解，是因為聚類機制的使用使CIACO算法擁有多個進化方向，在迭代過程中解的搜索范圍更大，導致適應度函數值下降較慢。但好處是使得改進后的CIACO算法更不易陷入局部最優，增加了算法搜索到優質解的可能性。

由ACO、IACO算法收斂生成的一條路徑和由CIACO算法產生的多條路徑分別如圖9和圖10所示。

如圖9所示，ACO和IACO算法只能收斂得到一條路徑，無法達到同時規劃多條路徑的要求。若想通過運行多次的方式獲得多條路徑，勢必會占用過多的計算機運算資源，降低路徑規劃效率。與之相比，由圖10可見，CIACO算法運行一次即能夠產生多條路徑。這是因為ACO和IACO算法沒有聚類機制，在經過多次迭代后會收斂到一條路徑；而CIACO算法在迭代開始之前，就通過聚類機制將初始解分類，隨著迭代過程的進行，解能朝著不同的方向進化，最終達到同時輸出多條路徑的目的。CIACO算法各類別的收斂曲線如圖11所示，3種算法的解的質量對比如表4所示。

圖9 ACO和IACO算法求解出的路徑

圖10 CIACO算法求解出的路徑

圖11 CIACO算法各類別的收斂曲線

表4 3種算法解的質量對比

該算例中CIACO算法產生了4個聚類中心，最終輸出了4條不同的路徑。4條路徑的適應度函數值最低為482、最高為501，均小于ACO與IACO算法生成路徑的適應度函數值602和507。仿真結果證明了本文提出的CIACO算法不僅能同時生成多條路徑，而且解的質量更優。

4 結 論

本文針對無人機在城市環境中的飛行安全和同時規劃多條備選路徑的需求，研究了面向城市飛行安全的無人機多路徑規劃問題。通過描述無人機運行風險的發生過程，建立安全性分析模型。根據定義的城市環境模型、無人機飛行規則和安全性原則，建立了離散城市環境下的無人機多路徑規劃數學模型。針對基本蟻群算法收斂速度慢、易陷入局部最優的缺陷，對蟻群算法進行了改進。設計聚類算子，與改進的蟻群算法結合，提出了改進聚類蟻群算法。通過仿真實驗對比驗證了本文所提方法不僅能夠同時生成多條路徑，為無人機飛行提供備選方案，而且所設計的改進聚類蟻群算法還具有收斂快、安全性高的優勢。