基于改進A*算法的無人機路徑規劃研究

張麗麗，黃辰，杜宇飛

（沈陽航空航天大學 民用航空學院，遼寧沈陽，110136）

0 引言

隨著科技和經濟的蓬勃發展，移動機器人作為我國新興科技的重要產業被各行各業所大量應用。目前，用途不同、型號不同的移動機器人正在不同的應用領域中有著越來越廣闊的應用，我國移動機器人市場也呈現出了迅速發展的勢頭。隨著移動機器人技術的不斷發展，移動機器人在導航和外賣物流等領域得到了迅速的發展，人們渴望更高效、運營成本更低廉、更省時省事的方式。移動機器人具有交付效率高、靈活性強、實用性強、環境污染小等特點，并且移動機器人可以通過自主執行任務來降低人工成本。因此，掀起了移動機器人物流時代的攻勢。

由于政府的大力推進，使移動機器人的導航技術取得了階段性的研究成果，降低了人工成本，但也帶來了以下挑戰：

(1)移動機器人運行時移動的安全仍然面臨著嚴峻的挑戰。雖然移動機器人的運行在企業中的應用越來越廣泛，但是復雜環境中物體的移動受到的空間、各種障礙物的混合的制約，給移動機器人的運行安全帶來了很大風險，如移動機器人與障礙物碰撞、移動機器人在復雜地形運行等問題。

(2)移動機器人運行的效率。各類設備的采購成本仍然很高，導致了采購成本的居高不下，缺乏合格的設備。因此，為了平衡移動機器人本身的費用，需要規劃出更快速、更高效的運行路徑。但目前規劃的生成路徑可能在移動中有很多轉折點、路線不夠平滑，在大規模搜索的情況下，大量計算會降低因操作效率等問題導致的低運營效率。

(3)地形狀況對移動機器人移動姿態的影響。移動機器人的體積較小，因此，地形因素對移動機器人的使用的影響更大，例如，路面不平不僅會影響到移動機器人靈活性與機動性，還會影響移動機器人的承載能力，使運動狀態造成威脅。

綜合上述幾種情況，為了有序、安全、高效、平穩地運行，移動機器人的運行路線需要獨立規劃，從合理避障的角度切入，針對突破路徑優化過程中的技術難題，在保障安全運行的前提下盡量提高效率，達到最大程度利用移動機器人，降低運輸成本。本文在傳統的A*算法規劃路徑的基礎上進行一些改進，提高運行效率、減少轉折點、盡量使路線更加平滑、降低移動機器人運行風險，也減少了能源損耗。

1 構建運行環境模型

在復雜的環境中，移動機器人的路徑規劃的第一要素是安全，安全的移動才是實現一切行動的前提，第二則考慮規劃出更短的移動路徑，更短的路徑會讓移動機器人的耗能和運行時間變少。移動機器人的障礙區域主要包括桌椅板凳、特殊地形等，根據障礙物的特點進行簡化，構建適合移動機器人運行的環境模型地圖。移動機器人在運行時，可能會遇到因道路不平等地形威脅，需要考慮不同地形情況對規劃移動機器人路徑的影響并保障其移動安全。

規劃路徑的第一步是規劃運行環境模型，通常使用的環境圖形的構建方法有柵格法［1］、可視圖法［2］、拓撲圖法。根據移動時的地形障礙物等特征構建運行環境模型，采用可視圖法模擬移動機器人的移動條件，可視圖法建立的環境模型簡單，易于使用和維護，路線觀測較為直觀，因此建立適合移動機器人運行環境的三維地形圖。

(1)設置坐標軸范圍為1到MAX_X，1到MAX_Y，1到MAX_Z，創建一個曲面圖，并將Z中元素的列索引和行索引用作x坐標和y坐標，以10為單位長度對x軸和y軸進行劃分，2000為單位長度對z軸進行劃分，同時對坐標系中文字的字體規定為宋體，方向節點也進行了限定。

(2)繪制異常地形區，將地面中不平的低洼地區用球體進行模擬，確定球體自變量，對異常地形區域進行限制，并將綠色地區設定為異常地形區，確定出異常地形區進行模擬。對異常數據設置限制進行封頂處理。

(3)設置障礙物，用0標記的節點代表可以通過的節點，用1標記的節點代表不能通過的節點，繪制符合規劃路徑的不同方位的障礙物地形圖。

2 A*算法

2.1 A*算法

A*算法是N.J.Nilsson、B.Raphael和 P.E.Hart在1968年提出來的一種啟發式搜索算法[3]。這種方法將Dijkstra和BFS兩種方法的優勢相融合，并且Dijkstra算法與BFS算法的距離代價同時被A*算法考慮到，摒棄了部分劣勢構造了新的代價函數用來搜索路徑。從規劃路徑的起始點出發，根據節點的擴展方向，通過柵格圖繼續搜索目標點的最優搜索方向，獲得最優路徑，保證搜索效率。其基本思想是利用啟發式函數計算柵格周圍8個節點的估計值，選擇生成最低成本的節點作為下一個搜索步驟的父節點，繼續不斷搜索該父節點周圍相鄰的節點，直到找到目標節點為止來確定搜索方向[4]。因此搜索算法的效率不僅被提高了，還優化了規劃的路徑以至保證路徑最優，代價函數的計算方式可表示為：

式中：g(n)是指從起始點到待擴展點n的實際路程的代價，一般是固定數值；啟發函數是A*算法的關鍵，具有一致性和可接受性的啟發函數可使A*算法收斂到既滿足局部最優的解又滿足全局最優的解[5]，h(n)是待擴展點n到終止點的預估路程，為了減少該算法的計算量，選用歐式距離來近似代替啟發函數，啟發式函數如下式：

從式(2)可以看出，h(n)函數表示待擴展路徑點n到目標節點的x軸、y軸和z軸的相對距離的絕對值的和。

2.2 A*算法存在的問題

A*算法作為最常用的全局算法之一，該算法可以快速確定靜態環境下的最優路徑[6]，但傳統的A*算法仍然存在搜索范圍少、擴展方向盲目等一些缺點。

使用傳統的A*算法搜索移動機器人路徑時，會存在以下問題：

(1)當傳統A*算法擴展路徑點時，計算量會隨著地圖增大而增加，從而導致搜索效率降低、規劃路線不平滑等問題。

(2)傳統的A*算法搜索出來的算法只有躲避障礙物的路徑，沒有考慮在復雜的地形條件下執行運行任務的路徑。為了解決上述在移動機器人運行中存在的問題，對A*算法進行如下改進。

3 改進A*算法

3.1 擴展搜索節點

在傳統A*算法中，簡化了移動機器人在移動運輸中與周圍障礙物碰撞的問題，將移動機器人在三維坐標系中的投影視為一個質點，提出了一種擴大搜索范圍、拓展節點的方法。傳統A*算法在當前目標點擴展領域節點時，擴展的路徑通常使用八向區域擴展，也就是八個搜索方向的搜索方式，八向領域擴展偏向于存儲搜索模式，擴展節點如圖1所示，每次當前路徑點臨近的8個鄰域可以被算法搜索到，每一個轉角都為45°，導致有效搜索方向是有限的。

圖1 八向擴展圖

為準確確定A*算法的搜索范圍，將物流無人機的搜索方向擴展到16個，如圖2所示，移動機器人可以從當前路徑點直接搜索到鄰近區域的8+16個節點中是否存在障礙物，因此移動機器人的最小轉角減小到22.5°，有效地擴展了搜索范圍。在選擇下一個擴展節點之前，長遠的搜索范圍可以更好地規劃路徑來搜索下一路徑點，為了更快地到達終止路徑點，更快速地完成運行任務打下基礎。

圖2 16個搜索方向

3.2 特殊地形威脅

移動機器人的體積更小，對地面威脅的感知更加敏感。因此，移動機器人的路徑規劃要考慮地形對運行姿態的威脅。

在路徑規劃中，以移動機器人的安全為主要目標，考慮到地面不平整有凹陷問題，使規劃的路線滿足運行需求，因此首先對安全方面進行優化，其次考慮優化時間消耗。為了規劃出高安全度和高效率的移動機器人運行路徑，對搜索路徑進行約束。

本文主要研究地面凹陷對移動機器人運行時規劃路徑的影響，將凹陷區域表示為一個球體，球體半徑就是凹陷的范圍，因此，凹陷的最大半徑記為Rmax。凹陷的危險度W如下式：

式中：xs、ys為與當前點相鄰的點的立方體周圍坐標。

式中，Tw為移動機器人到凹陷區域中心的距離。

4 仿真實驗

4.1 仿真實驗分析及初始化

仿真采用的計算機型號為CPUi5-8265U，4G內存，1.6GHz的主頻，使用MATLAB R2018b版本軟件進行仿真實驗。規劃環境長度、寬度和高度分別為100×100×6000的空間區域為運行的環境地圖，在此基礎上輸入起始點、終止點、障礙物特性、特殊地形區域、啟發式函數、實際成本函數等限制條件，并從生成的三種不同地圖環境中的規劃路徑地面投影長度、規劃路徑長度、路線形狀與傳統A*算法進行對比，再使用通過MATLAB程序得到的數據進行計算，從而驗證改進A*算法在移動機器人路徑規劃中的可行性。

4.2 實現步驟

Step1：輸入移動機器人尋路程序、路徑起始坐標和結束坐標；

Step2：繪制改進A*算法路徑規劃的不同方位的地圖，包括：三維環境地圖，垂直剖面視圖，水平剖面視圖；

Step3：創建OPEN集數據結構和CLOSE集數據結構，設置起點為第一個點，Node為當前點，FNode為父節點；

Step4：設置g(n)起點到指定方格和h(n)指定方格到終點。判斷是否有可行路徑，并且把1設置為可行路徑，把0設置為不可行路徑；

Step5：判斷搜索到的路徑點是否為目標點，選擇最小f(n)值的點為下一路徑點；

Step6：當路徑點已經到終止路徑點所在的節點，或未擴展到終止巡航點但 OPEN 列表為空時搜索完成。

Step7：移動機器人的運行軌跡從終止路徑點，經過每個路徑點的父節點，反向回溯直到達起始點，算法可以停止。

4.3 結果分析

采用傳統A*算法與改進A*算法得到移動機器人路徑結果，3D仿真結果如圖3、圖4所示，垂直剖面視圖如圖5和圖6所示，水平剖面視圖如圖7和圖8所示。在起始路徑點 start 坐標為（20，20，7），終止路徑點 end 坐標為（90，70，5）時，利用改進的A*算法在三維地圖和垂直水平兩個剖面地圖下得到的路徑規劃圖。

圖3 傳統A*算法的3D仿真結果

圖4 改進A*算法的3D仿真結果

圖5 傳統A*算法的垂直剖面視圖

圖6 改進A*算法的垂直剖面視圖

圖7 傳統A*算法的水平剖面視圖

圖8 改進A*算法的水平剖面視圖

由圖可以直觀地看出，改進A*算法在三種表示方式不同的地圖上，比傳統的A*算法規劃的路徑擁有更小的轉彎角度、更大的路徑平滑度、更短的運行路徑長度，安全性和效率都得到了明顯的提高，移動機器人從起始點通過新規劃的路徑到終止點所經的路徑更短，且能夠適應不同方位表達的空域環境地圖，同時和障礙物保持一定的距離，避免與障礙物發生碰撞，保障了移動機器人在運行時候的安全。改進A*算法的擴展搜索節點通過減少路徑折角使路徑變得更加平滑，以此高效、平穩地避開了對環境中的障礙物。同時考慮環境中的特殊的地形凹陷對移動機器人的威脅，對運行路徑進行約束，提高了移動機器人運行時的安全性。

表1 路徑規劃對比結果

由表1可知，傳統A*算法規劃路徑長度為13091.44 m，改進后的A*算法規劃路徑長度為11813.24 m，傳統A*算法規劃路徑地面投影長度為12266.90 m，改進后的A*算法規劃路徑地面投影長度為10959.80m。通過計算可知，改進后的A*算法比傳統A*算法規劃路徑長度縮短了9.8%，地面投影長度縮短了10.7%，也表明了上文對擴展搜索節點和考慮運行時特殊地形威脅的合理性，改進后的A*算法在移動機器人運行時能夠規劃出更短的路徑。

5 結論

A*算法在路徑規劃方面具有一定的優勢，可以為最優安全運行路徑提供快速求解方法。因此，本文在傳統A*算法的基礎上提出了一種改進算法，通過把搜索節點數擴大搜索范圍，搜索方向擴展成16個，鄰域則擴展為24個，解決了路徑拐點個數多、路徑不平滑、搜索范圍有限等問題，可以快速有效地規劃在靜態環境下的一條最優路徑來避免碰撞保障運行安全，同時也提高了搜索精度，縮短了移動機器人的運行路徑；仿真實驗結果表明，基于該算法的移動機器人在保證安全避障的前提下，改進后的A*算法在規劃路徑長度和規劃路徑地面投影長度等方面都優于原算法，更加符合移動機器人的運行狀態，為后續移動機器人的研究提供思路。