邱 誠(chéng)，黃大慶，王浩雪，劉耀輝

（1.南京航空航天大學(xué)電子信息工程學(xué)院，江蘇南京 210016；2.南京航空航天大學(xué)中小型無(wú)人機(jī)先進(jìn)技術(shù)工信部重點(diǎn)實(shí)驗(yàn)室，江蘇南京 210016）

近年來(lái)，各種無(wú)人機(jī)的使用、服務(wù)需求正在持續(xù)快速增長(zhǎng)。在對(duì)抗新冠肺炎期間，無(wú)人機(jī)就被用于醫(yī)療物資投遞、空中巡邏督查等方面?？臻g網(wǎng)格模型可用于實(shí)現(xiàn)無(wú)人機(jī)群飛行空間的數(shù)字表示、環(huán)境信息的預(yù)存儲(chǔ)和空間屬性的高效查詢(xún)。無(wú)人機(jī)完成任務(wù)的前提是進(jìn)行合理的航跡規(guī)劃，在空間網(wǎng)格模型的基礎(chǔ)上進(jìn)行無(wú)人機(jī)的航跡規(guī)劃更加符合信息化時(shí)代的需求[1]。

目前有多種算法被國(guó)內(nèi)外學(xué)者用于無(wú)人機(jī)的最佳航跡求解，如文獻(xiàn)[2]將啟發(fā)算法與遺傳算法結(jié)合，實(shí)現(xiàn)無(wú)人機(jī)路徑的重規(guī)劃；文獻(xiàn)[3]用一種自適應(yīng)粒子群優(yōu)化算法進(jìn)行路徑規(guī)劃；文獻(xiàn)[4]基于人工勢(shì)場(chǎng)，利用最優(yōu)控制方法求解路徑規(guī)劃；文獻(xiàn)[5]對(duì)蟻群算法進(jìn)行改進(jìn)，用來(lái)建立無(wú)人機(jī)低空航路網(wǎng)。其中，蟻群算法因?yàn)轸敯粜暂^強(qiáng)且具有正反饋機(jī)制，在無(wú)人機(jī)航跡規(guī)劃的研究中受到廣泛關(guān)注。在對(duì)蟻群算法的研究中，文獻(xiàn)[6]進(jìn)一步完善了算法的狀態(tài)轉(zhuǎn)移函數(shù)，并引入了信息素調(diào)節(jié)因子，以防止后期陷入局部最優(yōu)；文獻(xiàn)[7]在融合遺傳算法的基礎(chǔ)上改進(jìn)信息素機(jī)制；文獻(xiàn)[8]為克服蟻群算法在計(jì)算后期易陷入局部最優(yōu)的問(wèn)題，提出了混沌式搜索策略。但是，上述相關(guān)研究未考慮空域的實(shí)時(shí)性問(wèn)題，在實(shí)際應(yīng)用中，空域應(yīng)當(dāng)被賦予時(shí)間屬性。

文中在傳統(tǒng)飛行環(huán)境建模的基礎(chǔ)上提出了新的蟻群算法改進(jìn)策略，在搜索開(kāi)始前通過(guò)信息素初始化規(guī)則，先初始化全局信息素，減少算法初期盲目搜索導(dǎo)致收斂速度慢的問(wèn)題；通過(guò)部分次優(yōu)解和最優(yōu)解的交集對(duì)優(yōu)質(zhì)節(jié)點(diǎn)進(jìn)行信息素強(qiáng)化，提升算法的全局尋優(yōu)能力以及收斂速度；提出關(guān)聯(lián)時(shí)間的空域網(wǎng)格化建模，使其更加符合實(shí)際需求。

1 空域網(wǎng)格化

1.1 空域網(wǎng)格化的基本概念及方法

空間地理剖分的思想早已有之，可追溯到夏商周時(shí)期出現(xiàn)的“井田制”，該土地管理制度根據(jù)道路、渠道將土地分隔成方塊，體現(xiàn)了古老的空間剖分思想，是現(xiàn)代城市網(wǎng)格劃分思想的鼻祖。人類(lèi)對(duì)大區(qū)域空間的管理，習(xí)慣于網(wǎng)格式的“粒子化”分隔管理方式，各種典型的信息管理網(wǎng)格包括行政管理網(wǎng)格、環(huán)境監(jiān)測(cè)管理網(wǎng)格、戰(zhàn)場(chǎng)網(wǎng)格、有限元計(jì)算網(wǎng)格等。

基于空間信息剖分的思想，將空域進(jìn)行網(wǎng)格化管理，劃分成若干大小一致、相互鏈接的基本空域單元，建立空域四維時(shí)空框架。如圖1-2 所示，每個(gè)網(wǎng)格單元G（Index,Time,Property）被用于組織空域中的各類(lèi)數(shù)據(jù)，其中，Index 為網(wǎng)格單元空間編碼，用于存儲(chǔ)空間位置信息；Time 為時(shí)間戳；Property 為屬性集合?？沼蚓W(wǎng)格化的核心是將物理的空域空間通過(guò)空間規(guī)則剖分后，利用矩陣空間管理空中交通的幾何結(jié)構(gòu)和空域結(jié)構(gòu)，利用空域剖分建立唯一的全球地址碼，以地址碼作為主鍵索引各網(wǎng)格內(nèi)的數(shù)據(jù)。

圖1 空域四維時(shí)空框架的虛擬結(jié)構(gòu)

目前有三類(lèi)主要方法被用于構(gòu)建全球平面網(wǎng)格，分別是經(jīng)緯網(wǎng)格、正多面體網(wǎng)格和自適應(yīng)網(wǎng)格。

1.2 GeoSOT網(wǎng)格

圖2 空域網(wǎng)格劃分核心內(nèi)容

文中使用的網(wǎng)格化方法是一種空天地一體化的地球空間參考網(wǎng)格體系——全球經(jīng)緯度剖分網(wǎng)格[9]（Geo-graphic coordinate Subdivision grid with One dimension integer coding on 2n-Tree,GeoSOT），該方法采用經(jīng)緯度進(jìn)行地球剖分，是經(jīng)緯網(wǎng)格的一種。其設(shè)想的核心是對(duì)地球經(jīng)緯度空間實(shí)行三次擴(kuò)展（將地球及其鄰近空間的經(jīng)緯度范圍擴(kuò)展至512°×512°，將1°擴(kuò)展為64＇，將1＇擴(kuò)展為64″），將地球空間分割為一個(gè)個(gè)整度、整分、整秒的網(wǎng)格，最高一級(jí)包含整個(gè)地球空間，最小可以劃分至厘米級(jí)，共32 級(jí)剖分，可根據(jù)實(shí)際需要選擇合適的剖分層級(jí)進(jìn)行研究。例如文獻(xiàn)[10]針對(duì)戰(zhàn)場(chǎng)空域表征需要，選取了最大512 km、最小128 m 共七級(jí)網(wǎng)格進(jìn)行戰(zhàn)場(chǎng)空域表征；文獻(xiàn)[11]分析了GeoSOT 網(wǎng)格應(yīng)用在無(wú)人機(jī)碰撞檢測(cè)上的可行性，發(fā)現(xiàn)64 m 網(wǎng)格用于無(wú)人機(jī)碰撞檢測(cè)的計(jì)算時(shí)間最少。

2 蟻群算法及改進(jìn)策略

2.1 飛行環(huán)境模型建立

在傳統(tǒng)的基于蟻群算法的無(wú)人機(jī)航跡規(guī)劃研究中，通過(guò)建立柵格圖的形式建立了無(wú)人機(jī)的航行環(huán)境模型[12-16]。如圖3 所示，研究中往往簡(jiǎn)單地將黑色網(wǎng)格看作無(wú)法飛越的障礙網(wǎng)格，將白色網(wǎng)格看作可供航行的自由網(wǎng)格，從而忽略了低空環(huán)境隨時(shí)間的變化，導(dǎo)致規(guī)劃的路徑不夠科學(xué)、合理。

圖3 飛行環(huán)境模型

基于空間信息剖分的思想，文中將飛行環(huán)境模型改進(jìn)為關(guān)聯(lián)了時(shí)間屬性的網(wǎng)格化空域，選取GeoSOT中第16 級(jí)1 km×1 km 網(wǎng)格建立模型，每個(gè)網(wǎng)格除位置信息外，還對(duì)應(yīng)一個(gè)時(shí)間信息，即若該網(wǎng)格存在障礙物，則網(wǎng)格關(guān)聯(lián)一個(gè)障礙物存在的時(shí)間，在該時(shí)間范圍外該網(wǎng)格依舊可以視為自由網(wǎng)格。

2.2 蟻群算法

蟻群算法(Ant Colony Optimization，ACO)的思想源自于蟻群覓食的過(guò)程。在覓食初期，所有螞蟻均等概率地選定能夠獲取到食物的路線(xiàn)，信息素隨著螞蟻尋找的過(guò)程被釋放在螞蟻?zhàn)哌^(guò)的路線(xiàn)上，該信息素可以指導(dǎo)后來(lái)的螞蟻?zhàn)鞒雎肪€(xiàn)抉擇，同時(shí)路線(xiàn)上的信息素含量也會(huì)隨著時(shí)間衰減。同樣時(shí)間內(nèi)，相較于其他路徑而言，較短路線(xiàn)上的信息素含量會(huì)累積得更高，而由于螞蟻在路線(xiàn)選擇中偏向于挑選信息素含量高的路線(xiàn)，基于正反饋?zhàn)饔?，信息素含量較高的較短路線(xiàn)被更多的螞蟻選擇，其信息素含量也因此越來(lái)越高。由于信息素的揮發(fā)，較短路線(xiàn)上的信息素含量遠(yuǎn)高于其他路線(xiàn)時(shí)，所有螞蟻傾向于選擇該路徑，認(rèn)為該路徑為最短路徑。

2.2.1 狀態(tài)轉(zhuǎn)移函數(shù)

在蟻群算法中，蟻群根據(jù)狀態(tài)轉(zhuǎn)移函數(shù)選擇下一個(gè)路徑點(diǎn)，狀態(tài)轉(zhuǎn)移函數(shù)表示如下：

2.2.2 信息素更新機(jī)制

蟻群算法中的信息素更新機(jī)制如下：

式中，ρ為信息素蒸發(fā)系數(shù)；τij(t)為當(dāng)前信息素含量；Δτij(t)為信息素增量計(jì)算如下：

2.3 改進(jìn)策略

傳統(tǒng)蟻群算法存在以下缺點(diǎn)：①蟻群在路徑規(guī)劃初期搜索存在盲目性，收斂速度慢，搜索時(shí)間長(zhǎng)；②在某次迭代中，一只螞蟻可能發(fā)現(xiàn)了最優(yōu)解，但由于次優(yōu)解路徑上信息素已經(jīng)積累較多，導(dǎo)致最優(yōu)解與次優(yōu)解之間信息素含量存在差距，算法無(wú)法收斂于最優(yōu)解而陷于局部最優(yōu)。

針對(duì)以上兩個(gè)缺點(diǎn)，提出改進(jìn)策略。首先，對(duì)于圖3 已知起始點(diǎn)的環(huán)境模型，初始化全局信息素，加快算法初期搜索效率，更新規(guī)則為：

式中，MM 為柵格環(huán)境的列數(shù)；p為定值，為初始化信息素量；τij為由第i個(gè)柵格到第j個(gè)柵格之間的信息素量。

其次，提出改進(jìn)的信息素更新機(jī)制，如下：

式中，Δτbetter(t)表示在此次迭代中所搜尋路線(xiàn)長(zhǎng)度最短的五只螞蟻在路徑(i,j)上釋放的額外信息素總量；為此次迭代中，搜尋路徑最短的五只螞蟻中第m只螞蟻在路徑(i,j)上釋放的額外信息素量；為搜尋路徑最短的第m只螞蟻搜索到的路徑長(zhǎng)度；Lbest為當(dāng)前歷史最短路徑長(zhǎng)度；ω為一常數(shù)，用于控制次優(yōu)解釋放額外信息素量的大小。

改進(jìn)的信息素更新機(jī)制將一代螞蟻搜索路徑長(zhǎng)度排序，選出五只搜索的路徑最短的螞蟻，將其搜索到的路徑與當(dāng)前歷史最優(yōu)路徑進(jìn)行比較，對(duì)屬于歷史最優(yōu)解和五個(gè)較優(yōu)解交集的路徑(i,j)進(jìn)行信息素增強(qiáng)，強(qiáng)化優(yōu)質(zhì)路徑上間的信息素量，加快算法收斂的同時(shí)提高螞蟻的尋優(yōu)能力[17]。

2.4 基于改進(jìn)蟻群算法的航跡規(guī)劃

利用改進(jìn)的蟻群算法進(jìn)行無(wú)人機(jī)航跡規(guī)劃，具體步驟如下：

1）初始化算法各參數(shù)，初始化搜索空間，每個(gè)網(wǎng)格關(guān)聯(lián)一個(gè)時(shí)間碼；

2）對(duì)于已知起始點(diǎn)的環(huán)境模型，初始化全局信息素；

3）將所有螞蟻置于初始位置，創(chuàng)建新的禁忌表Tabu，并將此時(shí)的位置加入禁忌表中；

4）更新螞蟻在當(dāng)前位置的可選節(jié)點(diǎn)集合，計(jì)算啟發(fā)函數(shù)以及各節(jié)點(diǎn)轉(zhuǎn)移概率；

5）螞蟻根據(jù)輪盤(pán)賭的方式選擇下一節(jié)點(diǎn)j，螞蟻到達(dá)節(jié)點(diǎn)j后，更新禁忌表Tabu，將節(jié)點(diǎn)j加入禁忌表；

6）判斷螞蟻是否到達(dá)目標(biāo)點(diǎn)E，若是，則停止搜索，迭代結(jié)束；否則，轉(zhuǎn)到步驟4），直到到達(dá)目標(biāo)點(diǎn)E；

7）當(dāng)全部螞蟻都抵達(dá)了目標(biāo)點(diǎn)E 后，迭代結(jié)束，記錄每代中每只螞蟻經(jīng)過(guò)的路線(xiàn)以及長(zhǎng)度，并記錄在此次迭代中所找到的路徑總長(zhǎng)度較短的前五只螞蟻的序號(hào)，對(duì)這五只螞蟻經(jīng)過(guò)的路線(xiàn)與當(dāng)前長(zhǎng)度最短的路線(xiàn)取交集，進(jìn)行信息素更新；

8）確定當(dāng)前迭代次數(shù)是否已到達(dá)最大值，如果是，則輸出為最佳路徑；否則，轉(zhuǎn)到步驟3）繼續(xù)迭代。

3 仿真結(jié)果分析

文中所使用的仿真平臺(tái)是Matlab2014a，硬件工作環(huán)境：CPU 參數(shù)為Intel Core i7-6700HQ 2.60 GHz，內(nèi)存8.00 GB。規(guī)劃范圍為20 km×20 km 的二維空域平面空間，仿真的關(guān)鍵參數(shù)設(shè)置如表1 所示。

表1 仿真參數(shù)設(shè)置

3.1 柵格環(huán)境建模下仿真

為了對(duì)改進(jìn)前后算法的性能做合理的對(duì)比分析，對(duì)改進(jìn)前后算法取相同參數(shù)。傳統(tǒng)蟻群算法最優(yōu)航跡及改進(jìn)蟻群算法最優(yōu)航跡分別如圖4 和圖5所示，對(duì)比兩圖可知，改進(jìn)后的蟻群算法所得最優(yōu)航跡明顯較傳統(tǒng)蟻群算法平滑。

圖4 傳統(tǒng)蟻群算法最優(yōu)航跡

圖5 改進(jìn)蟻群算法最優(yōu)航跡

傳統(tǒng)蟻群算法收斂曲線(xiàn)及改進(jìn)蟻群算法收斂曲線(xiàn)分別如圖6 和圖7 所示，結(jié)合實(shí)驗(yàn)數(shù)據(jù)可知，傳統(tǒng)蟻群算法規(guī)劃的最短路徑長(zhǎng)度為34.041 6 km，在迭代第43 次達(dá)到最優(yōu)，而最后卻收斂于次優(yōu)解；改進(jìn)蟻群算法規(guī)劃的最短路徑長(zhǎng)度為31.556 3 km，在迭代第31 次達(dá)到最優(yōu)且收斂。傳統(tǒng)蟻群算法并不能收斂到最優(yōu)解，主要是因?yàn)楫?dāng)螞蟻發(fā)現(xiàn)了最優(yōu)解時(shí)，由于在次優(yōu)解上的信息素積累已經(jīng)較多，使得螞蟻在一次迭代中，從最優(yōu)路徑上釋放的信息素對(duì)后來(lái)的螞蟻無(wú)法產(chǎn)生足夠的誘導(dǎo)影響，從而使得計(jì)算陷于局部最優(yōu)，改進(jìn)的蟻群算法基本解決了這個(gè)問(wèn)題。

圖6 傳統(tǒng)蟻群算法收斂曲線(xiàn)

圖7 改進(jìn)蟻群算法收斂曲線(xiàn)

對(duì)改進(jìn)前后的算法分別進(jìn)行10 次重復(fù)實(shí)驗(yàn)，所得數(shù)據(jù)如表2 所示。

表2 改進(jìn)前后蟻群算法對(duì)比

由表2 可知，文中所給出的改進(jìn)蟻群算法比起傳統(tǒng)蟻群算法更具優(yōu)勢(shì)，平均路徑長(zhǎng)度縮短了6.5%，且所尋得的最優(yōu)路徑顯著優(yōu)于傳統(tǒng)蟻群算法所尋得的最優(yōu)路徑，平均迭代次數(shù)降低了41%。對(duì)比兩種算法的結(jié)果顯示，文中給出的改進(jìn)蟻群算法不但收斂速度快而且所尋路徑也更優(yōu)，從而證明了算法的可行性。

3.2 關(guān)聯(lián)時(shí)間的網(wǎng)格化環(huán)境建模下仿真

設(shè)無(wú)人機(jī)飛行速度為30 km/h，預(yù)計(jì)11:15從起始點(diǎn)飛往目標(biāo)點(diǎn)，關(guān)聯(lián)時(shí)間的網(wǎng)格模型如圖8 所示。箭頭所指部分為臨時(shí)禁空區(qū)，空域禁用時(shí)間為10:00-11:30。采用改進(jìn)的蟻群算法進(jìn)行航跡規(guī)劃，起始點(diǎn)坐標(biāo)(0,20)，目標(biāo)點(diǎn)坐標(biāo)(20,0)，關(guān)聯(lián)時(shí)間的網(wǎng)格化環(huán)境下得到的最優(yōu)路徑如圖9 所示。由圖8 可知，所規(guī)劃路徑穿過(guò)了臨時(shí)禁飛區(qū)，這是因?yàn)樵诖舜温窂揭?guī)劃中，當(dāng)路徑搜索至該臨時(shí)禁空區(qū)時(shí)，空域已變?yōu)榭赏ㄐ袪顟B(tài)，無(wú)人機(jī)可選擇該區(qū)域里的節(jié)點(diǎn)作為航跡規(guī)劃的節(jié)點(diǎn)。圖8所示的最優(yōu)路徑長(zhǎng)度為28.041 6 km，對(duì)比3.1 節(jié)中的最優(yōu)路徑長(zhǎng)度，明顯得到了一條更優(yōu)路徑，并且也在一定程度節(jié)約了空域資源。

圖8 關(guān)聯(lián)時(shí)間的網(wǎng)格模型

圖9 關(guān)聯(lián)時(shí)間的網(wǎng)格化環(huán)境下的最優(yōu)路徑

4 結(jié)論

無(wú)人機(jī)行業(yè)的快速發(fā)展離不開(kāi)空間信息科學(xué)的進(jìn)步，數(shù)字地球的概念為無(wú)人機(jī)在低空安全、合理地飛行創(chuàng)造了條件。文中采用了空域網(wǎng)格化方式，對(duì)傳統(tǒng)蟻群算法加以改良，改進(jìn)蟻群算法可獲得更快的收斂速度并且具有更強(qiáng)的全局尋優(yōu)能力，更容易取得最優(yōu)解且得到的路徑長(zhǎng)度更短。將飛行環(huán)境網(wǎng)格化并為每個(gè)網(wǎng)格賦予時(shí)間屬性，更加符合實(shí)際需求，發(fā)展動(dòng)態(tài)數(shù)字空域?qū)⑹钱?dāng)下和未來(lái)的研究重點(diǎn)。

文中旨在說(shuō)明對(duì)空域進(jìn)行網(wǎng)格化處理以及在算法中賦予其時(shí)間屬性的重要性以及對(duì)傳統(tǒng)蟻群算法用于航跡規(guī)劃中存在的缺點(diǎn)進(jìn)行改進(jìn)，故僅在二維環(huán)境下進(jìn)行仿真，后續(xù)研究應(yīng)當(dāng)建立三維場(chǎng)景進(jìn)行仿真。