基于A＊算法的無人機路徑規劃研究及分析

羅漢杰，林義尚，周杰，沈桂英，倪虹

（杭州師范大學錢江學院，杭州310018）

0 引言

無人機的航行時間周期短，電能消耗過快并且在飛行也存在一些安全隱患。在飛行過程中，路徑規劃成為了關鍵技術[1]。此技術不僅可以節能同時也能提高無人機的安全性。常用的規劃算法有迪杰斯特拉（Dijkstra）算法、BFS 算法以及A*算法都是一些典型的最有效路徑算法。通過比對尋找到各個節點的最小代價節點，對其最小代價節點進行不斷擴展，直至找到最終的目的節點。本文采用Malabar 軟件搭建無人機三維，利用以A*算法，對杭州師范大學錢江學院其中一區域為無人機飛行環境進行模擬。

1 MALAB建模

利用MLTLAB 開發性與交互性強、操作簡便的特點。通過UG 導出STL 格式的外形數據。其模型外形由不同的頂點組成小三角形面片，多個面片組合可以實現了無人機整體各種形狀的曲面。其面片的數據均采用以下格式

通過讀取模型的外形數據得出以下結果。圖1 為路空兩用無人機MATLAB 建模空間結果。

圖1 路空兩用無人機MATLAB建模圖

本次無人機路徑規劃所采用的是路空兩用無人機在傳統無人機基礎結構上改良具備輪動、爬樓與飛行模式。傳統四旋翼無人機由于工藝與技術限制，其受外界如大風、地形等影響較大。本無人機在硬件設計方面，通過齒輪傳動，實現旋翼槳距距離、角度與位置的自由變化。提高了無人機在樓巷、叢林等狹小涵道與大風環境中的穩定性。內置的無刷電機調整轉速，完成爬升、降落、轉向多姿態變換。在無人機控制硬件方面：采用模塊化架構形式，搭載Arduino2560 微型控制板，通過數據傳輸模塊、電機驅動模塊、飛行控制模塊、六軸運動模塊、GPS 模塊、電子羅盤、氣壓計七大部分組成[3]。GPS 與電子羅盤雙位置傳感器的設置，有效提高了飛行需求。其中USV 攝像頭收集外界圖像，OpenCV 完成數據處理，基于A*算法完成路徑的規劃[4]。可以應對復雜的環境。可折疊并且結構簡單，重量適中的特點也使其易于攜帶。

2 柵格模型的建立

以杭州師范大學錢江學院地形為例，取學校其中的一個區域進行無人機的路徑規劃，區域包括A 教學樓、B 教學樓，C 教學樓、第二實驗樓及圖書館等在的區域。采用自主設計的陸空兩用無人機進行試驗，無人機建模圖如圖1 所示，飛行模式時機架呈X 型模式，軸距為500 毫米，構建以60×60 格的柵格模型，一個格邊長為10 米，灰色部分為障礙物所在位置（建筑）。飛行軌跡障礙柵格模型圖若圖二所示，以藍點為出發點，紅點為目的地。

圖2 飛行軌跡障礙柵格模型圖

3 A＊算法路徑規劃

3.1 A★算法原理

A*算法是一種重要的啟發式算法，它主要是用于在最優路徑選擇上，可以在靜態路網中求解出最短最有效的路徑，而其算法通過定義滿足一定的評估函數，估計各個節點的搜索代價，通過比對尋找到各個節點的最小代價節點，對其最小代價節點進行不斷擴展，直至找到最終的目的節點[5]。其一般公示如公示（1）所示：

其中，f（n）是從初始狀態到最終狀態的總代價估計，即從起點到終點的最小代價估計總值，g（n）是在狀態空間中從初始狀態到狀態n 的實際的代價，即消耗的實際代價，h（n）是從當前節點到目標節點的估計代價，一般體現的是啟發式的信息，即啟發函數。為了尋找到最短路徑即最優解，其中的關鍵在于如何選擇f（n）。[5]

該算法在最短路徑選擇搜索算法中一般分類為：直接搜索算法，啟發式算法，靜態圖搜索算法。

3.2 利用A★算法模擬路徑

對于無人機的路線圖基本可以作為一個幾何柵格模型圖進行求解，當無人機在地圖中的運動方向為正方向時，即正東、正西、正南、正北方向，可以選擇曼哈頓距離作為估價函數，曼哈頓距離為兩個節點之間的x軸方向和y軸方向上的距離，因此啟發函數可以看作為公式（2）所示：

假設行一個網格的飛行距離為D，即曼哈頓距離為D，則h(n)如公式（3）所示：

其中，m為目前節點，g為目標節點。曼哈頓正方向運動距離如圖3 曼哈頓正方向運動示意圖所示。

圖3 曼哈頓正方向運動示意圖

當無人機在路網圖中除了正方向運動外還進行對角線的運動時，可以選擇對角線為新的股價函數[6]，即如公式（4）所示：

加入無人機的正向飛行和對角線飛行的距離都為D時，則啟發式函數如公式（5）所示：

其中，m為目前節點，g為目標節點。如果對角線飛行的代價不為D而是時，因此需要計算，即沿著對角線移動的網格數為曼哈頓距離，然后將這兩項合并為一項，所有的斜線都乘以D2，剩下所有正方向飛行距離都乘以D，即如公式（6-7）所示：

因此根性對角線函數如公式（8）所示：

曼哈頓對角線距離如圖4 曼哈頓對角線距離示意圖所示。

圖4 曼哈頓對角線距離示意圖

如果無人機在路網圖中可以遵循任意角度移動時，此刻可以選擇歐使用幾里得距離進行估價距離運算，兩點間的直線距離D將如公式（9）所示：

當直線距離和對角線距離代價都為D時，則h(n)啟發函數如公式（10）所示：

由于歐幾里得的正方先于曼哈頓距離正方向代價相同，而對角線距離代價比曼哈頓距離的對角線距離代價都小，所以使用歐幾里得距離仍然可以得到最短的路徑，但是會使得A*算法運行時間更久，因此可根據使用利弊進行隨機選擇歐幾里得距離或者曼哈頓距離。

3.3 算法實現

在Python 環境下，構建一個模擬柵格圖，障礙物通過隨機生成模擬隨機存在的障礙物，導入程序運行所需要的相關數據庫如matplotlib，Rectangle，random_map，start，進行設置柵格大小，部分實現代碼如下所示：

3.4 基于A★算法路徑分析

通過使用曼哈頓距離代價進行A*算法估值運算[7]，無人機飛行距離如圖5 飛行軌跡示意圖所示。

圖5 飛行軌跡示意圖

由于在進行軌跡規劃時使用的幾何路網圖進行求解最優解，因此并沒有充分的考慮無人機的動力學和運動學，所以最后，必須要對最優軌跡進行平滑處理，以此滿足現實狀態下的無人機的機動轉向性，形成最終的無人機飛行軌跡。

由于最優路線已通過A*算法進行計算出來，所以決定通過考慮無人機的最大法向過載，來引進圓弧化思想[2]，將無人機的運動軌跡進行平滑處理，利用公式（11）對目前最優路線進行平滑處理。

其中，ny.min代表無人機的最大法向過載，Vmin代表無人機的最小速度。

4 結語

本文針對靜態目標區域進行分析規劃，使用曼哈頓距離代價進行A*算法估值運算，計算出無人機最佳路徑，但未考慮到無人機的運動學和無人機的安全性有待改善，總體來說此次的仿真模擬達到研究的目的，同時驗證A*算法規劃路徑可行性和無人機的可飛性。