胡莘婷，吳宇

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.2 安全性分析模型

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

圖2 無人機(jī)對地面人群的安全威脅

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

R=PNF

(1)

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

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

N=AρH

(2)

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

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

(3)

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

表1 遮蔽指數(shù)

(4)

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

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

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

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

C=ωR

(5)

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

(6)

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

無人機(jī)飛行路徑的信息可表示為

(7)

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

(8)

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

1.4 約束條件

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

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

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

(9)

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

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

(10)

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

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

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

(11)

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

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

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

(12)

式中：n1、n2為同一條路徑中的兩個航路點(diǎn)。

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

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

Nmax≤Npermit

(13)

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

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

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

(14)

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

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

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

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

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

2.1 改進(jìn)的蟻群算法

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

1) 航路點(diǎn)的選擇策略

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

(15)

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

(16)

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

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

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

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

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

(17)

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

3) 信息素濃度更新策略

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

(18)

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

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

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

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

(19)

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

2.2 聚類算法設(shè)計(jì)

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

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

圖4 聚類算法流程圖

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

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

2.3 改進(jìn)聚類蟻群算法

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

圖5 改進(jìn)聚類蟻群算法流程圖

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

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

3 仿真實(shí)驗(yàn)與結(jié)果分析

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

3.1 風(fēng)險(xiǎn)模型合理性驗(yàn)證

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

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

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

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

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

圖7 IACO算法中兩種指標(biāo)下的風(fēng)險(xiǎn)對比

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

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

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

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

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

圖8 3種算法的收斂曲線

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

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

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

如圖9所示，ACO和IACO算法只能收斂得到一條路徑，無法達(dá)到同時(shí)規(guī)劃多條路徑的要求。若想通過運(yùn)行多次的方式獲得多條路徑，勢必會占用過多的計(jì)算機(jī)運(yùn)算資源，降低路徑規(guī)劃效率。與之相比，由圖10可見，CIACO算法運(yùn)行一次即能夠產(chǎn)生多條路徑。這是因?yàn)锳CO和IACO算法沒有聚類機(jī)制，在經(jīng)過多次迭代后會收斂到一條路徑；而CIACO算法在迭代開始之前，就通過聚類機(jī)制將初始解分類，隨著迭代過程的進(jìn)行，解能朝著不同的方向進(jìn)化，最終達(dá)到同時(shí)輸出多條路徑的目的。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算法不僅能同時(shí)生成多條路徑，而且解的質(zhì)量更優(yōu)。

4 結(jié) 論

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