基于改進A＊算法的物流無人機路徑優化

張森森，陳 肯，李科揚

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

0 引言

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

前人的研究成果主要傾向于無人機的碰撞風險、自主智能避障等方面；對于復雜低空、影響路徑規劃的因素進行了簡化處理，不符合無人機真實運行場景。本文基于柵格法模擬無人機運輸三維環境，以路徑最優化為目標，利用改進的A*算法與傳統A*算法和RRT算法比較分析，探索物流無人機最優路徑。

1 環境模型

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

可以根據無人機運輸環境需要進行柵格化二維處理，黑色區域代表障礙物，如圖1 所示，把無人機運行環境分成100個小格，并且分別指定好起點和終點。利用三維坐標系建立無人機運輸環境，產生以A 點為中心的長方形區域，將其模擬為現實環境，如圖2所示。

圖1 規劃環境二維柵格化示意

圖2 規劃環境三維柵格化示意

2 改進A＊算法

2.1 傳統A＊算法原理

A*算法考慮將起始點到當前節點的實際路徑耗散也作為遴選的條件，表達式為：

其中，（）為路徑規劃起始點到中間點所付出的航程代價，（）為中間點到最終點估計的航程代價。

實際代價函數（）表達式為：

其中，、、分別為最小路徑長度、最大航程、轉彎角和俯仰角，詳細敘述見文獻［1］：、、為系數，且++= 1。

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

其中，、、分別是歐氏距離、曼哈頓距離others距離的權重系數，且++= 1。

2.2 改進A＊算法

2.2.1 使用hash和堆減少每個柵格的計算量

具體來說，需要使用hash 表備份Open 表，通過優化Open 表，使得所選擇的節點帶有“可參照性”，而不是單單的直接從Open 表中取。如果Open 表在放入數據之前，我們就讓它按照一定順序，那么從Open 表中取數據時，這些數據就是具備順序的，是有“可參照性的”。可以選擇優先隊列的方式。

2.2.2 雙向搜索策略

雙向搜索相當于有兩個起始點，雙向去搜索路徑，最后相交于同一點。通過正反向搜索相互切換，如此交替往復運行，直到找到一條最優路徑。

2.2.3 改進啟發函數

動態衡量啟發式為：

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

2.2.4 路徑平滑處理

通過平滑處理可以消除拐點、折角等現象，使飛行路徑更加平滑，也更接近于真實飛行方式，可以采用B 樣條法對初始路徑進行優化處理。

3 算法流程

本文算法流程設計如圖3所示。

圖3 算法流程設計

步驟1：指定初始點和終點，創建OPEN 集與CLOSED 集，把兩點開始放入OPEN集， 經過路徑搜索出點并放入CLOSED集。

步驟2：判斷是否為最佳路徑點，若到達最優點，則把最優點放在CLOSED 集進行進一步的搜索，即執行步驟3，否則執行步驟4。

步驟3：確定搜索是否完成，所得路徑即為最優無人機運輸路徑，否則以當前點為起始繼續搜索。

步驟4：以步驟2 中最優節點為中心，向周圍進行大范圍搜索，不斷更新最優點放入OPEN集，繼續執行步驟2。

4 仿真分析

比較幾種算法的模擬效果，并驗證改進算法的優越性，進行仿真實驗，指定起始點為（1，2，0），終點為（8，6，2），基礎數據見表1。

表1 參數取值

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

圖4 A＊算法和改進A＊算法結果

從圖4 可以看出，經過優化處理過的A*算法所計算的路徑更短，也更加平滑，符合無人機現實運行情況。因此，本文使用的經過改進的A*算法更加優化了無人機運輸路徑。

為了增加對比，把RRT 算法的仿真結果也展現出來，如圖5所示。

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

圖5 RRT算法結果

表2 幾種算法運算數據比較

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

5 結語

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