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

張麗麗，黃辰，杜宇飛

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

0 引言

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

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

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

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

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

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

1 構建運行環(huán)境模型

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

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

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

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

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

2 A*算法

2.1 A*算法

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

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

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

2.2 A*算法存在的問題

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

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

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

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

3 改進A*算法

3.1 擴展搜索節(jié)點

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

圖1 八向擴展圖

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

圖2 16個搜索方向

3.2 特殊地形威脅

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

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

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

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

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

4 仿真實驗

4.1 仿真實驗分析及初始化

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

4.2 實現(xiàn)步驟

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

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

Step3：創(chuàng)建OPEN集數(shù)據(jù)結構和CLOSE集數(shù)據(jù)結構，設置起點為第一個點，Node為當前點，F(xiàn)Node為父節(jié)點；

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

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

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

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

4.3 結果分析

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

圖3 傳統(tǒng)A*算法的3D仿真結果

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

圖5 傳統(tǒng)A*算法的垂直剖面視圖

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

圖7 傳統(tǒng)A*算法的水平剖面視圖

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

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

表1 路徑規(guī)劃對比結果

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

5 結論

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