城市區(qū)域物流無(wú)人機(jī)路徑規(guī)劃

張洪海，李 翰，劉 皞，許衛(wèi)衛(wèi)，鄒依原

(南京航空航天大學(xué)民航學(xué)院，南京211106)

0 引 言

隨著電商業(yè)務(wù)量的迅速增長(zhǎng)，物流“末端一公里”配送面臨的壓力越來(lái)越大，無(wú)人機(jī)具有速度快、靈活性強(qiáng)的特點(diǎn)，無(wú)人機(jī)物流應(yīng)運(yùn)而生.在抗擊新冠病毒疫情期間，武漢市運(yùn)用物流無(wú)人機(jī)進(jìn)行醫(yī)療物資配送，取得良好效果[1].可以預(yù)見，未來(lái)會(huì)有大量物流無(wú)人機(jī)在城市空域運(yùn)行，因此，研究城市區(qū)域物流無(wú)人機(jī)路徑規(guī)劃方法具有現(xiàn)實(shí)意義.

目前，對(duì)物流無(wú)人機(jī)路徑規(guī)劃研究較少.文獻(xiàn)[2]考慮無(wú)人機(jī)在人道救援方面的應(yīng)用，提出在載荷和能耗約束下無(wú)人機(jī)運(yùn)輸成本最小的優(yōu)化模型；文獻(xiàn)[3]提出無(wú)人機(jī)運(yùn)輸整數(shù)線性規(guī)劃模型并進(jìn)行驗(yàn)證；文獻(xiàn)[4]分析無(wú)人機(jī)物流運(yùn)輸過(guò)程的風(fēng)險(xiǎn)，設(shè)計(jì)配送系統(tǒng)進(jìn)行仿真驗(yàn)證；文獻(xiàn)[5]利用遺傳算法和PSO算法，得出無(wú)人機(jī)在復(fù)雜環(huán)境的最優(yōu)路徑；文獻(xiàn)[6]針對(duì)低空復(fù)雜環(huán)境，提出基于A*蟻群算法的路徑規(guī)劃方法并進(jìn)行驗(yàn)證；文獻(xiàn)[7]考慮低空空域環(huán)境和無(wú)人機(jī)運(yùn)輸任務(wù)等約束，建立多約束路徑規(guī)劃模型并進(jìn)行驗(yàn)證.上述研究考慮的影響要素比較單一，缺乏在城市建筑物密集、規(guī)劃空間復(fù)雜環(huán)境下進(jìn)行路徑規(guī)劃的研究.

本文基于城市三維環(huán)境，考慮無(wú)人機(jī)性能條件，在滿足無(wú)人機(jī)安全的前提下，構(gòu)建航行總代價(jià)最小的無(wú)人機(jī)路徑規(guī)劃模型，設(shè)計(jì)基于柵格法的改進(jìn)A*算法，以獲得最佳配送路徑.

1 問(wèn)題建模

1.1 問(wèn)題描述與假設(shè)

假設(shè)某城市區(qū)域存在物流需求點(diǎn)，位置已知，利用無(wú)人機(jī)從配送中心出發(fā)進(jìn)行物流配送任務(wù).無(wú)人機(jī)為可垂直起降的充電旋翼式無(wú)人機(jī)，存在性能限制，且在其出發(fā)后路徑固定不變，不接受中途指派.為保證將貨物安全快捷地配送到需求點(diǎn)，需要在飛行前進(jìn)行路徑規(guī)劃.

1.2 環(huán)境建模

路徑規(guī)劃首先進(jìn)行環(huán)境建模，采用柵格法表征飛行環(huán)境.設(shè)規(guī)劃空間為OABC-O′A′B′C′的立方體區(qū)域，長(zhǎng)、寬、高分別為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)障礙物，不考慮動(dòng)態(tài)障礙物.傳統(tǒng)賦值方法為0-1賦值法，即柵格存在障礙物賦值為1，否則為0，這種方法區(qū)分度小，容易丟失環(huán)境信息.本文運(yùn)用[0,1]賦值法和柵格危險(xiǎn)度[7]概念，賦值為1 的柵格不會(huì)被擴(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 路徑規(guī)劃模型

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à).

定義無(wú)人機(jī)從S至G的航程代價(jià)為L(zhǎng)，表達(dá)式為

(2)高度代價(jià).

城市環(huán)境特點(diǎn)是建筑物高大且密集.定義無(wú)人機(jī)從S到G的高度代價(jià)為R，表達(dá)式為

式中：k1為無(wú)人機(jī)高度變化懲罰系數(shù)；M為無(wú)人機(jī)總質(zhì)量；g為重力加速度，取值為9.8 m/s2；Δz(i-1,i)為路徑點(diǎn)Ci-1與Ci的高度差.

(3)危險(xiǎn)度代價(jià).

在城市進(jìn)行物流配送必須考慮安全因素.定義無(wú)人機(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)最小路徑段長(zhǎng)度.

相鄰路徑點(diǎn)距離不能小于最小路徑段長(zhǎng)度，約束為

式中：li為各路徑段長(zhǎng)度；lmin為最小路徑段長(zhǎng)度.無(wú)人機(jī)航程為各路徑段長(zhǎng)度之和.

(2)最大航程.

無(wú)人機(jī)配送距離必須小于其最大航程，約束為

式中：Lmax為無(wú)人機(jī)最大航程.

(3)轉(zhuǎn)彎角和俯仰角.

無(wú)人機(jī)進(jìn)行轉(zhuǎn)彎或升降時(shí)，若zi-1=zi，無(wú)人機(jī)進(jìn)行轉(zhuǎn)彎操作，滿足約束

式中：βmax為最大轉(zhuǎn)彎角；βi為無(wú)人機(jī)在路徑點(diǎn)Ci轉(zhuǎn)彎角.

若zi-1≠zi，無(wú)人機(jī)進(jìn)行升降操作，滿足約束

式中：μmax為最大俯仰角；μi為無(wú)人機(jī)在路徑點(diǎn)Ci俯仰角.

(4)飛行高度.

無(wú)人機(jī)飛行高度的限制約束為

式中：Hmax、Hmin分別為最高、最低飛行高度，取決于無(wú)人機(jī)性能和空域政策.

(5)最大貨物載重.

無(wú)人機(jī)載貨上限約束為

式中：q為貨物質(zhì)量；qmax為最大載重；M′為無(wú)人機(jī)空重.

2 改進(jìn)A＊算法

2.1 傳統(tǒng)A＊算法原理

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 改進(jìn)A＊算法設(shè)計(jì)方案

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ù)會(huì)明顯小于實(shí)際航程，而采用曼哈頓距離會(huì)明顯大于實(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)；②若雙向搜索未能相遇，則對(duì)正向和反向搜索的2條路徑進(jìn)行比較，選取較短路徑.

2.2.3 路徑平滑處理

得到關(guān)鍵路徑點(diǎn)組成的線段折角比較明顯，需要進(jìn)行平滑處理.本文采用B 樣條法對(duì)初始路徑進(jìn)行優(yōu)化，B 樣條曲線具有曲率變化均勻的特點(diǎn)，能滿足無(wú)人機(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 中，說(shuō)明雙向搜索相遇，轉(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 中，說(shuō)明雙向搜索相遇，轉(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)路徑；若未相遇，則對(duì)搜索的路徑進(jìn)行比較，選取較短路徑.

Step 5 采用B樣條法對(duì)路徑進(jìn)行平滑處理得到最終路徑，算法結(jié)束.

圖2 算法流程Fig.2 Flow of algorithm

3 仿真與分析

3.1 仿真環(huán)境及參數(shù)設(shè)置

為驗(yàn)證方法的有效性，使用Visual Studio 和Matlab進(jìn)行仿真實(shí)驗(yàn).利用Google Earth獲取香港太古城地理數(shù)據(jù)(地圖分辨率為5 m).采用柵格法進(jìn)行環(huán)境建模，作為無(wú)人機(jī)飛行環(huán)境.因缺乏實(shí)際案例數(shù)據(jù)，參照文獻(xiàn)[7]設(shè)置參數(shù)值，如表1所示.

表1 參數(shù)設(shè)置Table 1 Parameter setting

3.2 仿真結(jié)果分析

仿真實(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é)果對(duì)比Table 2 Comparison of path planning results between traditional algorithm and improved algorithm

圖3 物流無(wú)人機(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)勢(shì)顯著.

為進(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)勢(shì)，符合城市物流無(wú)人機(jī)飛行要求.

表3 迪杰特斯拉算法和改進(jìn)A＊算法路徑規(guī)劃結(jié)果對(duì)比Table 3 Comparison of path planning results between Dijkstra algorithm and improved A＊algorithm

圖4 不同算法路徑規(guī)劃對(duì)比Fig.4 Path planning results of each algorithm

3.3 參數(shù)設(shè)置分析

代價(jià)權(quán)重{α1,α2,α3} 和距離權(quán)重{ω1,ω2} 取值會(huì)對(duì)結(jié)果產(chǎn)生影響，故采用對(duì)照實(shí)驗(yàn)法對(duì)參數(shù)取值進(jìn)行分析.

3.3.1 代價(jià)權(quán)重分析

城市物流配送首先要保證安全，因此，固定危險(xiǎn)度權(quán)重α3=0.5 不變，分析α1、α2取值對(duì)結(jié)果的影響，進(jìn)行21組對(duì)照實(shí)驗(yàn).實(shí)驗(yàn)數(shù)據(jù)如表4所示.

表4 不同代價(jià)權(quán)重對(duì)規(guī)劃結(jié)果的影響Table 4 Influence of different cost weight on path planning results

由表4可知，隨著α1增大，航程呈現(xiàn)先增加后逐漸減少的趨勢(shì)；高度代價(jià)前期比較穩(wěn)定，從實(shí)驗(yàn)18 開始劇烈增加；危險(xiǎn)度表現(xiàn)為先下降后穩(wěn)定的趨勢(shì)；規(guī)劃時(shí)長(zhǎng)在前8 組實(shí)驗(yàn)中波動(dòng)較大，之后較為穩(wěn)定.基于構(gòu)建模型的目標(biāo)函數(shù)并考慮算法時(shí)長(zhǎng)，以實(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的取值對(duì)結(jié)果的影響，進(jìn)行21 組對(duì)照實(shí)驗(yàn).實(shí)驗(yàn)數(shù)據(jù)如表5所示.

表5 不同距離權(quán)重對(duì)規(guī)劃結(jié)果的影響Table 5 Influence of different distance weight on path planning results

由表5可知，隨著ω1增大，航程為先減小后增大的趨勢(shì)；高度代價(jià)和危險(xiǎn)度先保持穩(wěn)定后迅速增加；算法規(guī)劃時(shí)長(zhǎng)在波動(dòng)中有增大趨勢(shì).基于構(gòu)建模型的目標(biāo)函數(shù)并考慮算法規(guī)劃時(shí)長(zhǎng)，以實(shí)驗(yàn)4所得結(jié)果為最佳規(guī)劃路徑，最優(yōu)距離權(quán)重值為：ω1=0.15，ω2=0.85.

3.4 其他環(huán)境驗(yàn)證

為檢驗(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é)果對(duì)比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í)間略長(zhǎng)外，其他數(shù)據(jù)明顯優(yōu)于傳統(tǒng)A*算法.而最佳參數(shù)需要根據(jù)規(guī)劃要求，采用參數(shù)設(shè)置分析方法進(jìn)行分析獲得.

4 結(jié) 論

本文基于柵格法構(gòu)建飛行環(huán)境，設(shè)計(jì)以航程、高度和危險(xiǎn)度代價(jià)最小為目標(biāo)函數(shù)的路徑規(guī)劃模型，有效實(shí)現(xiàn)多目標(biāo)優(yōu)化，貼合無(wú)人機(jī)在城市空域飛行實(shí)際.改進(jìn)算法由歐氏距離和曼哈頓距離的線性組合作為啟發(fā)函數(shù)，采用雙向搜索策略搜索路徑.仿真實(shí)驗(yàn)表明，改進(jìn)算法較傳統(tǒng)算法優(yōu)勢(shì)顯著，說(shuō)明改進(jìn)算法具有合理性.本文方法可用于物流無(wú)人機(jī)路徑規(guī)劃，且規(guī)劃結(jié)果受代價(jià)權(quán)重值、距離權(quán)重值影響.在不同環(huán)境和規(guī)劃要求下，可采用本文參數(shù)設(shè)置分析方法得到最佳參數(shù)值.隨著無(wú)人機(jī)技術(shù)的成熟，物流無(wú)人機(jī)在城市空域大規(guī)模運(yùn)行為期不遠(yuǎn)，今后將會(huì)對(duì)多物流無(wú)人機(jī)協(xié)同路徑規(guī)劃開展研究.