復雜低空物流無人機路徑規劃

張啟錢，許衛衛，張洪海，鄒依原，陳雨童

（南京航空航天大學 民航學院，南京211106）

無人機作為科技創新的重要產業處于井噴式發展時期。由于技術日臻成熟，各型別無人機應用領域不斷擴大，如軍事偵查、農林生產、物流運輸［1］。雖然其在物流領域的應用處于起步階段，但各國進行了前沿性研究且成功案例較多。國內外學者對軍用無人機研究深入［2-3］，涉及民用無人機則較少，且主要對巡檢、藥物噴灑等路徑進行規劃［4-5］。國內學者研究物流無人機管控居多［6］，國外學者則關注其路徑規劃，解決如何將貨物送至多個分快遞站問題［7-8］，但卻很少研究分站點間具體運輸的路徑。實際應用中，物流無人機自身及環境復雜，其路徑是貨物安全、經濟、快捷送至目的地的重要保障，可降低運營成本、提升流轉效率，故研究物流無人機路徑規劃技術有重要現實意義。

現有對復雜低空物流無人機路徑規劃的研究較少。Byung等［7］融合無人機物流系統飛行時間有限、貨物對性能影響大等特點，提出基于混合整數線性規劃的無人機運輸路徑模型，設計啟發式算法解算路徑；Boualem等［8］考慮無人機在人道救援物流方面的應用，提出在載荷和能耗約束下無人機運輸物品總成本最小的優化模型；Scott等［9］驗證了無人機運輸醫療物資可行性，提出2個面向醫療服務的無人機物流配送模型；周浪 提出“配送車+無人機”配送及路徑優化問題，構建了不同運輸路徑優化模型，采用遺傳算法等求解模型；翁丹寧［11］、吳永鑫［12］探討無人機物流配送的短板及未廣泛用于市場的原因，分析物流無人機的優勢并研究了影響其配送的因素；Jiang等［13］考慮無人機性能建立帶時間窗的無人機物流任務分配模型，設計改進粒子群算法進行求解；Dorling等［14］推導并證明多旋翼無人機能耗與載荷呈線性變化，建立無人機路徑規劃的混合整數線性模型；Torabbeigi等［15］構建并驗證無人機電量消耗率隨載重的變化函數，采用最小集覆蓋法對物流無人機路徑規劃進行建模，提出一種變預處理算法以提高求解模型的速度；Goss等［16］建立考慮無人機物理特性和執飛任務特點的無人機性能模型，采用四旋翼無人機測試并驗證模型的正確性；Abeywickrama等［17］研究無人機機動行為的電量消耗，考慮不同場景及條件對無人機能耗的影響，提出涵蓋無人機飛行全過程的能耗模型。

縱觀已有成果，部分將物流無人機路徑規劃問題簡化為道路車輛路徑規劃問題，未體現無人機空中運動特點及性能約束［12-15］；部分在規劃物流無人機路徑時未考慮實際飛行環境且未將任務要求、能耗、貨物質量等影響要素組合考慮，規劃結果不理想［7-8，10］?，F有研究面向飛行行為、宏觀路徑規劃，考慮的路徑影響要素單一有限；而低空環境下物流無人機路徑規劃空間復雜，路徑搜索需結合外部環境與自身限制，且對搜索效率要求高。同時物流無人機路徑規劃與執行其他任務的路徑規劃不同，其航空物流特點導致規劃考慮的因素更全面、具體，如何將這些因素綜合考慮以進行路徑規劃亟待研究。

本文從物流無人機飛行安全和運輸效率角度出發，以最小化路徑飛行時間、能耗及危險度作為目標函數，構建在滿足無人機運輸貨物過程中自主安全避障的前提下，減小運行成本的物流無人機路徑規劃模型，設計基于A*算法的路徑快速搜索策略，以獲得最佳的貨物配送路徑。

1 物流無人機路徑規劃問題建模

1.1 問題描述與相關假設

某區域有多個分快遞站且都配備物流無人機，利用無人機完成快遞站間貨物運輸任務。假設物流無人機均為可垂直起降的充電旋翼式無人機，且對貨物載重、能耗等有限制。為確保貨物安全快捷運輸至分快遞站，要求對其路徑進行科學規劃以降低運輸風險及成本。已知物流無人機有2種運輸模式：①每次為單個分快遞站（即目的派送點）提供服務后返回配送中心（即起始派送點）；②為多個分快遞站提供服務后再返回配送中心。本文采取第1種模式研究單架物流無人機從起始派送點到目的派送點運輸代價最小的安全避障路徑規劃技術。

1.2 飛行環境建模

常采用函數模擬法和地形高程數據對地形地物建模。前者通過解析公式對實際地形進行計算機模擬，如文獻［18］中的函數，但該方法太過理想化，利用函數產生的地形與真實地形存在差距，這對于以安全為主的物流運輸場景不適用；后者通過對已有地理信息數據進行插值處理獲得逼近真實環境的地形。除避開地形地物外，各地政府部門對無人機的活動范圍也進行限定，規定了一系列無人機禁飛區、限飛區和危險區等［19］。

1.3 柵格法規劃環境表征

柵格法將環境劃分為單元格，依據其中是否存在障礙物分類：若存在地形地物等障礙，則為障礙柵格并賦值1；否則，為自由柵格并賦值0。采用柵格法擴展路徑點需考慮柵格粒度大小設置，即柵格邊長。柵格粒度過大導致規劃的路徑偏離理論最優解，過小則導致規劃時計算量大。由于柵格中心點是物流無人機飛行路徑點且路徑需滿足無人機性能約束，因此柵格粒度大小需和性能限制匹配。

設運輸任務規劃環境是長、寬、高分別為x、y、z的長方體區域，記為OABC-O′A′B′C′，以O為原點建立三維直角坐標系。其中，OA長度為x，AA′長度為y，OC長度為z。考慮環境信息及物流無人機性能確定柵格粒度大小l。按以下2步確定柵格坐標。

步驟1 對OABC-O′A′B′C′沿OO′進行m等分，過等分點作平行于OABC面的平面，得m-1個平面γj（j＝1，2，…，m）。其中，m ＝int（y／l），int（）為取整函數。

步驟2 對上述任一平面γj，沿OA進行u等分，沿OC進行h等分。其中u＝int（x／l），h＝int（z／l）。此時γj便離散成u×h個平面柵格，OABC-O′A′B′C′被離散成m×u×h個立體柵格，則物流無人機待擴展路徑點可標記為p（i，j，k），i＝1，2，…，m，j＝1，2，…，u，k＝1，2，…，h。

圖1為規劃環境柵格化示意圖。

圖1 規劃環境柵格化Fig.1 Grid of planning environment

1.4 多限制條件物流無人機路徑規劃模型

物流無人機貨物運輸需考慮多方面影響要素，本文綜合考慮物流無人機性能約束與任務要求，從運輸的安全性、經濟性和快捷性等角度建立多限制條件物流無人機路徑規劃模型。

1.4.1 性能約束

1）最遠航程、最小路徑段長度

物流無人機路徑中相鄰兩飛行路徑點間距離不能小于最小路徑段長度，約束為

式中：tfly、D分別為飛行時間、路徑危險度；a1、a2、a3分別為飛行時間、能耗、危險度的系數；T為完成任務可用總時間；t1為起始派送點起飛時刻；t2為到達目的派送點最晚時刻。

式（8）為目標函數；式（9）中前7個式子為物流無人機性能約束；最后一個式子為物流無人機貨物運輸任務約束，表示物流無人機應在規定時間內完成任務。

2 算法設計

2.1 A*算法原理及流程

A*算法通過估計代價函數f（n）選擇待擴展路徑點n，通常考慮的代價是航程，即要求獲得飛行總航程最短的路徑，表達式為

式中：g（n）為起始派送點S至待擴展路徑點n的實際飛行航程，稱為實際代價函數；h（n）為待擴展路徑點n至目的派送點G的預估飛行航程，稱為啟發式函數。

A*算法的原理及實施流程參見文獻［20］，本文不再贅述。

2.2 算法設計方案

直接套用A*算法求解上述模型時存在以下問題：①函數g（n）及h（n）僅計算航程，卻沒考慮能耗、飛行時間等因素，不符合實際應用；②忽略自由柵格位置的差異而同等看待，低空環境及障礙物對路徑點選擇的影響未體現；③未考慮無人機物理性能、機動行為對路徑代價的影響；④函數f（n）未體現無人機貨物載重；⑤待擴展路徑點時前期和后期的效率、精度不匹配；⑥規劃的路徑存在冗余路徑點且不平滑。

為適用本文模型，采用以下方案設計求解算法：①物流無人機飛行航程相比于車輛運輸距離已大大縮短，因此航程不是計算的重點。物流無人機飛行由電池供電且目的派送點接收貨物有時間限制，所以對飛行時間及能耗等代價進行考慮。此外，爬升時高度差導致的能耗與平飛相同距離能耗不同［16］，故不同操作的成本代價也應分開計算。②低空安全飛行是物流無人機運輸貨物的首要目標，為有效躲避地形地物、惡劣氣象等障礙，定義柵格危險度因子概念，用新方式對數字柵格環境存儲，并在g（n）中新增柵格危險度因子以確保擴展更安全、穩定的路徑點。③考慮所載貨物對物流無人機性能、路徑有影響，定義貨物質量懲罰系數，對飛行時間、能耗等代價進行懲罰。④h（n）采用執行任務時間和電量表示，將其表達為從當前路徑點預計到達目的派送點的時間和能耗與剩余可飛時間和電量的差值，該值大小反映完成運輸任務成本的高低。⑤A*算法中，當待擴展路徑點靠近目的派送點時h（n）變小，導致其在f（n）中所占比例減小，啟發效率降低，此時可對h（n）適當增加比重，但這導致前期搜索范圍小而無法搜索最優路徑。因此，設計動態權重系數對g（n）和h（n）加權以權衡算法搜索效率和精度。⑥為篩除原路徑中冗余路徑點，采用雙向交叉判斷法對路徑點對連線構成的路徑段和障礙物進行相交檢測以獲得精簡路徑，并利用樣條曲線插值對精簡路徑處理得到物流無人機連續平滑路徑。

2.3 具體設計

2.3.1 新增柵格危險度因子

A*算法利用0-1矩陣對柵格環境存儲，這將自由柵格同等看待，在搜索路徑點時這些區域被選中的概率相等，導致搜索的路徑安全性差。實際情況中，雖然某些柵格不對物流無人機造成危害，但由于柵格所處位置不同造成無人機在不同柵格中飛行所受危險度有差異。本文對原標記為1的柵格不做改變，而對標記為0的柵格將其值重新標為危險度因子。定義柵格危險度因子來衡量路徑點周圍環境對該點的危險程度，公式如下：

式中：d為柵格危險度因子；Nobstacle為該柵格周圍障礙柵格數；Nsurround為周圍總柵格數。

本文稱對自由柵格差異化而非同一化處理的方法為非二值存儲法，此法能保留原始威脅信息。圖2為柵格危險度因子計算示意圖，黑、白柵格分別代表障礙柵格和自由柵格。式（12）為A*算法0-1矩陣存儲結果，式（13）為非二值存儲法存儲結果。

圖2 柵格危險度因子計算Fig.2 Calculation of grid risk

2.3.2 添加貨物質量懲罰系數

物流無人機不同機動行為對能耗是不同的［16］，所以函數g（n）將水平和升降運動能耗分開計算且不考慮起降能耗。假設物流無人機水平運動能耗為距離的λ倍，垂直運動能耗為高度差的r倍，g（n）表達式為

2.3.5 路徑優化及平滑

路徑轉彎多表明物流無人機姿態改變次數多，利用雙向交叉判斷法篩除冗余路徑點可減少路徑點數，其思想是：當原路徑中不相鄰兩路徑點間連線構成的路徑段不與障礙物交叉時，可剔除該兩點間的冗余路徑點。假設采用本文算法搜索的原路徑為Path，按如下步驟對該路徑進行優化，操作示例如圖3所示。

步驟1 創建新列表DELETE。

步驟2 對Path中路徑點按其高度劃分為多段子路徑Path＝｛subpath1，subpath2，…｝，任一子路徑可表示為subpathi＝｛p1，p2，…，pe｝，e為該段路徑點總個數。

步驟3 對subpath中滿足e＞2條件的任一子路徑進行操作：①共需進行q輪判斷，其中q＝e-2，并令i＝1；②若i≤q，則跳至步驟4判斷點pj與pj+e-i是否位于DELETE中（j＝1，2，…，i），若i＞q，跳至步驟6。

步驟4 對上述每一路徑點判斷其是否位于DELETE列表中。若路徑點pj與pj+e-i均不在DELETE中，則跳至步驟5。

步驟5 若路徑點對間連線與障礙物不交叉，則該兩點可直接連接，并將原段中兩點間的其余點移入DELETE，第i輪中路徑點對全判斷完后跳至步驟3中的②，令i＝i+1。

步驟6 對其余子路徑循環執行步驟3～步驟5，直至所有路徑點全判斷完畢。

步驟7 將位于DELETE的路徑點在原Path中篩除，剩余路徑點序列構成的路徑即為精簡路徑。

圖3 雙向交叉判斷法Fig.3 Bidirectional cross judgmentmethod

利用雙向交叉判斷法得到的精簡路徑為一條折線飛行路徑，但在復雜低空中物流無人機從起始派送點至目的派送點的路徑應是連續的，故對路徑再進行平滑處理。采用B樣條曲線對精簡路徑插值擬合獲得可飛的連續平滑路徑，具體流程見文獻［21］。

2.4 算法實現

本文算法規劃物流無人機路徑的流程如圖4所示，步驟如下：

步驟1 獲得物流無人機機動性能約束，起始派送點和目的派送點坐標，貨物質量懲罰系數τ（Q）。

圖4 本文算法流程Fig.4 Flowchart of proposed algorithm

步驟2 依據運輸場景地圖確定柵格粒度大小，采用非二值存儲法生成柵格危險度因子矩陣。

步驟3 建立OPEN、CLOSE列表，將起始派送點所在柵格加入OPEN列表，將障礙柵格加入CLOSE列表。

步驟4 循環執行：

4.1 搜索前一路徑點周圍柵格危險度因子不為1的路徑點并放入OPEN列表，計算其gQ（n）、hQ（n）、W（n）、W′（n）和fQ（n）值，選擇其中fQ（n）值最小的點為當前正擴展路徑點并記作A。

4.2 將A點移入CLOSE列表。

4.3 判斷A點周圍的路徑點，若其危險度為1則跳過該點，否則記該點為B并求gQ（B）、hQ（B）、W（B）、W′（B）和fQ（B）值，進 行 以 下判斷：

4.3.1 若B點已在OPEN列表，則確定B點的最優父節點。記對原先B點求得的估計成本值為fQ（B′），若fQ（B）＜fQ（B′），B點的父節點為A點；否則B點的父節點不變。

4.3.2 若B點已在CLOSE列表，則跳過B點。

4.3.3 若B點既不在OPEN列表也不在CLOSE列表，則將B 點移入OPEN 列表并在OPEN列表中對估計成本值的大小按升序排序，選出fQ（n）值最小的點為下一路徑點。

步驟5 當路徑點到達目的派送點所在柵格或未擴展到目的派送點但OPEN列表為空時搜索結束，終止步驟4。

步驟6 從目的派送點通過各路徑點的父節點反向移動回到起始派送點，便得物流無人機路徑，并采用雙向交叉判斷法及樣條曲線插值對該路徑進行優化平滑。

3 仿真驗證及分析

3.1 仿真環境及參數設置

為驗證本文算法規劃物流無人機路徑的有效性，利用Google獲取某區域1 300 m×1 300 m×310m的地形高程數據，并將該區域作為此次物流無人機路徑規劃環境，部分數據見表1，其中，第2行第2列表示（0，0）點處地形高程值（此處為34.52m），相鄰單元格間的距離為5 m，即第i行第j列單元格中數據代表坐標（5（i-1），5（j-1））處的高程值。采用MATLAB將此環境以圖形化展示，如圖5所示。由于目前直接面向顧客的無人機末端配送技術不成熟及相應基礎設施建設不完備，本文規劃的物流無人機路徑僅用于兩貨物存儲倉庫間。為盡量真實模擬物流無人機最優飛行路徑產生的過程，仿真實驗具體參數按表2進行設置。

表1 環境數據Tab le 1 Environm en tal data

圖5 物流無人機路徑規劃環境Fig.5 Environment for path planning of logistics UAV

表2 仿真參數Table 2 Sim ulation param eters

3.2 仿真結果分析

采用本文算法及表2中參數設置得到物流無人機路徑規劃結果，如圖6中綠色曲線所示?？芍?，該物流無人機安全平滑地從起始派送點飛行至目的派送點，且有效地對低空環境中的障礙物進行避讓。為對比本文算法與A*算法規劃性能的優劣，在上述各參數設置、路徑規劃環境保持不變的前提下，對該物流無人機路徑利用A*算法進行規劃，結果如圖6中紅色曲線所示，并從飛行路徑的路徑點數、航程、能耗等方面進行分析，數據如表3所示?？梢钥闯?，本文算法的各指標數據均優于A*算法，且路徑點數變化率最大，降低了42.9%，表明雙向交叉判斷法可有效減小路徑點數，降低物流無人機姿態改變次數，保證了貨物運輸安全。

為進一步分析本文算法的規劃性能，再采用人工勢場法、未優化及平滑的改進算法對物流無人機的路徑進行規劃，各算法規劃結果如圖7所示（為便于觀察，圖中僅展示各路徑），并將對比結果記錄于表4。由圖7知，在圖7（a）中，各算法均可規劃出路徑，但A*算法及人工勢場法規劃的路徑高度變換次數多，且人工勢場法陷于局部最優；在圖7（b）中，未優化及平滑的改進算法規劃的路徑存在冗余路徑點且不平滑。再結合表3、表4分析，人工勢場法在復雜環境下陷入局部最優解，故規劃時間、路徑點數、路徑航程分別為本文算法的6.5、1.6、1.2倍；A*算法未考慮物流無人機貨物運輸要求導致其路徑長、能耗多，飛行時間約為本文算法的1.1倍；未優化及平滑的改進算法在規劃時間上比本文算法短，原因在于雙向交叉判斷法、樣條曲線插值都具有一定時間復雜度，但其路徑點數、路徑航程、危險度均比本文算法高，故規劃時間變長屬可接受范圍。

圖6 物流無人機路徑規劃結果Fig.6 Path planning results of logistics UAV

表3 A*算法和本文算法路徑規劃結果對比Tab le 3 Com parison of path p lanning resu lts betw een A* algorithm and proposed algorithm

通過以上分析得，本文算法路徑規劃結果在路徑航程、能耗、危險度等方面都優于A*算法及人工勢場法；物流無人機路徑規劃模型可優化無人機的貨物運輸時間和路徑搜索結果，實現時間上飛行時間減少、空間上安全平滑避障，進而及時低風險地完成任務，這也表明引入柵格危險度因子、動態賦權估計成本函數等改進的合理性。

圖7 不同算法路徑規劃結果Fig.7 Path planning results of different algorithms

表4 不同算法路徑規劃結果對比Tab le 4 Com parison of path p lanning resu lts am ong different algorithm s

3.3 算法參數分析

在求解物流無人機路徑規劃模型時，柵格粒度大小l和代價權重值組合｛α1，α2，α3｝會對模型解算結果產生影響。本文采用對照實驗法分析參數l和｛α1，α2，α3｝的取值對路徑規劃結果的影響。

保持代價權重值組合如表2中設置不變，柵格粒度大小l分別取5、10、15、20m，在其他參數設置及規劃環境相同的條件下進行多組對照實驗，對各組實驗規劃出的路徑數據記錄于表5中，并畫出各數據的變化趨勢圖，如圖8所示。

表5 柵格粒度大小對路徑規劃結果的影響Table 5 Influence of grid length on path p lanning resu lts

圖8 柵格粒度大小的影響Fig.8 Influence of grid length

從表5得出，l＝5m時，路徑點數為129，柵格危險度因子為11.69；l＝15 m 時，路徑點數為128，與l取5m時接近，但其柵格危險度因子卻比前者高65%；l分別為10m、20m時，路徑點數、柵格危險度因子均明顯高于l取5m情況。由圖8知，圖8（a）中，路徑點數、路徑航程隨柵格粒度大小呈先增大后減小變化，但仍有上升趨勢；圖8（b）中，能耗隨柵格粒度大小有上升變化趨勢，危險度則相反。經分析，柵格粒度太小變化時，l越小，環境劃設精細，待擴展路徑點多，需要更多存儲空間；l越大，環境劃設粗糙，效率提高，但難保證航程等成本小。綜上所述，l取5m時可規劃出結果最佳的飛行路徑，因此選擇性能較好的5 m為最優的柵格粒度大小設置。

同理，保持柵格粒度大小l＝5m設置不變，由于物流無人機路徑對安全要求較高，故固定α3為0.5不變，分析α1、α2取值對結果的影響，代價權重值組合取表6中設置，在其他參數設置及規劃環境相同的條件下再進行多組對照實驗，對各組實驗規劃出的路徑數據記錄于表6中，并畫出其變化趨勢圖，如圖9所示。

由圖9知，各路徑數據隨代價權重值的取值不同有明顯變化趨勢。圖9（a）中，路徑點數雖有起伏但呈下降趨勢，路徑航程變化幅度大且在實驗5時取最小值；圖9（b）中，能耗呈先減小后增大趨勢，且在實驗5后增長率達7.3%，危險度呈下降變化，且在實驗5中取相對較小值。經分析，飛行時間權重α1越大，路徑點數相應變少，但能耗等有所增加；能耗權重α2越大，能耗相應變少，但路徑點數、危險度有增加趨勢。綜上，實驗5中參數設置可平衡各路徑代價，故選擇α1＝0.4，α2＝0.1，α3＝0.5為最優的代價權重值組合。

表6 代價權重值對規劃結果的影響Tab le 6 In fluence of cost weight on p lanning resu lts

圖9 代價權重值的影響Fig.9 Influence of cost weight

4 結 論

1）引入物流無人機物理性能及任務約束，設計了考慮飛行時間、能耗及危險度的目標函數，建立多限制條件物流無人機路徑規劃模型；為快速解算該模型，設計A*算法并采用雙向交叉判斷法、樣條曲線插值對原路徑優化平滑。

2）以某區域地形高程數據進行仿真驗證，結果表明，本文算法求解物流無人機路徑規劃模型時能在無人機安全避障的前提下，縮短規劃時間，減少能耗與路徑點數，提供可飛連續平滑的路徑。

3）本文模型及算法可應用于物流無人機貨物運輸路徑的規劃，且規劃結果受柵格粒度大小和代價權重值影響較大。在本文設置的運輸路徑規劃環境下，當柵格粒度大小取5 m，代價權重值取0.4、0.1、0.5時，路徑規劃結果最佳。

對低空物流無人機路徑規劃技術的研究目前較少，下一步的研究將從突發情況下物流無人機實時動態路徑規劃及多物流無人機協同貨物運輸路徑規劃進行。