張洪海,李 翰,劉 皞,許衛(wèi)衛(wèi),鄒依原
(南京航空航天大學(xué)民航學(xué)院,南京211106)
隨著電商業(yè)務(wù)量的迅速增長,物流“末端一公里”配送面臨的壓力越來越大,無人機(jī)具有速度快、靈活性強(qiáng)的特點(diǎn),無人機(jī)物流應(yīng)運(yùn)而生.在抗擊新冠病毒疫情期間,武漢市運(yùn)用物流無人機(jī)進(jìn)行醫(yī)療物資配送,取得良好效果[1].可以預(yù)見,未來會有大量物流無人機(jī)在城市空域運(yùn)行,因此,研究城市區(qū)域物流無人機(jī)路徑規(guī)劃方法具有現(xiàn)實(shí)意義.
目前,對物流無人機(jī)路徑規(guī)劃研究較少.文獻(xiàn)[2]考慮無人機(jī)在人道救援方面的應(yīng)用,提出在載荷和能耗約束下無人機(jī)運(yùn)輸成本最小的優(yōu)化模型;文獻(xiàn)[3]提出無人機(jī)運(yùn)輸整數(shù)線性規(guī)劃模型并進(jìn)行驗(yàn)證;文獻(xiàn)[4]分析無人機(jī)物流運(yùn)輸過程的風(fēng)險(xiǎn),設(shè)計(jì)配送系統(tǒng)進(jìn)行仿真驗(yàn)證;文獻(xiàn)[5]利用遺傳算法和PSO算法,得出無人機(jī)在復(fù)雜環(huán)境的最優(yōu)路徑;文獻(xiàn)[6]針對低空復(fù)雜環(huán)境,提出基于A*蟻群算法的路徑規(guī)劃方法并進(jìn)行驗(yàn)證;文獻(xiàn)[7]考慮低空空域環(huán)境和無人機(jī)運(yùn)輸任務(wù)等約束,建立多約束路徑規(guī)劃模型并進(jìn)行驗(yàn)證.上述研究考慮的影響要素比較單一,缺乏在城市建筑物密集、規(guī)劃空間復(fù)雜環(huán)境下進(jìn)行路徑規(guī)劃的研究.
本文基于城市三維環(huán)境,考慮無人機(jī)性能條件,在滿足無人機(jī)安全的前提下,構(gòu)建航行總代價(jià)最小的無人機(jī)路徑規(guī)劃模型,設(shè)計(jì)基于柵格法的改進(jìn)A*算法,以獲得最佳配送路徑.
假設(shè)某城市區(qū)域存在物流需求點(diǎn),位置已知,利用無人機(jī)從配送中心出發(fā)進(jìn)行物流配送任務(wù).無人機(jī)為可垂直起降的充電旋翼式無人機(jī),存在性能限制,且在其出發(fā)后路徑固定不變,不接受中途指派.為保證將貨物安全快捷地配送到需求點(diǎn),需要在飛行前進(jìn)行路徑規(guī)劃.
路徑規(guī)劃首先進(jìn)行環(huán)境建模,采用柵格法表征飛行環(huán)境.設(shè)規(guī)劃空間為OABC-O′A′B′C′的立方體區(qū)域,長、寬、高分別為Q、W、E,以O(shè)為原點(diǎn)建立3維直角坐標(biāo)系.根據(jù)柵格大小lgrid,將規(guī)劃空間劃分為u×v×w個(gè)立體柵格,每個(gè)柵格的中心點(diǎn)作為待選路徑點(diǎn),其中,u=int(Q/lgrid),v=int(W/lgrid),w=int(E/lgrid),int()為取整函數(shù).lgrid由地圖分辨率和計(jì)算機(jī)性能決定.柵格法環(huán)境建模示意如圖1所示,其中,灰色網(wǎng)格線將空域環(huán)境劃分為一個(gè)個(gè)柵格,曲線表示在柵格中的飛行路徑.
本文規(guī)劃空間中所考慮障礙物為城市建筑物等靜態(tài)障礙物,不考慮動態(tài)障礙物.傳統(tǒng)賦值方法為0-1賦值法,即柵格存在障礙物賦值為1,否則為0,這種方法區(qū)分度小,容易丟失環(huán)境信息.本文運(yùn)用[0,1]賦值法和柵格危險(xiǎn)度[7]概念,賦值為1 的柵格不會被擴(kuò)展為路徑點(diǎn),其他柵格可能被擴(kuò)展但存在明顯的危險(xiǎn)度差異.柵格i的危險(xiǎn)度di為
式中:Nobstacle(i)為柵格i周圍障礙物數(shù)量;Nsurround(i)為柵格i周圍柵格總數(shù).
圖1 柵格法環(huán)境建模示意Fig.1 Schematic diagram of grid environment modeling
1.3.1 目標(biāo)函數(shù)
設(shè)起始點(diǎn)S坐標(biāo)為(x0,y0,z0),目標(biāo)點(diǎn)G坐標(biāo)為(xn,yn,zn),途經(jīng)路徑點(diǎn)Ci的坐標(biāo)為(xi,yi,zi),其中i∈(1,2,…,n-1).考慮代價(jià)如下.
(1)航程代價(jià).
定義無人機(jī)從S至G的航程代價(jià)為L,表達(dá)式為
(2)高度代價(jià).
城市環(huán)境特點(diǎn)是建筑物高大且密集.定義無人機(jī)從S到G的高度代價(jià)為R,表達(dá)式為
式中:k1為無人機(jī)高度變化懲罰系數(shù);M為無人機(jī)總質(zhì)量;g為重力加速度,取值為9.8 m/s2;Δz(i-1,i)為路徑點(diǎn)Ci-1與Ci的高度差.
(3)危險(xiǎn)度代價(jià).
在城市進(jìn)行物流配送必須考慮安全因素.定義無人機(jī)從S到G的危險(xiǎn)度代價(jià)為D,表達(dá)式為
式中:k2為危險(xiǎn)度懲罰系數(shù).
綜上,模型目標(biāo)函數(shù)J為
式中:α1、α2、α3分別為航程、高度和危險(xiǎn)度代價(jià)的權(quán)重系數(shù),滿足:α1+α2+α3=1.
1.3.2 約束條件
(1)最小路徑段長度.
相鄰路徑點(diǎn)距離不能小于最小路徑段長度,約束為
式中:li為各路徑段長度;lmin為最小路徑段長度.無人機(jī)航程為各路徑段長度之和.
(2)最大航程.
無人機(jī)配送距離必須小于其最大航程,約束為
式中:Lmax為無人機(jī)最大航程.
(3)轉(zhuǎn)彎角和俯仰角.
無人機(jī)進(jìn)行轉(zhuǎn)彎或升降時(shí),若zi-1=zi,無人機(jī)進(jìn)行轉(zhuǎn)彎操作,滿足約束
式中:βmax為最大轉(zhuǎn)彎角;βi為無人機(jī)在路徑點(diǎn)Ci轉(zhuǎn)彎角.
若zi-1≠zi,無人機(jī)進(jìn)行升降操作,滿足約束
式中:μmax為最大俯仰角;μi為無人機(jī)在路徑點(diǎn)Ci俯仰角.
(4)飛行高度.
無人機(jī)飛行高度的限制約束為
式中:Hmax、Hmin分別為最高、最低飛行高度,取決于無人機(jī)性能和空域政策.
(5)最大貨物載重.
無人機(jī)載貨上限約束為
式中:q為貨物質(zhì)量;qmax為最大載重;M′為無人機(jī)空重.
A*算法是常用的啟發(fā)式算法,表達(dá)式為
式中:g(x)為起始點(diǎn)S至擴(kuò)展路徑點(diǎn)Cx的實(shí)際航程代價(jià),稱為實(shí)際代價(jià)函數(shù);h(x)為擴(kuò)展路徑點(diǎn)Cx至目標(biāo)點(diǎn)G的預(yù)估航程代價(jià),稱為啟發(fā)函數(shù).
2.2.1 估價(jià)函數(shù)
(1)實(shí)際代價(jià)函數(shù).
實(shí)際代價(jià)函數(shù)g(x)參照目標(biāo)函數(shù)式(5),為
(2)啟發(fā)函數(shù).
合理的啟發(fā)函數(shù)h(x)能有效提高搜索質(zhì)量.傳統(tǒng)啟發(fā)函數(shù)采用單一航程計(jì)算方法,在有障礙物的環(huán)境中,采用歐氏距離作為啟發(fā)函數(shù)會明顯小于實(shí)際航程,而采用曼哈頓距離會明顯大于實(shí)際航程,故本文采用歐氏距離和曼哈頓距離線性組合作為啟發(fā)函數(shù),表達(dá)式為
式中:ω1、ω2分別是歐氏距離、曼哈頓距離的權(quán)重系數(shù),ω1+ω2=1.
2.2.2 雙向搜索策略
為提高算法求解速度,本文采用雙向搜索策略.設(shè)f1(x)=g1(x)+h1(x)和f2(x)=g2(x)+h2(x)分別為正向搜索和反向搜索的估價(jià)函數(shù).首先,進(jìn)行正向搜索,生成下一路徑點(diǎn)后切換至反向搜索,反向搜索生成下一路徑點(diǎn)后切換至正向搜索,如此交替進(jìn)行.滿足以下條件之一則停止搜索:①雙向搜索在m點(diǎn)相遇,即在正向和反向搜索均搜索到某個(gè)路徑點(diǎn)m,且被標(biāo)記為代價(jià)值最小的路徑點(diǎn);②若雙向搜索未能相遇,則對正向和反向搜索的2條路徑進(jìn)行比較,選取較短路徑.
2.2.3 路徑平滑處理
得到關(guān)鍵路徑點(diǎn)組成的線段折角比較明顯,需要進(jìn)行平滑處理.本文采用B 樣條法對初始路徑進(jìn)行優(yōu)化,B 樣條曲線具有曲率變化均勻的特點(diǎn),能滿足無人機(jī)飛行要求[8].
2.2.4 算法流程
算法流程如圖2所示.具體步驟如下.
Step 1 獲取起始點(diǎn)S和目標(biāo)點(diǎn)G坐標(biāo),計(jì)算每個(gè)柵格的危險(xiǎn)度.
Step 2 分別建立OPEN1、CLOSE1、OPEN2、CLOSE2列表,將S所在柵格加入OPEN1,將G所在柵格加入OPEN2.
Step 3 循環(huán)執(zhí)行下述步驟.
Step 3.1 彈出OPEN1 和OPEN2 中代價(jià)值最小的正向路徑點(diǎn)R和反向路徑點(diǎn)T,把它們分別從OPEN1 和OPEN2 中刪除,并分別放入CLOSE1和CLOSE2中.
Step 3.2 進(jìn)行正向搜索,判斷路徑點(diǎn)R周圍路徑點(diǎn)R′.若為路徑點(diǎn)G,則轉(zhuǎn)向Step 4;否則,進(jìn)行如下判斷.
Step 3.2.1 若路徑點(diǎn)R′在CLOSE2 中,說明雙向搜索相遇,轉(zhuǎn)向Step 4;否則,進(jìn)入Step 3.3.2.
Step 3.2.2 計(jì)算f1(x),將拓展的子節(jié)點(diǎn)按順序存入OPEN1.
Step 3.3 進(jìn)行反向搜索,判斷路徑點(diǎn)T周圍路徑點(diǎn)T′.若為路徑點(diǎn)S,則轉(zhuǎn)向Step 5;否則,進(jìn)行如下判斷.
Step 3.3.1 若路徑點(diǎn)T′在CLOSE1 中,說明雙向搜索相遇,轉(zhuǎn)向Step 5;否則,進(jìn)入Step 3.3.2.
Step 3.3.2 計(jì)算f2(x),將拓展的子節(jié)點(diǎn)按順序存入OPEN2.
Step 3.4 若OPEN1 或OPEN2 為空,則終止循環(huán),進(jìn)入Step 4;否則,返回Step 3.1.
Step 4 若為相遇,則從相遇點(diǎn)開始分別沿正向搜索和反向搜索的父節(jié)點(diǎn)上溯至各自起點(diǎn),得到最優(yōu)路徑;若未相遇,則對搜索的路徑進(jìn)行比較,選取較短路徑.
Step 5 采用B樣條法對路徑進(jìn)行平滑處理得到最終路徑,算法結(jié)束.
圖2 算法流程Fig.2 Flow of algorithm
為驗(yàn)證方法的有效性,使用Visual Studio 和Matlab進(jìn)行仿真實(shí)驗(yàn).利用Google Earth獲取香港太古城地理數(shù)據(jù)(地圖分辨率為5 m).采用柵格法進(jìn)行環(huán)境建模,作為無人機(jī)飛行環(huán)境.因缺乏實(shí)際案例數(shù)據(jù),參照文獻(xiàn)[7]設(shè)置參數(shù)值,如表1所示.
表1 參數(shù)設(shè)置Table 1 Parameter setting
仿真實(shí)驗(yàn)得到傳統(tǒng)A*算法和改進(jìn)A*算法路徑規(guī)劃,實(shí)驗(yàn)數(shù)據(jù)如表2所示,結(jié)果如圖3所示.
表2 傳統(tǒng)和改進(jìn)算法路徑規(guī)劃結(jié)果對比Table 2 Comparison of path planning results between traditional algorithm and improved algorithm
圖3 物流無人機(jī)路徑規(guī)劃結(jié)果Fig.3 Results of logistics UAV's path planning
由表2和圖3可知:2 種算法均能完成路徑規(guī)劃任務(wù),改進(jìn)算法的各項(xiàng)數(shù)據(jù)優(yōu)于傳統(tǒng)算法,尤其是高度代價(jià)比傳統(tǒng)算法減少76.2%,優(yōu)勢顯著.
為進(jìn)一步分析算法性能,采用迪杰特斯拉算法進(jìn)行路徑規(guī)劃,實(shí)驗(yàn)數(shù)據(jù)如表3所示,各算法規(guī)劃結(jié)果如圖4所示.
由表3可知,改進(jìn)A*算法明顯優(yōu)于迪杰特斯拉算法,特別是高度代價(jià)和規(guī)劃時(shí)間分別減少83.9%和98.7%.由圖4可知,相較于其他算法,改進(jìn)A*算法規(guī)劃路徑高度變化少,飛行穩(wěn)定.因此,與傳統(tǒng)A*算法和迪杰特斯拉算法相比,改進(jìn)A*算法具有航程短,路徑點(diǎn)少,高度變化少,求解速度快等優(yōu)勢,符合城市物流無人機(jī)飛行要求.
表3 迪杰特斯拉算法和改進(jìn)A*算法路徑規(guī)劃結(jié)果對比Table 3 Comparison of path planning results between Dijkstra algorithm and improved A*algorithm
圖4 不同算法路徑規(guī)劃對比Fig.4 Path planning results of each algorithm
代價(jià)權(quán)重{α1,α2,α3} 和距離權(quán)重{ω1,ω2} 取值會對結(jié)果產(chǎn)生影響,故采用對照實(shí)驗(yàn)法對參數(shù)取值進(jìn)行分析.
3.3.1 代價(jià)權(quán)重分析
城市物流配送首先要保證安全,因此,固定危險(xiǎn)度權(quán)重α3=0.5 不變,分析α1、α2取值對結(jié)果的影響,進(jìn)行21組對照實(shí)驗(yàn).實(shí)驗(yàn)數(shù)據(jù)如表4所示.
表4 不同代價(jià)權(quán)重對規(guī)劃結(jié)果的影響Table 4 Influence of different cost weight on path planning results
由表4可知,隨著α1增大,航程呈現(xiàn)先增加后逐漸減少的趨勢;高度代價(jià)前期比較穩(wěn)定,從實(shí)驗(yàn)18 開始劇烈增加;危險(xiǎn)度表現(xiàn)為先下降后穩(wěn)定的趨勢;規(guī)劃時(shí)長在前8 組實(shí)驗(yàn)中波動較大,之后較為穩(wěn)定.基于構(gòu)建模型的目標(biāo)函數(shù)并考慮算法時(shí)長,以實(shí)驗(yàn)17 所得結(jié)果為最佳,最優(yōu)代價(jià)權(quán)重值為:α1=0.4,α2=0.1,α3=0.5.
3.3.2 距離權(quán)重分析
固定最優(yōu)代價(jià)權(quán)重值不變,分析距離權(quán)重ω1、ω2的取值對結(jié)果的影響,進(jìn)行21 組對照實(shí)驗(yàn).實(shí)驗(yàn)數(shù)據(jù)如表5所示.
表5 不同距離權(quán)重對規(guī)劃結(jié)果的影響Table 5 Influence of different distance weight on path planning results
由表5可知,隨著ω1增大,航程為先減小后增大的趨勢;高度代價(jià)和危險(xiǎn)度先保持穩(wěn)定后迅速增加;算法規(guī)劃時(shí)長在波動中有增大趨勢.基于構(gòu)建模型的目標(biāo)函數(shù)并考慮算法規(guī)劃時(shí)長,以實(shí)驗(yàn)4所得結(jié)果為最佳規(guī)劃路徑,最優(yōu)距離權(quán)重值為:ω1=0.15,ω2=0.85.
為檢驗(yàn)在其他環(huán)境下的性能,采用墨爾本地理數(shù)據(jù)進(jìn)行仿真驗(yàn)證.起始點(diǎn)S坐標(biāo)為(20,20,10),目標(biāo)點(diǎn)G坐標(biāo)為(230,230,8),其他參數(shù)保持不變,所得傳統(tǒng)A*算法和改進(jìn)A*算法路徑規(guī)劃,實(shí)驗(yàn)數(shù)據(jù)如表6所示,結(jié)果如圖5所示.
表6 2 種算法路徑規(guī)劃結(jié)果對比Table 6 Comparison of path planning results of two algorithms
圖5 其他環(huán)境下路徑規(guī)劃結(jié)果Fig.5 Path planning results in other environments
由表6和圖5可知,在不同環(huán)境下本文算法依然有良好性能,除規(guī)劃時(shí)間略長外,其他數(shù)據(jù)明顯優(yōu)于傳統(tǒng)A*算法.而最佳參數(shù)需要根據(jù)規(guī)劃要求,采用參數(shù)設(shè)置分析方法進(jìn)行分析獲得.
本文基于柵格法構(gòu)建飛行環(huán)境,設(shè)計(jì)以航程、高度和危險(xiǎn)度代價(jià)最小為目標(biāo)函數(shù)的路徑規(guī)劃模型,有效實(shí)現(xiàn)多目標(biāo)優(yōu)化,貼合無人機(jī)在城市空域飛行實(shí)際.改進(jìn)算法由歐氏距離和曼哈頓距離的線性組合作為啟發(fā)函數(shù),采用雙向搜索策略搜索路徑.仿真實(shí)驗(yàn)表明,改進(jìn)算法較傳統(tǒng)算法優(yōu)勢顯著,說明改進(jìn)算法具有合理性.本文方法可用于物流無人機(jī)路徑規(guī)劃,且規(guī)劃結(jié)果受代價(jià)權(quán)重值、距離權(quán)重值影響.在不同環(huán)境和規(guī)劃要求下,可采用本文參數(shù)設(shè)置分析方法得到最佳參數(shù)值.隨著無人機(jī)技術(shù)的成熟,物流無人機(jī)在城市空域大規(guī)模運(yùn)行為期不遠(yuǎn),今后將會對多物流無人機(jī)協(xié)同路徑規(guī)劃開展研究.