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

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

（杭州師范大學(xué)錢江學(xué)院，杭州310018）

0 引言

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

1 MALAB建模

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

通過讀取模型的外形數(shù)據(jù)得出以下結(jié)果。圖1 為路空兩用無人機MATLAB 建?？臻g結(jié)果。

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

本次無人機路徑規(guī)劃所采用的是路空兩用無人機在傳統(tǒng)無人機基礎(chǔ)結(jié)構(gòu)上改良具備輪動、爬樓與飛行模式。傳統(tǒng)四旋翼無人機由于工藝與技術(shù)限制，其受外界如大風(fēng)、地形等影響較大。本無人機在硬件設(shè)計方面，通過齒輪傳動，實現(xiàn)旋翼槳距距離、角度與位置的自由變化。提高了無人機在樓巷、叢林等狹小涵道與大風(fēng)環(huán)境中的穩(wěn)定性。內(nèi)置的無刷電機調(diào)整轉(zhuǎn)速，完成爬升、降落、轉(zhuǎn)向多姿態(tài)變換。在無人機控制硬件方面：采用模塊化架構(gòu)形式，搭載Arduino2560 微型控制板，通過數(shù)據(jù)傳輸模塊、電機驅(qū)動模塊、飛行控制模塊、六軸運動模塊、GPS 模塊、電子羅盤、氣壓計七大部分組成[3]。GPS 與電子羅盤雙位置傳感器的設(shè)置，有效提高了飛行需求。其中USV 攝像頭收集外界圖像，OpenCV 完成數(shù)據(jù)處理，基于A*算法完成路徑的規(guī)劃[4]?？梢詰?yīng)對復(fù)雜的環(huán)境?？烧郫B并且結(jié)構(gòu)簡單，重量適中的特點也使其易于攜帶。

2 柵格模型的建立

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

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

3 A＊算法路徑規(guī)劃

3.1 A★算法原理

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

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

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

3.2 利用A★算法模擬路徑

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

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

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

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

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

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

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

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

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

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

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

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

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

3.3 算法實現(xiàn)

在Python 環(huán)境下，構(gòu)建一個模擬柵格圖，障礙物通過隨機生成模擬隨機存在的障礙物，導(dǎo)入程序運行所需要的相關(guān)數(shù)據(jù)庫如matplotlib，Rectangle，random_map，start，進行設(shè)置柵格大小，部分實現(xiàn)代碼如下所示：

3.4 基于A★算法路徑分析

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

圖5 飛行軌跡示意圖

由于在進行軌跡規(guī)劃時使用的幾何路網(wǎng)圖進行求解最優(yōu)解，因此并沒有充分的考慮無人機的動力學(xué)和運動學(xué)，所以最后，必須要對最優(yōu)軌跡進行平滑處理，以此滿足現(xiàn)實狀態(tài)下的無人機的機動轉(zhuǎn)向性，形成最終的無人機飛行軌跡。

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

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

4 結(jié)語

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