宋阿妮,包賢哲

(湖北工業(yè)大學(xué)電氣與電子工程學(xué)院，湖北 武漢 430068)

1 引言

隨著科學(xué)技術(shù)的發(fā)展，無(wú)人機(jī)技術(shù)日趨成熟并開(kāi)始運(yùn)用于救援、運(yùn)輸、監(jiān)測(cè)、農(nóng)業(yè)和軍事等各個(gè)領(lǐng)域，無(wú)人機(jī)在執(zhí)行任務(wù)過(guò)程中面臨的最主要問(wèn)題是如何在復(fù)雜環(huán)境中避開(kāi)障礙物尋找最短路徑安全到達(dá)目的地。在空間中無(wú)人機(jī)需要考慮障礙物大小和形狀進(jìn)行高度和姿態(tài)的調(diào)整，地形復(fù)雜的山區(qū)或城區(qū)對(duì)無(wú)人機(jī)識(shí)別、判斷路徑的性能要求更高。如何解決此問(wèn)題已經(jīng)成為了該領(lǐng)域研究的熱點(diǎn)，提高無(wú)人機(jī)復(fù)雜環(huán)境下的尋徑性能將提高各領(lǐng)域無(wú)人機(jī)工作效率，具有較高的研究?jī)r(jià)值。

國(guó)內(nèi)外學(xué)者對(duì)此做過(guò)許多研究，如闞平等[1]將補(bǔ)給總次數(shù)、返航補(bǔ)給總時(shí)間、總耗時(shí)和最小補(bǔ)給時(shí)間間隔用權(quán)重系數(shù)化為單目標(biāo)函數(shù)，根據(jù)作業(yè)區(qū)域面積結(jié)合柵格法提出了一種改進(jìn)的粒子群算法。該算法以最大迭代次數(shù)的一半為分界線給予進(jìn)化公式不同的慣性權(quán)重加快算法收斂，對(duì)無(wú)人機(jī)返航順序和返航位置進(jìn)行尋優(yōu)。最后將其運(yùn)用于多植物保護(hù)無(wú)人機(jī)協(xié)同系統(tǒng)中，較好地綜合了最大作業(yè)距離規(guī)劃和最小返航距離規(guī)劃的優(yōu)點(diǎn)。黃小毛等[2]對(duì)田塊形狀進(jìn)行分類并結(jié)合貪婪算法解決了復(fù)雜形狀農(nóng)田環(huán)境下無(wú)人機(jī)作業(yè)問(wèn)題。Li等[3]首先通過(guò)無(wú)人機(jī)的位置和耐久性劃分搜索區(qū)域，再利用并行搜索策略找到最優(yōu)路徑。Duchoň等[4]發(fā)現(xiàn)傳統(tǒng)A*算法無(wú)法高效利用長(zhǎng)距離單元格的有用空間，并且在搜索過(guò)程中有些單元格無(wú)法用鋸齒形線連接的問(wèn)題，為此改進(jìn)算法讓其進(jìn)行多角度搜索，根據(jù)跳轉(zhuǎn)點(diǎn)搜索JPS(Jump Point Search)方法在實(shí)際評(píng)估的細(xì)胞周圍種植鄰近細(xì)胞,以強(qiáng)化算法搜索性能,提出了JPS(A*)算法，并將其運(yùn)用于復(fù)雜標(biāo)準(zhǔn)網(wǎng)格環(huán)境中進(jìn)行實(shí)驗(yàn)。結(jié)果表明，就快速尋找路徑而言，該算法比Basic Theta*性能更好，但該算法在搜尋的路徑長(zhǎng)度方面表現(xiàn)較差，搜索得到的路徑長(zhǎng)度更長(zhǎng)，不利于機(jī)器人快速完成任務(wù)。

嚴(yán)煒等[5]以無(wú)人機(jī)總飛行距離和多余覆蓋率為目標(biāo)函數(shù)，采用差分進(jìn)化算法和量子退火算法相結(jié)合的方式求解無(wú)人機(jī)最優(yōu)路徑，最后的仿真結(jié)果表明算法能夠有效減小無(wú)人機(jī)的飛行距離。王飛等[6]針對(duì)三維移動(dòng)機(jī)器人路徑規(guī)劃問(wèn)題，重新設(shè)定了蟻群算法中的啟發(fā)函數(shù)，彌補(bǔ)了傳統(tǒng)蟻群算法啟發(fā)函數(shù)未能考慮下一個(gè)節(jié)點(diǎn)到目標(biāo)點(diǎn)距離的缺陷；并采用非均勻的初始化信息素濃度保證算法前期不會(huì)盲目搜索，采用自適應(yīng)信息揮發(fā)因子平衡搜索能力；最終通過(guò)實(shí)驗(yàn)表明其改進(jìn)效果較好，但螞蟻個(gè)體之間的關(guān)聯(lián)性不強(qiáng)，收斂速度較慢，不適應(yīng)于高速多無(wú)人機(jī)系統(tǒng)。劉可等[7]通過(guò)設(shè)置各類參數(shù)并重新設(shè)計(jì)啟發(fā)函數(shù)建立二維的任務(wù)源和參數(shù)矩陣，設(shè)定機(jī)器人只能朝5個(gè)方向前進(jìn)，將設(shè)置的參數(shù)映射到三維空間中，根據(jù)映射擴(kuò)展后的三維遷移圖，結(jié)合譜圖理論中參數(shù)遷移圖和拉普拉斯矩陣之間的對(duì)應(yīng)關(guān)系得到最優(yōu)參數(shù)簇，從而獲得機(jī)器人在三維空間的路線。該方法可以大幅度減少機(jī)器人得到最優(yōu)路徑的計(jì)算時(shí)間，但是該方法只適合于特定的環(huán)境且對(duì)于機(jī)器人屬性有一定限制。徐興等[8]則通過(guò)將原有2點(diǎn)間直線路徑更改為平行于各個(gè)坐標(biāo)軸的折線路徑，以滿足立體倉(cāng)庫(kù)中平面移動(dòng)和垂直移動(dòng)的要求，并通過(guò)cumsum 函數(shù)對(duì)每段路徑元素累加求和改進(jìn)蟻群算法的概率公式,防止算法陷入局部最優(yōu)。最終將該算法運(yùn)用于立體倉(cāng)庫(kù)的實(shí)際問(wèn)題中，與其他算法的對(duì)比表明了改進(jìn)的有效性，但算法個(gè)體之間聯(lián)系較少且信息素初始化濃度相同，會(huì)導(dǎo)致算法收斂緩慢。張洪海等[9]將無(wú)人機(jī)編隊(duì)分為路徑規(guī)劃和速度規(guī)劃2個(gè)階段，在路徑規(guī)劃階段，采用Dubins曲線在6種不同路線形式下尋找滿足曲率約束條件的連接，規(guī)定切線方向的2點(diǎn)之間的最短路徑作為最優(yōu)解；在速度規(guī)劃階段，通過(guò)空間柵格化將路徑區(qū)分為“安全區(qū)間”“非安全區(qū)間”和“隊(duì)形調(diào)整區(qū)間”，為不同區(qū)間設(shè)定差異化速度規(guī)劃規(guī)則，在降低速度規(guī)劃的復(fù)雜度的同時(shí)，用5次多項(xiàng)式曲線規(guī)劃無(wú)人機(jī)位移和時(shí)間的關(guān)系，得到連續(xù)平滑的速度曲線。將該方法運(yùn)用于多無(wú)人機(jī)系統(tǒng)中能夠有效平衡路徑長(zhǎng)度、轉(zhuǎn)向頻度和跟蹤誤差之間的關(guān)系，加快無(wú)人機(jī)的集結(jié)速度和反應(yīng)速度，增加了路徑的平滑程度。

王云常等[10]采用人工勢(shì)場(chǎng)法搜索全局路徑，用A*算法指導(dǎo)局部路徑尋優(yōu)避開(kāi)障礙物，最后通過(guò)仿真表明該算法能夠增強(qiáng)避障性能，縮短尋優(yōu)時(shí)間，但在搜索中存在抖動(dòng)性問(wèn)題。Sun等[11]發(fā)現(xiàn)經(jīng)典的APF(Artificial Potential Field)算法僅限于單個(gè)無(wú)人機(jī)UAV(Unmanned Aerial Vehicle)軌跡規(guī)劃，通常無(wú)法保證完全避免碰撞,為克服這一問(wèn)題，提出了一種具有距離因子和跳躍策略的方法來(lái)解決不可達(dá)目標(biāo)等較為復(fù)雜的問(wèn)題，確保無(wú)人機(jī)不會(huì)與任何障礙物發(fā)生碰撞。該方法將無(wú)人機(jī)同伴視為實(shí)現(xiàn)協(xié)同彈道規(guī)劃的動(dòng)態(tài)障礙，以避免無(wú)人機(jī)之間的相互干擾。此外，還使用動(dòng)態(tài)步進(jìn)調(diào)整方法解決了抖動(dòng)問(wèn)題。胡潔等[12]考慮無(wú)人機(jī)有限續(xù)航和障礙物問(wèn)題提出一種集中式逐次貪婪路徑規(guī)劃算法，迭代時(shí)每次選擇一個(gè)節(jié)點(diǎn)進(jìn)行匹配組合，能夠在最大化收益的同時(shí)滿足各種約束條件。Scott等[13]提出了2種無(wú)人機(jī)物流運(yùn)輸模型來(lái)提供醫(yī)療相關(guān)服務(wù)。Boualem等[14]對(duì)無(wú)人機(jī)的能耗和負(fù)載做出約束，建立了運(yùn)輸物品總成本最小的優(yōu)化模型。唐立等[15]針對(duì)山區(qū)應(yīng)急物資無(wú)人機(jī)運(yùn)輸問(wèn)題，提出一種考慮路徑安全度的改進(jìn)的蟻群算法，以避開(kāi)障礙物縮短運(yùn)輸路徑，仿真表明其算法收斂速度更快，但該算法并未考慮障礙物在三維空間內(nèi)的形狀及大小。Byung等[16]考慮到飛行時(shí)間、可裝載能力和貨物重量等對(duì)無(wú)人機(jī)飛行能力的影響，提出了混合整數(shù)線性規(guī)劃MILP(Mixed Integer Linear Programming)公式，用于推導(dǎo)無(wú)人機(jī)交付時(shí)間表。 為了解決計(jì)算問(wèn)題，開(kāi)發(fā)了后退平線任務(wù)分配RHTA(Receding Horizon Task Assignment)啟發(fā)式方法，且根據(jù)當(dāng)前裝載的產(chǎn)品量開(kāi)發(fā)了實(shí)時(shí)權(quán)重函數(shù)以平衡裝載產(chǎn)品量對(duì)無(wú)人機(jī)飛行時(shí)間的影響，提高了算法的實(shí)用性。通過(guò)數(shù)值示例對(duì)島嶼區(qū)域交付進(jìn)行了測(cè)試，表明該算法能夠在短時(shí)間內(nèi)為大型無(wú)人機(jī)系統(tǒng)提供路徑方案。

雖然許多優(yōu)化算法在無(wú)人機(jī)路徑規(guī)劃問(wèn)題上都有著不錯(cuò)的效果，但仍然存在著收斂速度過(guò)慢、精度不高和參數(shù)設(shè)置復(fù)雜等問(wèn)題。針對(duì)這些問(wèn)題本文提出一種精英擴(kuò)散蟻群優(yōu)化EDACO(Elite Diffusion Ant Colony Optimization)算法，該算法首先通過(guò)極值限定策略限制信息素濃度的范圍，防止算法陷入局部最優(yōu)；然后采用精英策略改進(jìn)信息素更新公式，加快算法收斂；再引入信息素?cái)U(kuò)散策略，加大距離較近螞蟻的交流合作，以加快算法收斂，防止算法過(guò)早停滯。最后用傳統(tǒng)蟻群優(yōu)化ACO(Ant Colony Optimization)算法、精英擴(kuò)散蟻群優(yōu)化EDACO算法、遺傳算法GA(Genetic Algorithm)和螢火蟲(chóng)算法FA(Firefly Algorithm) 在4個(gè)算例下進(jìn)行仿真實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果表明EDACO算法在三維空間無(wú)人機(jī)路徑規(guī)劃問(wèn)題上有著良好的適應(yīng)性。

2 模型建立與問(wèn)題分析

假設(shè)某一山區(qū)由于突發(fā)自然災(zāi)害導(dǎo)致山路受阻，無(wú)法通過(guò)陸路運(yùn)輸救援物資，此時(shí)派出無(wú)人機(jī)為山區(qū)居民運(yùn)送必要的生活用品。假設(shè)該地區(qū)是一個(gè)大小為a1×b1×c1km3的空間(第4節(jié)中a1=b1=c1=1)，將山峰等障礙物簡(jiǎn)化為不同高度的單峰函數(shù)如式(1)所示:

(1)

其中,Zi(x,y)表示第i個(gè)山峰上點(diǎn)(x,y)處的高度，即縱坐標(biāo)。k1,k2為2個(gè)可調(diào)整參數(shù)，用來(lái)改變山峰的形狀和大小。xi,yi表示山峰中心的橫坐標(biāo)和縱坐標(biāo),xpi,ypi則代表山峰i在x方向和y方向的坡度。

無(wú)人機(jī)在飛行過(guò)程中需要避開(kāi)所有山峰，即無(wú)人機(jī)在點(diǎn)(xm,ym)上的飛行高度要大于山峰在該點(diǎn)的高度，否則會(huì)導(dǎo)致無(wú)人機(jī)損傷或墜毀，如式(2)所示:

V(xm,ym)>Zi(xm,ym),xm∈Si，ym∈Si

(2)

其中,V(xm,ym)表示無(wú)人機(jī)所在的位置，Si表示第i個(gè)山峰投影在xy平面上的所有點(diǎn)的集合。

但在實(shí)際情況中，由于山峰坡度不同且無(wú)人機(jī)有一定體積，在無(wú)人機(jī)體心飛行高度恰好高過(guò)山峰高度時(shí)仍然會(huì)發(fā)生碰撞。設(shè)無(wú)人機(jī)的長(zhǎng)為a,寬為b，高為h(第4節(jié)中，a=0.5 m，b=0.6 m,h=0.5 m)，將無(wú)人機(jī)簡(jiǎn)化為一個(gè)長(zhǎng)方體，其平面示意圖如圖1所示。

Figure 1 Schematic diagram of the location of UAV and mountains圖1 無(wú)人機(jī)與山峰位置示意圖

根據(jù)圖1所示無(wú)人機(jī)飛行情況，如果按照式(1)的約束條件求解，即無(wú)人機(jī)在(xm,ym)的中心縱坐標(biāo)大于山峰的縱坐標(biāo)時(shí)，無(wú)人機(jī)會(huì)與山峰發(fā)生碰撞，如圖1中虛線所示。無(wú)人機(jī)與山峰碰撞不僅與其體積有關(guān)，也與山峰碰撞面的陡度有關(guān)，但由于山峰各個(gè)面的曲率不同且隨著高度的升高而發(fā)生變化，難以對(duì)所有山峰建立具體模型。為了能夠保證任何時(shí)刻無(wú)人機(jī)位置都不與山峰碰撞，將無(wú)人機(jī)放置于以其體對(duì)角線的一半作為半徑的球體中，如圖2所示。

Figure 2 Simplified model of UAV圖2 無(wú)人機(jī)簡(jiǎn)化模型圖

圖2中的長(zhǎng)方體即為無(wú)人機(jī)的簡(jiǎn)化示意圖，其中球體的半徑如式(3)所示:

(3)

以無(wú)人機(jī)中心坐標(biāo)當(dāng)前位置為原點(diǎn)，建立極坐標(biāo)系，引入球體的極坐標(biāo)公式，如式(4)所示:

(4)

其中,R(x,y,z)表示球體R上的任意一點(diǎn)，φ是通過(guò)z軸和空間任意點(diǎn)的平面與坐標(biāo)面zOx所構(gòu)成的角；θ是極點(diǎn)和任意點(diǎn)組成的直線與z軸正方向的夾角。

當(dāng)滿足式(5)時(shí)，即球體上任意一點(diǎn)(x,y,z)都不在山峰表面或內(nèi)部時(shí)，就能夠保證在任何情況下無(wú)人機(jī)都不會(huì)與山峰發(fā)生碰撞。

R(xm,ym,z)>Zi(xm,ym),xm,ym∈Si

(5)

無(wú)人機(jī)的飛行高度存在限制，超過(guò)最大值將會(huì)影響控制信號(hào)，而由于地形原因，在飛行途中無(wú)人機(jī)高度低于最小值存在與石塊和樹(shù)木碰撞的危險(xiǎn)，如式(6)所示：

Hmin≤Hi≤Hmax

(6)

其中,Hmin為無(wú)人機(jī)飛行最小高度(第4節(jié)中Hmin=10 m)，Hmax為無(wú)人機(jī)飛行最大高度(第4節(jié)中Hmax=1000 m)。

評(píng)判無(wú)人機(jī)路徑優(yōu)劣的指標(biāo)包括路徑長(zhǎng)短、路徑平滑度和路徑飛行高度等，為了能夠得到最優(yōu)路徑，將3種因素整合作為評(píng)判路徑優(yōu)劣的指標(biāo)，無(wú)人機(jī)飛行過(guò)程中經(jīng)過(guò)的2點(diǎn)間的距離如式(7)所示:

(7)

其中,(xi,yi,zi)是無(wú)人機(jī)經(jīng)過(guò)的第i個(gè)點(diǎn)的坐標(biāo)，由此無(wú)人機(jī)所經(jīng)過(guò)的總路程如式(8)所示:

(8)

其中，N為無(wú)人機(jī)一共經(jīng)過(guò)的點(diǎn)個(gè)數(shù)。無(wú)人機(jī)在飛行過(guò)程中每一次轉(zhuǎn)過(guò)的角度如圖3所示。

Figure 3 Schematic diagram of the rotation angle between two points of UAV圖3 無(wú)人機(jī)在2點(diǎn)間轉(zhuǎn)角示意圖

根據(jù)圖3可知，無(wú)人機(jī)從AB段到BC段轉(zhuǎn)過(guò)的角度為θ，其整體路徑的平均平滑度如式(9)所示:

(9)

其中,Ai表示無(wú)人機(jī)經(jīng)過(guò)的第i個(gè)點(diǎn)與第i+1個(gè)點(diǎn)組成的向量。由于無(wú)人機(jī)飛行高度增高會(huì)增加能耗且對(duì)控制信號(hào)有一定影響，所以要在保持無(wú)人機(jī)路徑安全的情況下盡可能降低飛行高度。無(wú)人機(jī)飛行過(guò)程中總的飛行平均高度如式(10)所示:

(10)

由式(7)～式(9)可以得到最終的優(yōu)化目標(biāo)函數(shù)，如式(11)所示:

minM=Lall+Q+Hall

(11)

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

3.1 傳統(tǒng)蟻群算法

蟻群算法是由Dorigo[17]于1992年在他的博士論文中提出的一種用來(lái)尋找優(yōu)化路徑的概率型算法。其靈感來(lái)源于螞蟻在尋找食物過(guò)程中發(fā)現(xiàn)路徑的行為，螞蟻在尋找食物的過(guò)程中會(huì)在爬過(guò)的道路上釋放一種信息素，螞蟻根據(jù)每條路徑上的信息素濃度選擇前進(jìn)方向，直到找到最優(yōu)路徑。

螞蟻按照不同路徑上的信息素濃度選擇下一個(gè)到達(dá)的區(qū)域，螞蟻k從區(qū)域i到區(qū)域j的轉(zhuǎn)移概率如式(12)所示:

(12)

其中,μij(t)表示在t時(shí)刻區(qū)域i與區(qū)域j之間的信息素濃度;α為一常數(shù),是信息素啟發(fā)因子，表示信息素對(duì)路徑選擇概率的影響力(第4節(jié)中α=0.7);φij(t)則表示t時(shí)刻區(qū)域i到區(qū)域j的期望；σ為期望啟發(fā)因子，表示期望對(duì)區(qū)域選擇概率的影響力(第4節(jié)中σ=0.7);S表示去除螞蟻?zhàn)哌^(guò)的區(qū)域后剩余的區(qū)域集合。期望φij(t)如式(13)所示:

(13)

其中，Lij表示區(qū)域i與區(qū)域j之間的路徑，|Lij|表示區(qū)域i與區(qū)域j之間的距離。在所有螞蟻遍歷完區(qū)域點(diǎn)后，對(duì)每條道路的信息素進(jìn)行更新，更新公式如式(14)所示:

μij(t+1)=(1-λ)μij(t)+Δμij

(14)

其中，λ為信息素?fù)]發(fā)系數(shù)(第4節(jié)中λ=0.3)，若一條道路長(zhǎng)時(shí)間沒(méi)有螞蟻經(jīng)過(guò)，其上的信息素濃度會(huì)隨著迭代次數(shù)的增加而逐漸減小。螞蟻經(jīng)過(guò)導(dǎo)致的信息素變化量如式(15)所示:

(15)

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

3.2.1 極值限定策略

傳統(tǒng)蟻群算法會(huì)因?yàn)槟承┞窂缴献哌^(guò)的螞蟻較多而信息素濃度持續(xù)上升，而其它無(wú)螞蟻經(jīng)過(guò)的路徑信息素濃度不斷下降，這樣會(huì)導(dǎo)致蟻群算法過(guò)早陷入局部最優(yōu)，所以要對(duì)信息素濃度的大小做出限定[18]，如式(16)和式(17)所示。

(16)

(17)

其中,|Lbest|是當(dāng)前全局最優(yōu)解的路徑總長(zhǎng)度;η為常數(shù)(第4節(jié)中η=0.2);Dbest為每次迭代結(jié)束后全局最優(yōu)解個(gè)數(shù)占總個(gè)體數(shù)的比例。蟻群的信息素濃度μij(t)∈[μmin(t),μmax(t)],限制信息素范圍能夠擴(kuò)大算法前期的搜索范圍，防止其過(guò)早陷入局部最優(yōu)。

3.2.2 精英策略

最優(yōu)解對(duì)所有螞蟻的路徑選擇有指導(dǎo)作用，能夠幫助算法快速收斂減少運(yùn)算時(shí)間，在信息素濃度更新公式中引入精英個(gè)體，如式(18)所示:

(18)

(19)

其中，γ為當(dāng)前最優(yōu)解個(gè)數(shù)，Pbest表示當(dāng)前全局最優(yōu)個(gè)體經(jīng)過(guò)的路徑集合。指數(shù)函數(shù)和全局最優(yōu)路徑長(zhǎng)度的加入，保證了算法在迭代次數(shù)逐漸增加的過(guò)程中，最優(yōu)個(gè)體對(duì)算法中其它個(gè)體的影響隨著迭代次數(shù)的增多而逐步增大，在保證算法前期的搜索范圍較大的情況下，使得算法整體的收斂速度加快，從而提高算法工作效率。

精英策略在算法原有搜索模式不變的情況下，加入了最優(yōu)個(gè)體對(duì)其他個(gè)體的引導(dǎo)影響，這將顯著提升算法的搜索性能。

3.2.3 擴(kuò)散策略

螞蟻釋放的信息素能夠?qū)Ω浇浵伒男袆?dòng)產(chǎn)生影響，指導(dǎo)后續(xù)螞蟻的行動(dòng)。根據(jù)螞蟻的這一協(xié)作特征，引入信息素?cái)U(kuò)散策略來(lái)加強(qiáng)位置相近螞蟻之間的協(xié)作，以加快算法的收斂。

各類揮發(fā)性物質(zhì)和氣體在空氣中的擴(kuò)散呈正態(tài)分布，離擴(kuò)散源位置越遠(yuǎn)其信息素濃度越低，將其模型在空間中表示出來(lái)，如圖4所示。

Figure 4 Pheromone diffusion space model圖4 信息素?cái)U(kuò)散空間模型

如圖4所示為信號(hào)源o點(diǎn)擴(kuò)散出的信息素在空間中的濃度分布情況。其中β和hu為常數(shù)，可以根據(jù)算法效果進(jìn)行調(diào)整，一般hu=1.2，β=π/2時(shí)得到的算法效果最好。R為信息素?cái)U(kuò)散的最大半徑，其與h、β的關(guān)系如式(20)所示:

hutanβ=R

(20)

根據(jù)圖4所示，可以得到當(dāng)螞蟻k從區(qū)域i向區(qū)域j移動(dòng)且不經(jīng)過(guò)路徑id時(shí)，在其擴(kuò)散范圍內(nèi)路徑id接收到的由路徑ij擴(kuò)散的信息素濃度如式(21)所示:

(21)

其中,ψ為一常數(shù)，|Lid|為區(qū)域i與區(qū)域d之間的距離，此時(shí)螞蟻k在路徑id上的信息素濃度改變量如式(22)所示:

(22)

通過(guò)引入信息素濃度擴(kuò)散策略，距離較近的螞蟻之間可以得到周圍螞蟻散發(fā)的信息素指引，個(gè)體總路徑越優(yōu)秀，對(duì)周圍所有螞蟻的信息素濃度影響就越大，這樣可以增加較近螞蟻之間的交流合作，加快蟻群的進(jìn)化收斂速度，避免了個(gè)體之間關(guān)聯(lián)性差導(dǎo)致算法陷入停滯的問(wèn)題。

在具體問(wèn)題中信息素按照如下方式進(jìn)行初始化：以所要到達(dá)的終點(diǎn)為圓心，距離終點(diǎn)越遠(yuǎn)其信息素濃度越低，這樣可以防止在迭代初期由于信息素相同導(dǎo)致算法盲目搜索。終點(diǎn)圓心處設(shè)置的信息素濃度為D，離圓心最遠(yuǎn)處設(shè)置的濃度為Ds，期間根據(jù)距離遠(yuǎn)近以等差為d2數(shù)列逐漸降低信息素濃度，其二維平面示意圖如圖5所示。

D-2d2D-2d2D-2d2D-2d2D-2d2D-2d2D-d2D-d2D-d2D-2d2D-2d2D-d2DD-d2D-2d2D-2d2D-d2D-d2D-d2D-2d2D-2d2D-2d2D-2d2D-2d2D-2d2

Figure 5 Two-dimensional plan view of initial pheromone

圖5 初始信息素二維平面圖

圖5中的D為終點(diǎn)信息素濃度(第4節(jié)中，D=2000)，圍繞終點(diǎn)，信息素濃度隨著與起點(diǎn)的距離增大而不斷降低，而等差數(shù)列的等差項(xiàng)d2則如式(23)所示:

(23)

其中,Ds為以終點(diǎn)為圓心可搜索區(qū)域內(nèi)最外圈各點(diǎn)的信息素濃度，在圖5中即為D-2d2(第4節(jié)中，Ds=1000);ks為按照?qǐng)D5方式，在整個(gè)搜索域內(nèi)圍繞終點(diǎn)的最大層數(shù)，例如在圖5中，整個(gè)區(qū)域內(nèi)圍繞終點(diǎn)的最大層數(shù)為2，所以ks=2。將其擴(kuò)展到三維空間中時(shí)也遵循此規(guī)則，只不過(guò)圍繞終點(diǎn)的外層平面空間變成了包圍終點(diǎn)空間的立體殼層空間，每一層外殼的信息素濃度也按照等差數(shù)列遞減。

EDACO算法流程圖如圖6所示。

Figure 6 Flow chart of EDACO algorithm圖6 EDACO算法流程圖

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

假設(shè)存在4個(gè)不同的受災(zāi)山區(qū),空間大小均為1000×1000×1000 m3，可通行，安排無(wú)人機(jī)向這4個(gè)山區(qū)的居民運(yùn)送必須的生活用品。

設(shè)螞蟻個(gè)體數(shù)N=100，最大迭代次數(shù)tmax=100，將山區(qū)空間區(qū)域看作1000×1000×1000 m3共109個(gè)位置點(diǎn)，無(wú)人機(jī)長(zhǎng)寬高分別為a=0.5 m,b=0.6 m,h=0.5 m，最大飛行高度Hmax=1000 m,途中最小飛行高度Hmin=10 m。其他的參數(shù)設(shè)置如表1所示。

Table 1 Parameter table

設(shè)定4個(gè)山區(qū)的起點(diǎn)分別為(1,5,0)，(0,5,0)，(2,9,0)，(0.5,3.5,0),4個(gè)山區(qū)的終點(diǎn)分別為(10,5,0)，(10,5,0)，(10,0.5,0)，(9.5,9.5,0)，設(shè)終點(diǎn)信息素濃度D=2000，區(qū)域內(nèi)最遠(yuǎn)處信息素濃度Ds=1000。由于已知4個(gè)山區(qū)的終點(diǎn)坐標(biāo)，所以在4個(gè)山區(qū)中，ks的值分別為999，999，999，999。

為了驗(yàn)證第3節(jié)提出的精英策略和擴(kuò)散策略對(duì)算法各方面性能有顯著提升作用，選擇1號(hào)山區(qū)作為驗(yàn)證環(huán)境，分別將單獨(dú)加入了精英策略的蟻群優(yōu)化EACO(Elite Ant Colony Optimization)算法和單獨(dú)加入擴(kuò)散策略的蟻群優(yōu)化DACO(Diffusion Ant Colony Optimization)算法與傳統(tǒng)蟻群算法運(yùn)用到該問(wèn)題中求解，求解得到的路徑圖如圖7所示。

Figure 7 Three-dimensional path diagram of three algorithms in No 1 mountain area圖7 3種算法在1號(hào)山區(qū)的三維路徑圖

從圖7中可以看到，單獨(dú)加入精英策略和單獨(dú)加入擴(kuò)散策略后的蟻群算法得到的路徑與傳統(tǒng)蟻群算法得到的路徑有很大的區(qū)別，3種算法的最終路徑長(zhǎng)度隨著迭代次數(shù)變化的過(guò)程如圖8所示。

Figure 8 Iterative diagram of three algorithms in No.1 mountain area圖8 3種算法在1號(hào)山區(qū)的迭代圖

根據(jù)圖8可知，單獨(dú)引入精英策略的蟻群算法(EACO)，其最終路徑長(zhǎng)度相對(duì)于傳統(tǒng)蟻群算法減少了5.8%，提升效果并不是特別顯著，但其迭代速度卻得到了大幅度提升，在30次左右就達(dá)到最優(yōu)；而單獨(dú)引入擴(kuò)散策略的蟻群算法(DACO)，其路徑長(zhǎng)度相對(duì)于傳統(tǒng)蟻群算法減少了18.5%，效果顯著，且其迭代速度也有小幅度的提升。由此測(cè)試可以看出，精英策略和擴(kuò)散策略能夠提升蟻群算法的收斂速度和精度等性能，表明上述精英策略、擴(kuò)散策略的改進(jìn)是有效的。

將上述參數(shù)代入到算法中，用精英擴(kuò)散蟻群優(yōu)化算法、傳統(tǒng)蟻群算法、遺傳算法和螢火蟲(chóng)算法計(jì)算得到4個(gè)山區(qū)的無(wú)人機(jī)派送路徑如圖9所示。

根據(jù)圖9中4個(gè)山區(qū)的無(wú)人機(jī)派送圖可以看出，改進(jìn)的蟻群算法(EDACO)都能找到飛行高度更低、平滑度更好的路徑。

3種對(duì)比基礎(chǔ)算法得到的4個(gè)山區(qū)的無(wú)人機(jī)派送路徑長(zhǎng)度對(duì)比數(shù)據(jù)如表2所示。表2中的Min表示最優(yōu)結(jié)果的路徑長(zhǎng)度，Time表示迭代算法獲得最優(yōu)解的時(shí)間。蟻群算法在計(jì)算時(shí)存在運(yùn)行常數(shù)階O(1)、找尋最大值的線性階O(n)和快速排序的對(duì)數(shù)階O(nlogn)，所以傳統(tǒng)蟻群算法的時(shí)間復(fù)雜度最高階為對(duì)數(shù)階O(nlogn)。改進(jìn)的蟻群算法加入的精英策略和擴(kuò)散策略只是在每次迭代結(jié)束后根據(jù)公式對(duì)信息素矩陣進(jìn)行加減運(yùn)算，僅僅增加了常數(shù)階和線性階復(fù)雜度，并沒(méi)有再增加傳統(tǒng)蟻群算法最高階對(duì)數(shù)階的運(yùn)算，所以整體來(lái)說(shuō)它們的時(shí)間復(fù)雜度相近，EDACO算法所用計(jì)算時(shí)間可能會(huì)略長(zhǎng)一點(diǎn)。Rate表示個(gè)體收斂率,即收斂到最優(yōu)結(jié)果的個(gè)體占總個(gè)體的比例。根據(jù)表2中3種基礎(chǔ)算法的數(shù)據(jù)，從求解的精度、迭代時(shí)間和粒子的收斂率3個(gè)指標(biāo)綜合評(píng)價(jià)來(lái)看，蟻群算法的效果要更為優(yōu)秀，對(duì)問(wèn)題的適應(yīng)性更好。因此改進(jìn)蟻群算法可以得到最好的優(yōu)化效果。

蟻群算法和精英擴(kuò)散蟻群優(yōu)化算法(EDACO)的結(jié)果數(shù)據(jù)如表3所示。從表3可以看出，EDACO算法在求解精度、迭代收斂速度、粒子收斂率上相對(duì)傳統(tǒng)蟻群算法都有了明顯提升，性能更加優(yōu)秀，對(duì)比于文獻(xiàn)[6～8]中改進(jìn)的蟻群算法，解決了因螞蟻個(gè)體之間關(guān)聯(lián)性差而導(dǎo)致的收斂速度慢，以及對(duì)無(wú)人機(jī)和環(huán)境有較多限制的問(wèn)題。本文EDACO算法適用環(huán)境更廣且更適合用于復(fù)雜環(huán)境下的大型無(wú)人機(jī)系統(tǒng)之中。理論上只要能夠建立環(huán)境模型，都可以采用本文所提出的EDACO算法解決問(wèn)題。選取其中的1號(hào)山區(qū)為例子，各算法迭代情況如圖10所示。根據(jù)圖10可以看出，相對(duì)于傳統(tǒng)的蟻群算法，EDACO算法在迭代40次左右就達(dá)到收斂值，其收斂速度更快、精度更高，能夠根據(jù)地形情況快速響應(yīng)為無(wú)人機(jī)提供最優(yōu)路徑，滿足無(wú)人機(jī)在復(fù)雜地形下對(duì)反應(yīng)速度和精度的要求。EDACO算法對(duì)無(wú)人機(jī)三維路徑分配問(wèn)題有著更好的適應(yīng)性。

Figure 9 UAV’s delivery path diagram of four algorithms in four mountain areas圖9 4種算法在4個(gè)山區(qū)的無(wú)人機(jī)派送路徑圖

山區(qū)編號(hào)ACOMin/km Time/s Rate/%GAMin/km Time/s Rate/%FAMin/km Time/s Rate/%11.484 767.59441.634 582.21321.495 584.702921.410 359.14551.533 877.76431.433 269.243731.591 063.12472.059 969.85451.739 673.153641.715 259.93491.564 170.04341.651 864.3735

Table 3 Comparison of algorithm results

Figure 10 Iteration diagram of four algorithms in No.1 mountain area圖10 4種算法在1號(hào)山區(qū)的迭代圖

5 結(jié)束語(yǔ)

針對(duì)受災(zāi)山區(qū)運(yùn)輸物資的無(wú)人機(jī)三維路徑規(guī)劃問(wèn)題，本文提出了一種精英擴(kuò)散蟻群算法，首先通過(guò)極值限定策略限制信息素的最大、最小范圍，防止算法陷入局部最優(yōu)；而后采用精英策略改進(jìn)信息素濃度公式，加強(qiáng)優(yōu)質(zhì)個(gè)體對(duì)種群的影響，以加快算法收斂；最后通過(guò)擴(kuò)散策略加大距離較近個(gè)體之間的交流合作，防止種群獨(dú)立搜索而陷入停滯。將精英擴(kuò)散蟻群算法EDACO、傳統(tǒng)蟻群算法、遺傳算法和螢火蟲(chóng)算法用于4個(gè)山區(qū)無(wú)人機(jī)運(yùn)送物資的實(shí)例中，結(jié)果表明改進(jìn)的算法在各方面擁有更優(yōu)秀的性能，對(duì)無(wú)人機(jī)三維路徑規(guī)劃問(wèn)題有著良好的適應(yīng)性。

值得注意的是，通過(guò)表3可以看出，雖然本文算法在路徑長(zhǎng)度和安全度等各方面都有著很大的優(yōu)勢(shì)，但這一切都必須建立在對(duì)飛行環(huán)境準(zhǔn)確建模的基礎(chǔ)上，如果對(duì)于飛行環(huán)境的建模不夠準(zhǔn)確，可能會(huì)導(dǎo)致路徑障礙判斷失誤而造成無(wú)人機(jī)撞擊墜毀事故，這對(duì)于環(huán)境的分析與建模是一個(gè)不小的挑戰(zhàn)。除此之外，本文算法較對(duì)比算法對(duì)物體碰撞的判斷要更加“嚴(yán)苛”，雖然“嚴(yán)苛”的判斷會(huì)提升無(wú)人機(jī)的飛行效率，有利于規(guī)劃出更加優(yōu)秀的路徑，但在一定程度上也會(huì)影響到無(wú)人機(jī)路徑規(guī)劃選擇的空間。后續(xù)將研究如何將該算法與其他算法融合以進(jìn)一步提高算法的性能，擴(kuò)大應(yīng)用范圍，并盡量降低建模和搜索所需時(shí)間和難度，使得算法的應(yīng)用范圍更廣、限制更少。