復(fù)雜低空物流無(wú)人機(jī)路徑規(guī)劃

張啟錢，許衛(wèi)衛(wèi)，張洪海，鄒依原，陳雨童

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

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

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

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

本文從物流無(wú)人機(jī)飛行安全和運(yùn)輸效率角度出發(fā)，以最小化路徑飛行時(shí)間、能耗及危險(xiǎn)度作為目標(biāo)函數(shù)，構(gòu)建在滿足無(wú)人機(jī)運(yùn)輸貨物過(guò)程中自主安全避障的前提下，減小運(yùn)行成本的物流無(wú)人機(jī)路徑規(guī)劃模型，設(shè)計(jì)基于A*算法的路徑快速搜索策略，以獲得最佳的貨物配送路徑。

1 物流無(wú)人機(jī)路徑規(guī)劃問(wèn)題建模

1.1 問(wèn)題描述與相關(guān)假設(shè)

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

1.2 飛行環(huán)境建模

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

1.3 柵格法規(guī)劃環(huán)境表征

柵格法將環(huán)境劃分為單元格，依據(jù)其中是否存在障礙物分類：若存在地形地物等障礙，則為障礙柵格并賦值1；否則，為自由柵格并賦值0。采用柵格法擴(kuò)展路徑點(diǎn)需考慮柵格粒度大小設(shè)置，即柵格邊長(zhǎng)。柵格粒度過(guò)大導(dǎo)致規(guī)劃的路徑偏離理論最優(yōu)解，過(guò)小則導(dǎo)致規(guī)劃時(shí)計(jì)算量大。由于柵格中心點(diǎn)是物流無(wú)人機(jī)飛行路徑點(diǎn)且路徑需滿足無(wú)人機(jī)性能約束，因此柵格粒度大小需和性能限制匹配。

設(shè)運(yùn)輸任務(wù)規(guī)劃環(huán)境是長(zhǎng)、寬、高分別為x、y、z的長(zhǎng)方體區(qū)域，記為OABC-O′A′B′C′，以O(shè)為原點(diǎn)建立三維直角坐標(biāo)系。其中，OA長(zhǎng)度為x，AA′長(zhǎng)度為y，OC長(zhǎng)度為z?？紤]環(huán)境信息及物流無(wú)人機(jī)性能確定柵格粒度大小l。按以下2步確定柵格坐標(biāo)。

步驟1 對(duì)OABC-O′A′B′C′沿OO′進(jìn)行m等分，過(guò)等分點(diǎn)作平行于OABC面的平面，得m-1個(gè)平面γj（j＝1，2，…，m）。其中，m ＝int（y／l），int（）為取整函數(shù)。

步驟2 對(duì)上述任一平面γj，沿OA進(jìn)行u等分，沿OC進(jìn)行h等分。其中u＝int（x／l），h＝int（z／l）。此時(shí)γj便離散成u×h個(gè)平面柵格，OABC-O′A′B′C′被離散成m×u×h個(gè)立體柵格，則物流無(wú)人機(jī)待擴(kuò)展路徑點(diǎn)可標(biāo)記為p（i，j，k），i＝1，2，…，m，j＝1，2，…，u，k＝1，2，…，h。

圖1為規(guī)劃環(huán)境柵格化示意圖。

圖1 規(guī)劃環(huán)境柵格化Fig.1 Grid of planning environment

1.4 多限制條件物流無(wú)人機(jī)路徑規(guī)劃模型

物流無(wú)人機(jī)貨物運(yùn)輸需考慮多方面影響要素，本文綜合考慮物流無(wú)人機(jī)性能約束與任務(wù)要求，從運(yùn)輸?shù)陌踩?、?jīng)濟(jì)性和快捷性等角度建立多限制條件物流無(wú)人機(jī)路徑規(guī)劃模型。

1.4.1 性能約束

1）最遠(yuǎn)航程、最小路徑段長(zhǎng)度

物流無(wú)人機(jī)路徑中相鄰兩飛行路徑點(diǎn)間距離不能小于最小路徑段長(zhǎng)度，約束為

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

式（8）為目標(biāo)函數(shù)；式（9）中前7個(gè)式子為物流無(wú)人機(jī)性能約束；最后一個(gè)式子為物流無(wú)人機(jī)貨物運(yùn)輸任務(wù)約束，表示物流無(wú)人機(jī)應(yīng)在規(guī)定時(shí)間內(nèi)完成任務(wù)。

2 算法設(shè)計(jì)

2.1 A*算法原理及流程

A*算法通過(guò)估計(jì)代價(jià)函數(shù)f（n）選擇待擴(kuò)展路徑點(diǎn)n，通常考慮的代價(jià)是航程，即要求獲得飛行總航程最短的路徑，表達(dá)式為

式中：g（n）為起始派送點(diǎn)S至待擴(kuò)展路徑點(diǎn)n的實(shí)際飛行航程，稱為實(shí)際代價(jià)函數(shù)；h（n）為待擴(kuò)展路徑點(diǎn)n至目的派送點(diǎn)G的預(yù)估飛行航程，稱為啟發(fā)式函數(shù)。

A*算法的原理及實(shí)施流程參見文獻(xiàn)［20］，本文不再贅述。

2.2 算法設(shè)計(jì)方案

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

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

2.3 具體設(shè)計(jì)

2.3.1 新增柵格危險(xiǎn)度因子

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

式中：d為柵格危險(xiǎn)度因子；Nobstacle為該柵格周圍障礙柵格數(shù)；Nsurround為周圍總柵格數(shù)。

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

圖2 柵格危險(xiǎn)度因子計(jì)算Fig.2 Calculation of grid risk

2.3.2 添加貨物質(zhì)量懲罰系數(shù)

物流無(wú)人機(jī)不同機(jī)動(dòng)行為對(duì)能耗是不同的［16］，所以函數(shù)g（n）將水平和升降運(yùn)動(dòng)能耗分開計(jì)算且不考慮起降能耗。假設(shè)物流無(wú)人機(jī)水平運(yùn)動(dòng)能耗為距離的λ倍，垂直運(yùn)動(dòng)能耗為高度差的r倍，g（n）表達(dá)式為

2.3.5 路徑優(yōu)化及平滑

路徑轉(zhuǎn)彎多表明物流無(wú)人機(jī)姿態(tài)改變次數(shù)多，利用雙向交叉判斷法篩除冗余路徑點(diǎn)可減少路徑點(diǎn)數(shù)，其思想是：當(dāng)原路徑中不相鄰兩路徑點(diǎn)間連線構(gòu)成的路徑段不與障礙物交叉時(shí)，可剔除該兩點(diǎn)間的冗余路徑點(diǎn)。假設(shè)采用本文算法搜索的原路徑為Path，按如下步驟對(duì)該路徑進(jìn)行優(yōu)化，操作示例如圖3所示。

步驟1 創(chuàng)建新列表DELETE。

步驟2 對(duì)Path中路徑點(diǎn)按其高度劃分為多段子路徑Path＝｛subpath1，subpath2，…｝，任一子路徑可表示為subpathi＝｛p1，p2，…，pe｝，e為該段路徑點(diǎn)總個(gè)數(shù)。

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

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

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

步驟6 對(duì)其余子路徑循環(huán)執(zhí)行步驟3～步驟5，直至所有路徑點(diǎn)全判斷完畢。

步驟7 將位于DELETE的路徑點(diǎn)在原Path中篩除，剩余路徑點(diǎn)序列構(gòu)成的路徑即為精簡(jiǎn)路徑。

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

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

2.4 算法實(shí)現(xiàn)

本文算法規(guī)劃物流無(wú)人機(jī)路徑的流程如圖4所示，步驟如下：

步驟1 獲得物流無(wú)人機(jī)機(jī)動(dòng)性能約束，起始派送點(diǎn)和目的派送點(diǎn)坐標(biāo)，貨物質(zhì)量懲罰系數(shù)τ（Q）。

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

步驟2 依據(jù)運(yùn)輸場(chǎng)景地圖確定柵格粒度大小，采用非二值存儲(chǔ)法生成柵格危險(xiǎn)度因子矩陣。

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

步驟4 循環(huán)執(zhí)行：

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

4.2 將A點(diǎn)移入CLOSE列表。

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

4.3.1 若B點(diǎn)已在OPEN列表，則確定B點(diǎn)的最優(yōu)父節(jié)點(diǎn)。記對(duì)原先B點(diǎn)求得的估計(jì)成本值為fQ（B′），若fQ（B）＜fQ（B′），B點(diǎn)的父節(jié)點(diǎn)為A點(diǎn)；否則B點(diǎn)的父節(jié)點(diǎn)不變。

4.3.2 若B點(diǎn)已在CLOSE列表，則跳過(guò)B點(diǎn)。

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

步驟5 當(dāng)路徑點(diǎn)到達(dá)目的派送點(diǎn)所在柵格或未擴(kuò)展到目的派送點(diǎn)但OPEN列表為空時(shí)搜索結(jié)束，終止步驟4。

步驟6 從目的派送點(diǎn)通過(guò)各路徑點(diǎn)的父節(jié)點(diǎn)反向移動(dòng)回到起始派送點(diǎn)，便得物流無(wú)人機(jī)路徑，并采用雙向交叉判斷法及樣條曲線插值對(duì)該路徑進(jìn)行優(yōu)化平滑。

3 仿真驗(yàn)證及分析

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

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

表1 環(huán)境數(shù)據(jù)Tab le 1 Environm en tal data

圖5 物流無(wú)人機(jī)路徑規(guī)劃環(huán)境Fig.5 Environment for path planning of logistics UAV

表2 仿真參數(shù)Table 2 Sim ulation param eters

3.2 仿真結(jié)果分析

采用本文算法及表2中參數(shù)設(shè)置得到物流無(wú)人機(jī)路徑規(guī)劃結(jié)果，如圖6中綠色曲線所示?？芍?，該物流無(wú)人機(jī)安全平滑地從起始派送點(diǎn)飛行至目的派送點(diǎn)，且有效地對(duì)低空環(huán)境中的障礙物進(jìn)行避讓。為對(duì)比本文算法與A*算法規(guī)劃性能的優(yōu)劣，在上述各參數(shù)設(shè)置、路徑規(guī)劃環(huán)境保持不變的前提下，對(duì)該物流無(wú)人機(jī)路徑利用A*算法進(jìn)行規(guī)劃，結(jié)果如圖6中紅色曲線所示，并從飛行路徑的路徑點(diǎn)數(shù)、航程、能耗等方面進(jìn)行分析，數(shù)據(jù)如表3所示。可以看出，本文算法的各指標(biāo)數(shù)據(jù)均優(yōu)于A*算法，且路徑點(diǎn)數(shù)變化率最大，降低了42.9%，表明雙向交叉判斷法可有效減小路徑點(diǎn)數(shù)，降低物流無(wú)人機(jī)姿態(tài)改變次數(shù)，保證了貨物運(yùn)輸安全。

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

圖6 物流無(wú)人機(jī)路徑規(guī)劃結(jié)果Fig.6 Path planning results of logistics UAV

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

通過(guò)以上分析得，本文算法路徑規(guī)劃結(jié)果在路徑航程、能耗、危險(xiǎn)度等方面都優(yōu)于A*算法及人工勢(shì)場(chǎng)法；物流無(wú)人機(jī)路徑規(guī)劃模型可優(yōu)化無(wú)人機(jī)的貨物運(yùn)輸時(shí)間和路徑搜索結(jié)果，實(shí)現(xiàn)時(shí)間上飛行時(shí)間減少、空間上安全平滑避障，進(jìn)而及時(shí)低風(fēng)險(xiǎn)地完成任務(wù)，這也表明引入柵格危險(xiǎn)度因子、動(dòng)態(tài)賦權(quán)估計(jì)成本函數(shù)等改進(jìn)的合理性。

圖7 不同算法路徑規(guī)劃結(jié)果Fig.7 Path planning results of different algorithms

表4 不同算法路徑規(guī)劃結(jié)果對(duì)比Tab le 4 Com parison of path p lanning resu lts am ong different algorithm s

3.3 算法參數(shù)分析

在求解物流無(wú)人機(jī)路徑規(guī)劃模型時(shí)，柵格粒度大小l和代價(jià)權(quán)重值組合｛α1，α2，α3｝會(huì)對(duì)模型解算結(jié)果產(chǎn)生影響。本文采用對(duì)照實(shí)驗(yàn)法分析參數(shù)l和｛α1，α2，α3｝的取值對(duì)路徑規(guī)劃結(jié)果的影響。

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

表5 柵格粒度大小對(duì)路徑規(guī)劃結(jié)果的影響Table 5 Influence of grid length on path p lanning resu lts

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

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

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

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

表6 代價(jià)權(quán)重值對(duì)規(guī)劃結(jié)果的影響Tab le 6 In fluence of cost weight on p lanning resu lts

圖9 代價(jià)權(quán)重值的影響Fig.9 Influence of cost weight

4 結(jié) 論

1）引入物流無(wú)人機(jī)物理性能及任務(wù)約束，設(shè)計(jì)了考慮飛行時(shí)間、能耗及危險(xiǎn)度的目標(biāo)函數(shù)，建立多限制條件物流無(wú)人機(jī)路徑規(guī)劃模型；為快速解算該模型，設(shè)計(jì)A*算法并采用雙向交叉判斷法、樣條曲線插值對(duì)原路徑優(yōu)化平滑。

2）以某區(qū)域地形高程數(shù)據(jù)進(jìn)行仿真驗(yàn)證，結(jié)果表明，本文算法求解物流無(wú)人機(jī)路徑規(guī)劃模型時(shí)能在無(wú)人機(jī)安全避障的前提下，縮短規(guī)劃時(shí)間，減少能耗與路徑點(diǎn)數(shù)，提供可飛連續(xù)平滑的路徑。

3）本文模型及算法可應(yīng)用于物流無(wú)人機(jī)貨物運(yùn)輸路徑的規(guī)劃，且規(guī)劃結(jié)果受柵格粒度大小和代價(jià)權(quán)重值影響較大。在本文設(shè)置的運(yùn)輸路徑規(guī)劃環(huán)境下，當(dāng)柵格粒度大小取5 m，代價(jià)權(quán)重值取0.4、0.1、0.5時(shí)，路徑規(guī)劃結(jié)果最佳。

對(duì)低空物流無(wú)人機(jī)路徑規(guī)劃技術(shù)的研究目前較少，下一步的研究將從突發(fā)情況下物流無(wú)人機(jī)實(shí)時(shí)動(dòng)態(tài)路徑規(guī)劃及多物流無(wú)人機(jī)協(xié)同貨物運(yùn)輸路徑規(guī)劃進(jìn)行。