程潔， 鄭遠(yuǎn)， 李誠龍，3， 江波， 劉東來

(1.中國民用航空飛行學(xué)院空中交通管理學(xué)院， 廣漢 618307； 2.中國民用航空飛行學(xué)院計(jì)算機(jī)學(xué)院， 廣漢 618307； 3.北京航空航天大學(xué)電子信息工程學(xué)院， 北京 100191)

無人機(jī)(unmanned aerial vehicle， UAV)作為中國科技創(chuàng)新的重要產(chǎn)業(yè)，其技術(shù)日漸成熟，能夠執(zhí)行復(fù)雜、危險(xiǎn)的任務(wù)，以“小、快、靈活”的優(yōu)勢逐漸應(yīng)用于城市物流配送中[1]，在低空航空領(lǐng)域占有一席之地[2]。美國聯(lián)邦航空管理局(Federal Aviation Administration， FAA)在107部規(guī)章中提出了輕小型無人機(jī)可在距離地面120 m高度下飛行[3]，并將120 m以下城市空域劃為城市超低空空域。在120 m以下的城市超低空場景中，無人機(jī)工作環(huán)境較為復(fù)雜，使得無人機(jī)在飛行過程中具有一定失控墜落的概率，從而撞擊地面的行人、車輛及關(guān)鍵基礎(chǔ)設(shè)施，造成一定的財(cái)產(chǎn)損失。因此，路徑規(guī)劃是幫助無人機(jī)運(yùn)行安全管理、高效完成任務(wù)的關(guān)鍵之一[4]。如何在一定約束條件下，快速搜索一條或多條起始點(diǎn)到目標(biāo)位置的無碰撞安全性較高的低風(fēng)險(xiǎn)路徑[5]，已成路徑規(guī)劃領(lǐng)域的研究熱點(diǎn)。近年來，多種算法被用來解決無人機(jī)路徑規(guī)劃問題，其中A*算法[6]是經(jīng)典的啟發(fā)式搜索算法，具有計(jì)算量較小、路徑規(guī)劃結(jié)果較優(yōu)等特點(diǎn)，被廣泛應(yīng)用于路徑規(guī)劃研究。

現(xiàn)有基于傳統(tǒng)A*算法的改進(jìn)工作主要集中于優(yōu)化啟發(fā)函數(shù)、提高搜索效率。Duchoň等[7]基于柵格地圖對A*算法的啟發(fā)函數(shù)權(quán)重系數(shù)進(jìn)行改進(jìn)，使改進(jìn)后的算法可以適應(yīng)不同場景；鄭煜坤等[8]提出了一種基于“追蹤”思想的改進(jìn)A*算法，滿足實(shí)際飛機(jī)飛行安全性需求；詹京吳等[9]提出一種基于安全考慮的改進(jìn)A*算法，與動態(tài)窗口法相融合進(jìn)行路徑規(guī)劃，可以在復(fù)雜環(huán)境中保證飛機(jī)的安全性；袁千賀等[10]提出一種基于改進(jìn)A*與動態(tài)窗口方法相融合的移動無人機(jī)導(dǎo)航算法，引入環(huán)境信息自適應(yīng)調(diào)整代價(jià)函數(shù)，提高了搜索效率；張啟錢等[11]針對復(fù)雜低空物流無人機(jī)路徑規(guī)劃問題，提出一種改進(jìn)A*算法，引入柵格危險(xiǎn)度因子等系數(shù)，保證無人機(jī)飛行安全；王維等[12]通過估價(jià)函數(shù)進(jìn)行指數(shù)衰減的方式加權(quán)減少了冗余的擴(kuò)展；沈克宇等[13]針對A*算法遍歷節(jié)點(diǎn)過多、轉(zhuǎn)折角度較大的問題提出一種能自適應(yīng)場景地圖的改進(jìn)A*算法，進(jìn)而減少遍歷節(jié)點(diǎn)數(shù)量、提高搜索效率；程杰等[14]針對A*算法在無人水面艇路徑規(guī)劃中由于無約束導(dǎo)致的安全問題，提出了一種優(yōu)化搜索和平滑的A*算法，從而提高無人水面艇路徑規(guī)劃的安全性；除A*算法外，李少波等[15]深入調(diào)查遺傳算法(GA)在機(jī)器人路徑規(guī)劃應(yīng)用領(lǐng)域，闡述現(xiàn)階段技術(shù)難點(diǎn)，并對發(fā)展趨勢進(jìn)行展望。從上述文獻(xiàn)可以看出，現(xiàn)有研究主要以路徑代價(jià)為目標(biāo)函數(shù)，在安全性方面僅保證不與障礙物相撞；然而在無人機(jī)飛行過程中，還應(yīng)考慮障礙物對應(yīng)的地區(qū)類型。由此，無人機(jī)對地面風(fēng)險(xiǎn)等級的研究受到中外學(xué)者的廣泛關(guān)注。Pang等[16]提出了一種考慮綜合成本評估模型的路徑優(yōu)化方法，該方法能夠有效降低飛行成本；Koh等[17]研究了無人機(jī)失控墜落與地面人員撞擊并致死間的關(guān)系；胡莘婷等[18]建立基于城區(qū)行人安全的無人機(jī)運(yùn)行風(fēng)險(xiǎn)評估模型，提高無人機(jī)在城區(qū)運(yùn)行的安全性。但上述文獻(xiàn)僅考慮了無人機(jī)運(yùn)行安全性與地面區(qū)域之間的關(guān)系，沒有基于城市超低空物流場景且在路徑規(guī)劃方面沒有實(shí)際應(yīng)用。

綜上所述，針對現(xiàn)有路徑規(guī)劃算法無法滿足超低空物流運(yùn)輸無人機(jī)在密集障礙物場景下進(jìn)行安全軌跡規(guī)劃問題，現(xiàn)提出一種基于120 m以下的超低空城市物流運(yùn)輸仿真場景的面向城市超低空物流場景的最小風(fēng)險(xiǎn)路徑規(guī)劃算法。

具體而言，本文研究以規(guī)劃風(fēng)險(xiǎn)最小軌跡為目標(biāo)，通過在飛行時(shí)避開高風(fēng)險(xiǎn)區(qū)域減輕突發(fā)情況造成的風(fēng)險(xiǎn)和影響；首先，從時(shí)間、風(fēng)險(xiǎn)兩個(gè)維度對成本估計(jì)函數(shù)進(jìn)行重構(gòu)，兼顧航程距離和風(fēng)險(xiǎn)成本；其次，基于重構(gòu)后的成本函數(shù)，提出一種適用于城市物流場景的最小風(fēng)險(xiǎn)路徑規(guī)劃算法，規(guī)劃得到安全性較高的無人機(jī)飛行路徑；最后?？紤]高度層架構(gòu)，基于先到先服務(wù)原則將該算法應(yīng)用于多無人機(jī)場景，實(shí)現(xiàn)多無人機(jī)在不同飛行高度層的無沖突低風(fēng)險(xiǎn)路徑規(guī)劃。

1 問題描述與環(huán)境設(shè)定

安全飛行是民航無人機(jī)的生命線[19]，然而無人機(jī)所處的超低空空域的飛行環(huán)境隨著無人機(jī)行業(yè)的發(fā)展逐漸呈現(xiàn)出復(fù)雜化、多變化的趨勢，因此為確保無人機(jī)在飛行過程中的安全性，需要對路徑進(jìn)行合理、安全地規(guī)劃。通常情況下，輕小型無人機(jī)進(jìn)近與離場階段由地面機(jī)場直接控制，而巡航階段只在某一確定高度范圍的高度層中進(jìn)行[20]。在120 m以下超低空城市物流運(yùn)輸交通網(wǎng)絡(luò)中，運(yùn)用劃分高度層的方式，可以使無人機(jī)在路徑規(guī)劃時(shí)選擇更短直的路徑，更大程度的降低擁堵的概率，有效提高無人機(jī)在飛行過程中的安全性[21]，城市空中交通高度層劃分后路徑規(guī)劃示意圖如圖1[22]所示。因此，將120 m以下巡航空域劃分為多個(gè)高度層，僅考慮確定高度層的巡航階段軌跡預(yù)規(guī)劃問題，更符合實(shí)際應(yīng)用的需求。

首先對環(huán)境進(jìn)行建模，依據(jù)文獻(xiàn) [23]，將空域劃分為層高15 m的多個(gè)高度層，符合無人機(jī)規(guī)模、無人機(jī)間安全距離等因素，即將120 m以下的三維超低空空域劃分為45～60 m、60～75 m、75～90 m、90～105 m和105～120 m 5個(gè)高度層空域，圖2為劃分高度層示意圖。

以每個(gè)高度層的上限層作為障礙物投影面，無人機(jī)抽象為質(zhì)點(diǎn)，在投影面中進(jìn)行二維路徑規(guī)劃。本文主要考慮的是如何在起飛前進(jìn)行預(yù)規(guī)劃，因此不考慮飛行過程中的動態(tài)障礙物。首先根據(jù)柵格粒度lgrid，即柵格邊長[24]，將環(huán)境劃分為u×v個(gè)單元格。環(huán)境約束為

{(x，y)|0≤x≤lgridu， 0≤y≤lgridv}

(1)

式(1)中：(x，y)為柵格中心坐標(biāo)；lgrid為柵格粒度；u、v為x軸、y軸對應(yīng)柵格數(shù)。每個(gè)柵格狀態(tài)信息表示為

圖1 飛行高度層劃分示意圖Fig.1 Schematic diagram of flight level division

圖2 飛行高度層Fig.2 Flight level

(2)

式(2)中：N(x，y)=0表示無障礙物，無人機(jī)可自由通行；N(x，y)=1表示有障礙物，無人機(jī)禁止通行；(x，y)為柵格中心坐標(biāo)。

2 基于A*算法的最小風(fēng)險(xiǎn)路徑規(guī)劃算法

針對120 m以下的超低空城市物流運(yùn)輸仿真場景，如何通過改進(jìn)A*算法得到無人機(jī)在多高度層基礎(chǔ)上獲得安全性較高的路徑顯得較為重要。本節(jié)簡述了傳統(tǒng)A*算法、改進(jìn)A*算法啟發(fā)函數(shù)、風(fēng)險(xiǎn)等級代價(jià)函數(shù)設(shè)計(jì)、路徑評價(jià)指標(biāo)4個(gè)方面，闡述了面向城市超低空物流場景的最小風(fēng)險(xiǎn)路徑規(guī)劃算法如何解決密集障礙物場景下的無人機(jī)路徑規(guī)劃問題，并在2.5節(jié)描述了本文方法應(yīng)用于多無人機(jī)運(yùn)行場景。

2.1 傳統(tǒng)A*算法

A*算法是一種啟發(fā)式的圖搜索算法，以Dijkstra[25]啟發(fā)式搜索算法為基礎(chǔ)，其搜索框架與Dijkstra算法相同，但A*算法啟發(fā)式函數(shù)優(yōu)于Dijkstra算法，適用于快速搜索最短路徑，并能夠在多約束條件及任意形狀的威脅環(huán)境下進(jìn)行路徑規(guī)劃，特別是在大面積的地圖中[26]。A*算法的核心是在候選路徑點(diǎn)集中選擇代價(jià)函數(shù)值最小的節(jié)點(diǎn)進(jìn)行拓展，將最小值節(jié)點(diǎn)作為下一步拓展的節(jié)點(diǎn)，循環(huán)以上步驟，直到達(dá)到目標(biāo)點(diǎn)。A*算法的啟發(fā)函數(shù)[27]為

f(n)=g(n)+h(n)

(3)

式(3)中：n為當(dāng)前節(jié)點(diǎn)；g(n)為積累代價(jià)，即從起始點(diǎn)到當(dāng)前節(jié)點(diǎn)累計(jì)的實(shí)際距離；h(n)為目標(biāo)代價(jià)，即從當(dāng)前節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的估計(jì)代價(jià)值。

通常情況下，g(n)使用曼哈頓距離計(jì)算，表達(dá)式如式(4)所示；h(n)運(yùn)用歐幾里得距離作為函數(shù)估計(jì)值，表達(dá)式為

g(n)=|xn-xs|+|yn-ys|

(4)

(5)

式中：(xn，yn)為當(dāng)前點(diǎn)坐標(biāo)；(xs，ys)為起始點(diǎn)坐標(biāo)；(xg，yg)為目標(biāo)點(diǎn)坐標(biāo)。

2.2 改進(jìn)啟發(fā)函數(shù)

A*算法在路徑搜索過程中，啟發(fā)函數(shù)g(n)和h(n)對路徑評估的影響是不同的，權(quán)重系數(shù)的變化會引起最終搜索路徑的變化[28]，加權(quán)后的啟發(fā)函數(shù)為

f(n)=αg(n)+βh(n)

(6)

式(6)中：α為g(n)代價(jià)的權(quán)重系數(shù)；β為h(n)代價(jià)的權(quán)重系數(shù)。α、β的取值會影響A*算法的計(jì)算效率，選擇合適的權(quán)重系數(shù)十分重要[29]。根據(jù)文獻(xiàn)[30]，當(dāng)α+β=1時(shí)，能夠在規(guī)劃過程中平衡兩種代價(jià)函數(shù)。本文考慮加權(quán)評估后的合理性，選擇α和β分別為

α=e-0.1tn

(7)

β=1-e-0.1tn

(8)

將式(6)和式(7)代入式(5)，可以得到優(yōu)化后A*算法的估計(jì)代價(jià)函數(shù)，即

f(n)=e-0.1tng(n)+(1-e-0.1tn)h(n)

(9)

(10)

式中：tn為位置系數(shù)，表征當(dāng)前位置和起始點(diǎn)、目標(biāo)點(diǎn)間的關(guān)系，由積累代價(jià)g(n)與目標(biāo)代價(jià)h(n)的比值確定。

2.3 風(fēng)險(xiǎn)等級代價(jià)函數(shù)設(shè)計(jì)

傳統(tǒng)A*算法在搜索路徑時(shí)并未將與障礙物的安全距離納入啟發(fā)函數(shù)中，當(dāng)障礙物較密集的區(qū)域人群也相對密集，為避免無人機(jī)在飛行過程中發(fā)生突發(fā)事件造成嚴(yán)重后果，在飛行前規(guī)劃過程中應(yīng)盡可能遠(yuǎn)離障礙物，保證無人機(jī)飛行安全與地面高密集區(qū)域的人群安全。

將無人機(jī)路徑點(diǎn)與最近障礙物柵格中心的歐幾里得距離作為安全距離，充分考慮飛機(jī)與障礙物之間的安全距離，將環(huán)境根據(jù)距最近障礙物柵格的距離劃分為3個(gè)風(fēng)險(xiǎn)等級，越靠近障礙物的柵格風(fēng)險(xiǎn)等級越高，反之風(fēng)險(xiǎn)等級越低，如式(10)～式(12)所示。

(11)

(12)

(13)

式中：R(xi，yi)為柵格(xi，yi)風(fēng)險(xiǎn)等級；k為障礙物個(gè)數(shù)；risk(xi，yi，xo，yo)為柵格風(fēng)險(xiǎn)等級篩選條件；d(xi，yi，xo，yo)為安全距離，即(xi，yi)與距離最近障礙物中心坐標(biāo)(xo，yo)的歐幾里得距離。風(fēng)險(xiǎn)等級劃分示意圖如圖3所示，圖3中黑色柵格為障礙物，柵格中數(shù)字代表柵格風(fēng)險(xiǎn)等級。

在選擇下一節(jié)點(diǎn)時(shí)，不同風(fēng)險(xiǎn)等級的當(dāng)前節(jié)點(diǎn)與下一節(jié)點(diǎn)之間存在9種擴(kuò)展情況，如圖4所示。

圖3 風(fēng)險(xiǎn)等級劃分示意圖Fig.3 Risk level classification diagram

圖4 節(jié)點(diǎn)擴(kuò)展情況Fig.4 Node expansion

(14)

與傳統(tǒng)A*算法代價(jià)函數(shù)不同，本文將風(fēng)險(xiǎn)等級代價(jià)納入啟發(fā)函數(shù)，在規(guī)劃過程中具有一定的自適應(yīng)性，能夠自主避開障礙物的同時(shí)兼顧飛行路徑的運(yùn)行風(fēng)險(xiǎn)，與傳統(tǒng)算法僅考慮運(yùn)行時(shí)間與航程有較大區(qū)別。將風(fēng)險(xiǎn)等級代價(jià)函數(shù)值納入啟發(fā)函數(shù)f(n)，優(yōu)化后的A*算法啟發(fā)函數(shù)W(n)為

W(n)=f(n)+γr(n)

=αg(n)+βh(n)+γr(n)

(15)

式(15)中：f(n)為估計(jì)代價(jià)函數(shù)；r(n)為風(fēng)險(xiǎn)等級代價(jià)函數(shù)；γ為風(fēng)險(xiǎn)等級代價(jià)函數(shù)值權(quán)重系數(shù)，γ根據(jù)擴(kuò)展節(jié)點(diǎn)所在風(fēng)險(xiǎn)等級由低至高依次增大，即

(16)

式(16)中：n為G(n)的輸入變量；i為擴(kuò)展柵格風(fēng)險(xiǎn)等級。

2.4 路徑評價(jià)指標(biāo)

A*算法常使用路徑代價(jià)作為評價(jià)指標(biāo)[31]，但忽略了路徑的安全距離，因此，本文兼顧路徑的安全性，重新定義路徑的評價(jià)指標(biāo)，即

(17)

式(17)中：L(n)為路徑總長度；T(n)為路徑節(jié)點(diǎn)距最近障礙物距離總和。

(18)

(19)

式中：(xn，yn)為路徑節(jié)點(diǎn)坐標(biāo)；m為路徑點(diǎn)個(gè)數(shù)；d(xn，yn，xo，yo)為(xn，yn)與距離最近障礙物中心坐標(biāo)(xo，yo)的歐幾里得距離；k為障礙物個(gè)數(shù)。

2.5 多無人機(jī)場景應(yīng)用

針對多無人機(jī)路徑規(guī)劃問題，基于高度層架構(gòu)及上述最小風(fēng)險(xiǎn)路徑規(guī)劃算法，在多無人機(jī)路徑規(guī)劃中兼顧路徑安全性，在先到先服務(wù)的基礎(chǔ)上，依據(jù)起飛次序規(guī)劃各無人機(jī)在每個(gè)高度層中路徑，并計(jì)算路徑評價(jià)指標(biāo)，選擇最小評價(jià)指標(biāo)的高度層作為無人機(jī)最終飛行高度層，即

(20)

式(20)中：ω為高度層。

實(shí)際操作中，在前序規(guī)劃得到的無人機(jī)路徑點(diǎn)納入障礙物列表，并在無人機(jī)降落后予以刪除；若后續(xù)無人機(jī)無法在所有高度層中規(guī)劃得到無沖突路徑，則推遲該無人機(jī)起飛時(shí)間，直至可以規(guī)劃到無沖突路徑時(shí)。

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

3.1 規(guī)劃區(qū)域定義

本次實(shí)驗(yàn)基于Python進(jìn)行仿真。隨著高度層增加，障礙物柵格占地圖柵格比例逐漸減少，取地圖柵格的20%、15%、12%、8.75%和6%作為障礙物數(shù)，與高度層45～60 m、60～75 m、75～90 m、90～105 m和105～120 m依次對應(yīng)。設(shè)置場景1、場景2和場景3分別對應(yīng)實(shí)際范圍為1 500 m×1 500 m、2 000 m×2 000 m及2 500 m×2 500 m的場景，柵格粒度lgrid取50 m，即地圖場景分別是場景1∶30×30、場景2∶40×40和場景3∶50×50。基于這3個(gè)場景，本文研究進(jìn)行了3個(gè)仿真實(shí)驗(yàn)：實(shí)驗(yàn)一為相同場景下的算法對比試驗(yàn)，展現(xiàn)了本文所提方法在低風(fēng)險(xiǎn)路徑規(guī)劃上的優(yōu)越性；實(shí)驗(yàn)二為本文所提方法在多無人機(jī)多高度層復(fù)雜場景下驗(yàn)證實(shí)驗(yàn)，展現(xiàn)本文方法在復(fù)雜城市空中交通場景下的通用型；實(shí)驗(yàn)三為蒙特卡洛仿真實(shí)驗(yàn)，驗(yàn)證了本文所提方法的實(shí)用性和可靠性。

3.2 實(shí)驗(yàn)一：優(yōu)化A*算法路徑規(guī)劃對比實(shí)驗(yàn)

將原A*算法啟發(fā)函數(shù)權(quán)重系數(shù)優(yōu)化為動態(tài)變化，并加入風(fēng)險(xiǎn)等級代價(jià)函數(shù)。在實(shí)驗(yàn)中各場景中，無人機(jī)的起始點(diǎn)坐標(biāo)均為(0，0)，目標(biāo)點(diǎn)的坐標(biāo)分別為(29，29)、(39，39)和(49，49)。在保持各項(xiàng)權(quán)重系數(shù)計(jì)算公式不變的條件下，在場景1、場景2和場景3下分別進(jìn)行30次實(shí)驗(yàn)，將本文算法較原算法在地圖場景中不同高度層路徑規(guī)劃后的安全距離和路徑代價(jià)的平均增長比數(shù)據(jù)如表1和表2所示；將不同場景下本文算法較原算法評價(jià)指標(biāo)的平均增長比數(shù)據(jù)如表3所示。

從表1和表2看出，與原算法安全距離與路徑代價(jià)相比，優(yōu)化后算法評價(jià)指標(biāo)都有不同程度的增長，是由于優(yōu)化后的啟發(fā)函數(shù)同時(shí)考慮路徑代價(jià)和風(fēng)險(xiǎn)等級，所以路徑代價(jià)有小幅度增加。但從表3中看出，優(yōu)化后算法的安全距離較原算法提高約60%，平均路徑代價(jià)較原算法增長約14%；畫出原算法與本文算法在15種不同情況下的路徑代價(jià)和安全距離的對比圖，如圖5所示，可以看出本文算法的安全距離有大幅提升。

表1 安全距離增長比Table 1 Safe distance growth ratio

表2 路徑代價(jià)增長比Table 2 Path cost growth ratio

表3 優(yōu)化后平均增長比Table 3 Average growth ratio after optimization

圖5 評價(jià)指標(biāo)對比圖Fig.5 Evaluation index comparison chart

以地圖尺度30×30的場景1為例，比較原算法與改進(jìn)后算法在障礙物比例分別為20%、15%、12%、8.75%和6%的5個(gè)高度層下，規(guī)劃得到的路徑結(jié)果，結(jié)果如圖6所示。圖中黑線為原A*算法全局路徑規(guī)劃結(jié)果；藍(lán)線為改進(jìn)后A*算法路徑規(guī)劃結(jié)果；黑色柵格為障礙物，柵格顏色依次變淺表示風(fēng)險(xiǎn)等級依次降低，除障礙物柵格外均為可擴(kuò)展柵格。從圖5中可以明顯看出，改進(jìn)后A*算法的與障礙物的安全距離有大幅提升。

3.3 實(shí)驗(yàn)二：多無人機(jī)多高度層路徑規(guī)劃實(shí)驗(yàn)

實(shí)驗(yàn)一已經(jīng)驗(yàn)證了本文提出面向城市超低空物流場景的最小風(fēng)險(xiǎn)路徑規(guī)劃算法能夠大幅提升無人機(jī)路徑的安全性，而本節(jié)實(shí)驗(yàn)主要考慮了多無人機(jī)路徑規(guī)劃問題，將本文提出方法在多無人機(jī)多高度層的運(yùn)行場景中進(jìn)行驗(yàn)證。如表4所示，現(xiàn)有八架無人機(jī)運(yùn)用于場景1中，各無人機(jī)起降點(diǎn)坐標(biāo)、飛行時(shí)間都不相同?；?.5節(jié)將綜合權(quán)值的路徑評價(jià)指標(biāo)作為選擇飛行高度層的依據(jù)，將前序規(guī)劃得到的無人機(jī)路徑納入障礙物列表，在該無人機(jī)降落后予以刪除；若后續(xù)無人機(jī)無法在所有高度層中規(guī)劃得到無沖突路徑，則推遲該無人機(jī)的起飛時(shí)間，直至可以規(guī)劃得到無沖突路徑。

圖6 場景1：不同高度層的路徑規(guī)劃算法結(jié)果對比圖Fig.6 Scenario 1:comparison chart of path planning algorithm results at different flight levels

表4 多無人機(jī)數(shù)據(jù)Table 4 Multi-UAV data

經(jīng)過規(guī)劃，得到上述8架無人機(jī)在不同飛行高度層的無沖突路徑規(guī)劃結(jié)果，即UAV-7在高度層1 中飛行；UAV-1在高度層2 中飛行；UAV-5和UAV-8在高度層3中飛行，盡管路徑間存在交叉，但是在不同時(shí)通過交叉路徑，不會產(chǎn)生沖突；UAV-2在高度層4中飛行；UAV-5在高度層5中飛行。最終路徑規(guī)劃結(jié)果如圖7所示。

綜上所述，本文所提方法不但能解決單機(jī)路徑規(guī)劃問題，還能應(yīng)用于多無人機(jī)多高度層的復(fù)雜城市空中交通運(yùn)行環(huán)境中。通過本多無人機(jī)多高度層路徑規(guī)劃實(shí)驗(yàn)可知，本文提出的面向城市超低空物流場景的最小風(fēng)險(xiǎn)路徑規(guī)劃算法能夠在復(fù)雜場景下，將最小綜合權(quán)值作為評價(jià)指標(biāo)選擇無人機(jī)飛行高度層，同時(shí)，在飛行前避開高密集區(qū)域，規(guī)劃得到多架無人機(jī)的無沖突路徑。

圖7 多無人機(jī)多高度層路徑規(guī)劃結(jié)果Fig.7 Multi-UAV multi-layer path planning results

3.4 實(shí)驗(yàn)三：蒙特卡洛仿真實(shí)驗(yàn)

蒙特卡洛仿真法[32]是以概率統(tǒng)計(jì)為基礎(chǔ)的一種仿真方法，其基本思路是通過大量的仿真實(shí)驗(yàn)，得到參數(shù)的統(tǒng)計(jì)特征，從而得到所求問題的近似值。仿真次數(shù)越多，仿真結(jié)果與實(shí)際情況越相近，蒙特卡洛仿真法的計(jì)算精度越高。因此，本次實(shí)驗(yàn)采用蒙特卡洛仿真實(shí)驗(yàn)結(jié)果證明本文算法的實(shí)用性和可靠性。

在本次蒙特卡洛仿真實(shí)驗(yàn)中，針對多高度層的城市超低空物流場景，隨機(jī)選取各項(xiàng)實(shí)驗(yàn)參數(shù)，并在隨機(jī)選取的參數(shù)中進(jìn)行多次重復(fù)實(shí)驗(yàn)，具體實(shí)驗(yàn)設(shè)置如下：地圖尺寸隨機(jī)取值為20、30、40、50，無人機(jī)起終點(diǎn)在地圖隨機(jī)尺寸內(nèi)；障礙物數(shù)量隨機(jī)比例為6%～20%；無人機(jī)數(shù)量為5～8，無人機(jī)起飛時(shí)間在8:00—10:00隨機(jī)選取，多無人機(jī)避障規(guī)則遵循2.5節(jié)中多無人機(jī)避障規(guī)則；該實(shí)驗(yàn)屬于復(fù)雜仿真實(shí)驗(yàn)，為確保測試結(jié)果的真實(shí)性，進(jìn)行多次實(shí)驗(yàn)并取平均值作為算法性能的統(tǒng)計(jì)結(jié)果，因此，本文設(shè)置1 000次蒙特卡洛仿真實(shí)驗(yàn)，同時(shí)設(shè)置傳統(tǒng)A*算法在相同變量取值規(guī)則情況下的仿真結(jié)果作為對比，對比指標(biāo)分別為：路徑規(guī)劃成功率、算法平均運(yùn)行時(shí)間、距離障礙物距離，仿真實(shí)驗(yàn)對比結(jié)果如表5所示。

在隨機(jī)選取障礙物的過程中，有幾率在起點(diǎn)或終點(diǎn)周圍產(chǎn)生環(huán)形障礙，造成無可行軌跡的情況。因此在表5中，本文提出的面向城市超低空物流場景的最小風(fēng)險(xiǎn)路徑規(guī)劃算法與A*算法的路徑規(guī)劃成功率都不為100%。同時(shí)，依據(jù)2.3節(jié)中將無人機(jī)路徑點(diǎn)與最近障礙物柵格中心的歐幾里得距離作為安全距離，由表5可知，本文算法安全距離較傳統(tǒng)算法有大幅度提升，保證了路徑的安全性。綜上所述，本文提出的方法可以應(yīng)用于多種城市空中交通場景，具有實(shí)用性和可靠性。

表5 仿真實(shí)驗(yàn)對比結(jié)果Table 5 Comparison results of simulation experiments

4 結(jié)論

從無人機(jī)飛行安全性角度出發(fā)，提出了一種面向城市超低空物流場景的最小風(fēng)險(xiǎn)路徑規(guī)劃算法，該算法基于傳統(tǒng)A*算法，優(yōu)化了啟發(fā)函數(shù)的權(quán)重系數(shù)；將三維環(huán)境依據(jù)飛行高度劃分為多個(gè)高度層，結(jié)合劃分空域風(fēng)險(xiǎn)等級思想，構(gòu)建風(fēng)險(xiǎn)等級代價(jià)函數(shù)，以規(guī)劃風(fēng)險(xiǎn)最小軌跡為目標(biāo)，從時(shí)間、風(fēng)險(xiǎn)兩個(gè)維度對A*算法的成本估計(jì)函數(shù)進(jìn)行重構(gòu)，在盡可能避開密集障礙物的同時(shí)飛行距離最短，在無人機(jī)飛行前避開高風(fēng)險(xiǎn)區(qū)域，規(guī)劃得到安全系數(shù)較高的路徑，并應(yīng)用于多無人機(jī)多高度層路徑規(guī)劃中。仿真實(shí)驗(yàn)表明本文優(yōu)化后的A*算法與原算法相比，安全距離平均增加60%，路徑代價(jià)平均僅增加約14%，路徑更加合理；同時(shí)能夠有效解決多無人機(jī)在復(fù)雜場景下路徑規(guī)劃問題，得到安全性較高的多無人機(jī)無沖突路徑；通過蒙特卡洛仿真實(shí)驗(yàn)，對比本文算法與傳統(tǒng)A*算法，證明本文算法具有實(shí)用性和可靠性。

本文高度層劃分方式及障礙物模型為理想化情況，無人機(jī)飛行高度劃分方式還在不斷完善中，并且現(xiàn)實(shí)生活中障礙物形狀多種多樣，還存在動態(tài)障礙物，但以上缺陷并不影響優(yōu)化后算法的可行性。因此，今后研究方向?qū)⒅τ诙酂o人機(jī)協(xié)同路徑規(guī)劃，更好地滿足未來城市超低空物流場景的需求。