基于改進(jìn)A＊算法的物流無人機(jī)路徑優(yōu)化

張森森，陳 肯，李科揚(yáng)

（中國民用航空飛行學(xué)院空中交通管理學(xué)院，廣漢 618307）

0 引言

隨著經(jīng)濟(jì)的發(fā)展，人們對物流配送服務(wù)的要求越來越高，而物流無人機(jī)憑借其不受交通限制、調(diào)度方便靈活、速度快等特點(diǎn)，能有效破解物流末端“最后一公里”的難題，很多物流企業(yè)順應(yīng)潮流發(fā)展無人機(jī)物流服務(wù)，中國民用無人機(jī)的發(fā)展已經(jīng)進(jìn)入了快速增長階段，因此對于無人機(jī)物流路徑的研究具有現(xiàn)實(shí)意義。文獻(xiàn)［4-6］研究了車輛-無人機(jī)組合運(yùn)輸問題，以運(yùn)輸固定成本、運(yùn)營成本和時(shí)間窗成本之和為目標(biāo)函數(shù)，構(gòu)建了基于TSP 的車輛-無人機(jī)擴(kuò)展路徑模型，通過一種改進(jìn)的迭代算法，確定無人機(jī)配送路線；文獻(xiàn)［7-14］運(yùn)用函數(shù)模擬及柵格法建立環(huán)境模型，利用多種改進(jìn)的A*算法、遺傳算法、粒子群等算法仿真無人機(jī)三維運(yùn)行環(huán)境下的最優(yōu)路徑；文獻(xiàn)［15］提出了一種在偵察區(qū)域內(nèi)通過掃描獲取偵察帶寬的方法偵察指令，然后結(jié)合無人機(jī)偵察飛行軌跡計(jì)算最短路徑原理；文獻(xiàn)［16］把各個(gè)航路點(diǎn)拆開處理，根據(jù)不同航路點(diǎn)分別進(jìn)行定向搜索，通過仿真實(shí)驗(yàn)驗(yàn)證定向進(jìn)化的可靠性；文獻(xiàn)［17］對有禁飛區(qū)的區(qū)域進(jìn)行路徑規(guī)劃時(shí)，通過建立飛行威脅模型，用雙向搜索策略和逆向引導(dǎo)策略解決此類問題。

前人的研究成果主要傾向于無人機(jī)的碰撞風(fēng)險(xiǎn)、自主智能避障等方面；對于復(fù)雜低空、影響路徑規(guī)劃的因素進(jìn)行了簡化處理，不符合無人機(jī)真實(shí)運(yùn)行場景。本文基于柵格法模擬無人機(jī)運(yùn)輸三維環(huán)境，以路徑最優(yōu)化為目標(biāo)，利用改進(jìn)的A*算法與傳統(tǒng)A*算法和RRT算法比較分析，探索物流無人機(jī)最優(yōu)路徑。

1 環(huán)境模型

環(huán)境建模的目的是模擬無人機(jī)真實(shí)運(yùn)行場景，通過模擬分析研究物流無人機(jī)路徑優(yōu)化問題。利用柵格法的建模思想，將無人機(jī)運(yùn)輸環(huán)境模擬為有很多小方塊組成的空間，相當(dāng)于把三維空間數(shù)字化處理，同時(shí)令障礙物為1，非障礙物為0。柵格的大小會影響到模擬效果，柵格較小時(shí)由于需要存儲較多的信息，干擾信號也會隨之增加，規(guī)劃效率和效果隨之下降；反之，很少的信息存儲量會使得規(guī)劃效率隨之加快，但環(huán)境信息劃分會變得較為模糊，不利于有效路徑的規(guī)劃。因此，選擇合適的柵格大小也是影響規(guī)劃效果的一個(gè)因素。

可以根據(jù)無人機(jī)運(yùn)輸環(huán)境需要進(jìn)行柵格化二維處理，黑色區(qū)域代表障礙物，如圖1 所示，把無人機(jī)運(yùn)行環(huán)境分成100個(gè)小格，并且分別指定好起點(diǎn)和終點(diǎn)。利用三維坐標(biāo)系建立無人機(jī)運(yùn)輸環(huán)境，產(chǎn)生以A 點(diǎn)為中心的長方形區(qū)域，將其模擬為現(xiàn)實(shí)環(huán)境，如圖2所示。

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

圖2 規(guī)劃環(huán)境三維柵格化示意

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

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

A*算法考慮將起始點(diǎn)到當(dāng)前節(jié)點(diǎn)的實(shí)際路徑耗散也作為遴選的條件，表達(dá)式為：

其中，（）為路徑規(guī)劃起始點(diǎn)到中間點(diǎn)所付出的航程代價(jià)，（）為中間點(diǎn)到最終點(diǎn)估計(jì)的航程代價(jià)。

實(shí)際代價(jià)函數(shù)（）表達(dá)式為：

其中，、、分別為最小路徑長度、最大航程、轉(zhuǎn)彎角和俯仰角，詳細(xì)敘述見文獻(xiàn)［1］：、、為系數(shù)，且++= 1。

啟發(fā)函數(shù)h（n）的選取影響A*算法的搜索策略，本文將歐氏距離、曼哈頓距離和others距離三者結(jié)合使用，提高啟發(fā)函數(shù)的質(zhì)量。

其中，、、分別是歐氏距離、曼哈頓距離others距離的權(quán)重系數(shù)，且++= 1。

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

2.2.1 使用hash和堆減少每個(gè)柵格的計(jì)算量

具體來說，需要使用hash 表備份Open 表，通過優(yōu)化Open 表，使得所選擇的節(jié)點(diǎn)帶有“可參照性”，而不是單單的直接從Open 表中取。如果Open 表在放入數(shù)據(jù)之前，我們就讓它按照一定順序，那么從Open 表中取數(shù)據(jù)時(shí)，這些數(shù)據(jù)就是具備順序的，是有“可參照性的”?？梢赃x擇優(yōu)先隊(duì)列的方式。

2.2.2 雙向搜索策略

雙向搜索相當(dāng)于有兩個(gè)起始點(diǎn)，雙向去搜索路徑，最后相交于同一點(diǎn)。通過正反向搜索相互切換，如此交替往復(fù)運(yùn)行，直到找到一條最優(yōu)路徑。

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

動態(tài)衡量啟發(fā)式為：

其中（）＞=1。把（）變成了（）*（），在搜索過程中，我們可以通過改變（）來影響（）對A*算法的影響。具體原理是在搜索初始階段搜索速度較快，搜索末期速度較慢，傾向于搜索最優(yōu)路徑?？梢酝评沓?，（）越大，越趨近于BFS 算法；而（）越小，則相對趨近于Dijkstra算法。

2.2.4 路徑平滑處理

通過平滑處理可以消除拐點(diǎn)、折角等現(xiàn)象，使飛行路徑更加平滑，也更接近于真實(shí)飛行方式，可以采用B 樣條法對初始路徑進(jìn)行優(yōu)化處理。

3 算法流程

本文算法流程設(shè)計(jì)如圖3所示。

圖3 算法流程設(shè)計(jì)

步驟1：指定初始點(diǎn)和終點(diǎn)，創(chuàng)建OPEN 集與CLOSED 集，把兩點(diǎn)開始放入OPEN集， 經(jīng)過路徑搜索出點(diǎn)并放入CLOSED集。

步驟2：判斷是否為最佳路徑點(diǎn)，若到達(dá)最優(yōu)點(diǎn)，則把最優(yōu)點(diǎn)放在CLOSED 集進(jìn)行進(jìn)一步的搜索，即執(zhí)行步驟3，否則執(zhí)行步驟4。

步驟3：確定搜索是否完成，所得路徑即為最優(yōu)無人機(jī)運(yùn)輸路徑，否則以當(dāng)前點(diǎn)為起始繼續(xù)搜索。

步驟4：以步驟2 中最優(yōu)節(jié)點(diǎn)為中心，向周圍進(jìn)行大范圍搜索，不斷更新最優(yōu)點(diǎn)放入OPEN集，繼續(xù)執(zhí)行步驟2。

4 仿真分析

比較幾種算法的模擬效果，并驗(yàn)證改進(jìn)算法的優(yōu)越性，進(jìn)行仿真實(shí)驗(yàn)，指定起始點(diǎn)為（1，2，0），終點(diǎn)為（8，6，2），基礎(chǔ)數(shù)據(jù)見表1。

表1 參數(shù)取值

利用仿真平臺，分別對A*算法以及改進(jìn)的A*算法進(jìn)行仿真，結(jié)果如圖4所示。

圖4 A＊算法和改進(jìn)A＊算法結(jié)果

從圖4 可以看出，經(jīng)過優(yōu)化處理過的A*算法所計(jì)算的路徑更短，也更加平滑，符合無人機(jī)現(xiàn)實(shí)運(yùn)行情況。因此，本文使用的經(jīng)過改進(jìn)的A*算法更加優(yōu)化了無人機(jī)運(yùn)輸路徑。

為了增加對比，把RRT 算法的仿真結(jié)果也展現(xiàn)出來，如圖5所示。

從圖5 可以明顯看到，此算法所求路徑比A*算法要長。三種算法運(yùn)算數(shù)據(jù)見表2。

圖5 RRT算法結(jié)果

表2 幾種算法運(yùn)算數(shù)據(jù)比較

從計(jì)算結(jié)果可以看出，A*算法可以更好地靠近最優(yōu)路徑，而RRT 算法迭代時(shí)間更短；經(jīng)過優(yōu)化的A*算法實(shí)現(xiàn)雙向搜索之后，搜索效率也明顯提升，搜索到的路徑更加優(yōu)化，本文改進(jìn)的A*算法可以很好地解決物流無人機(jī)路徑規(guī)劃問題。

5 結(jié)語

本文利用柵格法建立物流無人機(jī)三維運(yùn)行環(huán)境，比較分析A*算法和RRT 算法，針對兩者存在的缺陷進(jìn)行雙向搜素、啟發(fā)函數(shù)等的改進(jìn)。改進(jìn)后的A*算法模擬效果明顯更好，而且運(yùn)行時(shí)間更短，模擬出的飛行路徑更加平滑，因此，改進(jìn)后的A*算法能夠很好地處理類似問題。