基于碰撞預測的改進A*路徑規劃算法研究

陶 智 梁獻霞 路俊維 趙 慶

（1、邢臺職業技術學院信息工程系，河北 邢臺054000 2、河北機電職業技術學院機電工程系，河北 邢臺054000）

移動機器人的路徑規劃問題是當前移動機器人領域所研究的熱點問題，其主要目標是在已知、未知或者部分未知的環境中規劃出從起始點到目標點的安全無碰撞路徑。

在已知的靜態環境，所用的全局路徑規劃算法通常有柵格法、RRT 算法、A*算法、神經網絡算法、遺傳算法、蟻群算法等等。文獻[1]改進A*算法中使用了正反向搜索的機制，范圍仍然局限于靜態障礙物環境下。對于動態障礙物環境下的路徑規劃，文獻[2]采用了基本避障策略和啟發式動態規劃法相結合的思路，但是關于A*算法在動態障礙物下的路徑規劃研究文獻卻幾乎空白[1-2]。

本文結合前人的研究成果，對動態障礙物環境下的路徑規劃進行研究探討，在A*算法的基礎上進行改進，通過引入逃逸距離策略解決機器人與動態障礙物相遇的問題，并對新算法進行了仿真驗證。實驗結果表明，采用逃逸距離策略后的算法，可提高機器人路徑規劃的安全效率。

1 柵格化網絡

為了便于分析研究，將機器人、路徑系統和障礙物進行網絡柵格化處理，將不規則障礙物按照規則化處理，并設定路徑網格的最小單位正方形，單位為1cm，如圖1 所示。

圖1 環境網格

2 A*算法引入

A*算法的評價函數表示為：f（n）=g（n）+h（n）。其中f（n）是從初始站點經由當前站點到目標站點的估計值，在尋路過程中，總是選擇f（n）值最小的下一站點作為最優路徑中的站點，g（n）表示從初始站點到當前站點已經付出的代價，h（n）表示從當前站點到目標站點的估計代價。

A*算法中g（n）值由起點開始所經過的距離累加而得，h（n）值則通過距離預估方法求得，通常有曼哈頓距離或者歐幾里得距離[3-5]。

3 逃逸范圍策略

實際情況下，移動障礙物的尺寸大于機器人尺寸，并且在相互運動過程中有沖突的可能，需要設置有效避障范圍。預測機器人和動態障礙物相遇的邊界，由此確定此時碰撞的矩形范圍，機器人可以安全逃逸到達目標點，可以防止運行中被損壞。

3.1 最小矩形圖

在實際環境中，障礙物有規則和不規則形狀，為了方便處理，提出了最小矩形圖的概念，即能夠正好將整個障礙物包括在內的矩形，如圖2 所示的障礙物都包含在長10cm 和寬為4cm 的矩形框內。

圖2 中凸形障礙物

3.2 逃逸范圍數學建模

假設機器人車體r，移動速度為vr，機器人坐標為r（rx, ry）。動態障礙物為o，運動速度為vo，障礙物的坐標為o（ox, oy），其橫向長度為oh，縱向長度為ow，且在運動過程中不改變方向，機器人與障礙物的運動夾角為θ。

在沒有遇到障礙物的情況下，機器人r 搜索路徑的方向夾角為θ，因此機器人r 移動到障礙物o 邊界的橫向距離等同于縱向距離，可以推出此時機器人的坐標為（ox，ry+ox-rx），固逃逸范圍是以（ox，ry+ox-rx）為坐標，橫向長度為oh，縱向長度為ow的矩形。同理可以根據移動機器人r 和動態障礙物o 的相對位置和運動方向推出機器人r 移動到障礙物o 右邊界和上下邊界時的逃逸范圍[6]。

3.3 逃逸范圍計算模型

本文只考慮單動態障礙物的情況，對不規則的動態障礙物做了柵格化處理，統一為最小矩形圖。機器人和障礙物在協同運動過程中可能同時占用路徑網格資源[7-8]。圖3、圖4、圖5 和圖6 展示了在柵格型路徑運動過程中可能出現的沖突類型。

當機器人移動到邊界逃逸范圍，即計算逃逸范圍，其確定的方法，不同方向運動的計算各有差異，概括為四種情況，分別討論如下[9-10]。

（1）機器人r 和障礙物o 右斜向相向運動

圖3 右斜向相向運動逃逸

圖4 左斜向相向運動逃逸

圖5 左斜向反向運動逃逸

圖6 右斜向反向運動逃逸

3.4 改進A*算法流程

引入逃逸范圍策略，改進后A*算法的整體流程如圖7 所示[11-12]。

其算法的流程可以簡述為：

（1）加載路徑網格坐標信息；

（2）判斷有無障礙物，有則判斷障礙物的狀態，如果是動態，則執行改進A*算法，否則執行固有的A*算法；

（3）如果沒有障礙物，則直接計算路徑長度；

（4）更新機器人的坐標位置，并判斷是否到達目的坐標，如果沒有，則循環執行（2）、（3）和（4）步驟，否則，循環終止，流程結束。

圖7 路徑規劃算法流程

4 實驗結果分析

圖8 斜向相向運動

不考慮障礙物之間的碰撞，且機器人和障礙物的移動速度均為勻速。網格中紅色方框代表目標點，黑色邊框代表動態障礙物的移動軌跡，黑色箭頭表示障礙物的移動方向，綠色方框表示機器人的移動軌跡[13]。實驗模擬對比了斜向相向運動情況下A*算法和改進A*算法后的情況，圖8 中的（a）表示機器人r和障礙物o 剛好邊界相遇的狀態，（b）表示設置邊界逃逸范圍后的運動情況。

5 結論

通過改進A*算法，引入逃逸范圍策略，通過對比仿真實驗，證明此策略可以有效防止機器人與動態障礙物發生碰撞，避免了造成機器人的損傷，可以安全到達目標點。

本文探究了單動態障礙物下，機器人的路徑規劃，改進算法具有優越性，對于復雜環境中的多動態障礙物，以及多動態障礙物和靜態障礙物同時存在的情況，將是下一步要研究的方向。