針對多障礙陸戰場路徑規劃的改進A*算法研究

張明路，沈祺宗，高春艷，李滿宏

（河北工業大學機械工程學院，天津 300130）

1 前言

在多障礙陸戰場環境中，路徑規劃[1]即為在存在障礙物的前提下，利用柵格法等方法構造地圖，根據搜索算法（A*[2]，D*[3]，遺傳算法[4]，蟻群算法[5]等）生成從初始節點到目標節點的最優路徑。其中A*算法作為靜態啟發式算法，更適合處理復雜障礙，并且它在解決靜態全局規劃問題時還具有參數少、效率高等優點。

文獻[6]提出利用微分改進A*算法，有效降低了轉折次數，但是涉及了大量計算；文獻[7]一種改進的D*LIte算法—Field D*，對柵格進行線性插值使路徑點不局限于柵格點中心，搜索方向也不再受限于π4整數倍；文獻[8]則將該線性插值法應用于A*中，但是需要對柵格地圖進行定義修改。因此提出一種將A*算法與元胞自動機[9]相結合的路徑規劃算法，改進估價函數使當前點可以直連擴展Moore的第二層鄰域任意點，然后在依據通行性判定規則，繼續修改估價函數，添加多組限制條件，進行第二通行次可行性鄰域判定，從而對路徑的可行性提供優化。

該混合方法不但減少了路徑長度與轉向角度，同時能在復雜環境中滿足障礙物回避[10]。

經仿真驗證，路徑滿足陸戰場行軍靈活性的要求，具有可行性與有效性。

2 A*算法改進

2.1 傳統A＊算法

傳統A*算法屬于全局路徑規劃，利用從初始狀態和當前狀態到目標狀態估計所需的費用等信息，在選擇下一個節點時對當前結點距離終點的距離作出估計。

設計估價函數是A*算法的核心，本實驗估價函數參考歐幾里得距離估價法，假設起點S的坐標（Hx，Hy），終點G的坐標（Mx，My），中間點N的坐標（Nx，Ny），則歐幾里得距離表示為：