胡莘婷，吳宇

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

2. 重慶大學(xué) 航空航天學(xué)院，重慶 400044

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

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

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

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

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

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

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

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

1 多路徑規(guī)劃模型

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

1.1 城市環(huán)境模型和無人機飛行規(guī)則

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

圖1 無人機飛行規(guī)則示意圖

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

1.2 安全性分析模型

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

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

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

R=PNF

(1)

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

與無人機發(fā)生碰撞的人數(shù)N與墜落區(qū)域的人口密度正相關(guān)

N=AρH

(2)

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

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

(3)

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

表1 遮蔽指數(shù)

(4)

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

1.3 適應(yīng)度函數(shù)

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

為突出不同區(qū)域的風(fēng)險差異，引入比例因子ω調(diào)整式(1)數(shù)量級，將一個區(qū)域內(nèi)的風(fēng)險表示為

C=ωR

(5)

按照1.1節(jié)所述的城市環(huán)境模型，可對城市空域內(nèi)各正方體區(qū)域的風(fēng)險進行量化，表示為

(6)

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

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

(7)

進而本文從安全風(fēng)險角度建立適應(yīng)度函數(shù)為

(8)

式中：CL為無人機飛行路徑L的總風(fēng)險，其值為無人機途徑各區(qū)域風(fēng)險值的加和，總風(fēng)險值越低的路徑越優(yōu)。

1.4 約束條件

根據(jù)1.1節(jié)描述的城市環(huán)境模型和無人機飛行規(guī)則，制定如下約束條件。

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

無人機飛行經(jīng)過的每個航路點都必須位于指定的空域范圍內(nèi)，即

(9)

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

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

(10)

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

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

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

(11)

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

任一條完整路徑所經(jīng)過的各航路點均不重復(fù)。航路點重復(fù)表明無人機飛行過程出現(xiàn)折返現(xiàn)象，所生成的路徑必不是最優(yōu)路線。

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

(12)

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

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

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

Nmax≤Npermit

(13)

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

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

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

(14)

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

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

2 多路徑規(guī)劃算法設(shè)計

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

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

2.1 改進的蟻群算法

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

1) 航路點的選擇策略

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

(15)

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

(16)

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

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

2) 算法參數(shù)自適應(yīng)策略

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

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

(17)

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

3) 信息素濃度更新策略

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

(18)

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

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

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

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

(19)

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

2.2 聚類算法設(shè)計

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

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

圖4 聚類算法流程圖

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

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

2.3 改進聚類蟻群算法

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

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

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

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

3 仿真實驗與結(jié)果分析

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

3.1 風(fēng)險模型合理性驗證

設(shè)置實驗空域在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之間的隨機數(shù)。根據(jù)常見的無人機機型大疆精靈4和文獻[10,15,18,21]，風(fēng)險模型相關(guān)參數(shù)的取值如表2所示，實驗中用到的算法參數(shù)如表3所示，根據(jù)式(5)和表2參數(shù)生成的風(fēng)險圖如圖6所示。

表2 風(fēng)險模型參數(shù)

表3 蟻群算法參數(shù)表

圖6 各飛行高度層對應(yīng)的風(fēng)險圖

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

圖7 IACO算法中兩種指標下的風(fēng)險對比

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

3.2 不同路徑規(guī)劃算法的對比

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

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

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

圖8 3種算法的收斂曲線

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

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

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

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

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

圖10 CIACO算法求解出的路徑

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

表4 3種算法解的質(zhì)量對比

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

4 結(jié) 論

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