移動機器人路徑規劃融合算法研究

楊偉煌,王容霞

(廣州南洋理工職業學院,廣東 廣州 510900)

0 引言

路徑規劃是機器人研究領域不可或缺的技術。所謂路徑規劃,就是讓機器人在遵循一定的評價指標函數的前提下,在充滿障礙物的環境中順利避開障礙物,從而規劃出從起始位置到目標位置的最優路徑。

由于標準A*算法需要從起點開始,不斷擴展相鄰節點,并使用定義的代價估計函數尋找使函數得到最小的節點F(m)值,所以算法的時間消耗主要在于計算相鄰節點的代價估計函數和選擇最小的節點F(m)。這樣一來,標準的A*算法就會有一些不可避免的缺陷:隨著機器人二維空間的增加,算法擴展出來的無用節點的數量越來越多,導致計算數據量和搜索時間增加算法的增加,路徑規劃效率不高。

本文將基于跳躍點搜索的jump-A*算法與全局最優的動態窗口方法相結合,提出了一種混合路徑規劃算法。一個新的參數JPHeader(v,ω),它測量模擬軌跡的末端和距離當前軌跡最近的跳躍點之間的方位角偏差,被設計來構造一個新的評估函數。該融合算法基于動態窗口方法,采用跳躍點搜索方法,規劃速度更快,避障路徑更平滑。

1 jump-A*算法

A*算法是一種啟發式搜索算法,用于在靜態二維配置空間中計算最優路徑,與A*算法不同的是,jump-A*算法引入了跳轉點的概念(見圖1)。

圖1 跳轉點搜索算法

在A*算法中,由于評估了大量無意義的節點,如灰色網格,無形中增加了計算量,降低了搜索效率。因此,假設目標位置n是當前節點x的8個鄰域中的任意一個節點n,則通過滿足約束方程,確定從起點p到目標點n直線延伸的最優路徑。當擴展的相鄰網格節點遇到障礙物時,除強制鄰居節點外,其余的灰色網格都應該被剪掉。節點X是算法中要找到的跳轉點。切掉無意義的節點后,就可以得到一系列的跳躍點。然后,可以通過在這些跳躍點上應用標準的A*算法來獲得全局最優路徑。該算法稱之為jump-A*算法[1]。

對于jump-A*算法中的距離測量方法,使用較多的是歐幾里得幾何距離或曼哈頓距離。為了便于控制機器人,結合以上兩種測量方法,設計出更接近實際估計成本h(m)的新距離函數:

假設起點和目標點的坐標為(pi,qi)和(pj,qj),那么dx(m)=|pi-pj|,dy(m)=|qi-qj|。

2 改進的動態窗口方法

2.1 傳統的動態窗口方法

動態窗口算法的核心是將路徑規劃問題轉化為約束速度向量空間優化問題。

2.1.1 機器人運動學模型

實現動態窗口法的第一步是獲得機器人的運動學模型,這也是模擬機器人運動軌跡的前提。假設機器人的軌跡由一條微小的弧形軌跡組成,每個軌跡對應一個唯一的速度向量(vt,ωt)。由于每條圓弧軌跡產生的時間間隔Δt很短,可以近似看成一條直線軌跡。因此,可以假設機器人在Δt的時間間隔內做勻速直線運動,得到機器人的運動學模型如下:

其中xt,yt,θt為t時刻機器人的坐標位置和方位角；xt+1,yt+1,θt+1為t+1時刻機器人的坐標位置和方位角；vt和ωt是機器人在時間t的平移速度和旋轉角速度。

2.1.2 速度采樣

速度采樣是模擬軌跡所必需的。在動態窗口方法中,定義了3種不同的約束來限制采樣速度的范圍。

第一個約束是受機器人所處環境和物理結構的限制。機器人可以達到的速度范圍是:

其中,vmax和vmin是機器人可以達到的最大和最小線速度,ωmax和ωmin是機器人可以達到的最大和最小角速度。

第二個約束考慮遇到障礙的情況。當機器人采用最大減速度時,v′b,ω′b緊急制動,為了使機器人在碰撞前停止并確保其安全,必須設置允許的速度范圍:

其中,dist(v,ω)表示速度向量模擬的軌跡之間的距離(v,ω)和最近的障礙物。

第三個約束是在模擬時間Δt間隔內可以達到的速度范圍,由電機允許的最大加速度v′a,ω′a和最大減速度v′b,ω′b限制:

其中vc,ωc表示機器人當前的線速度和角速度。

2.1.3 評價函數

在多組采樣速度的集合中,通過仿真可以得到多組可行的軌跡。要從這些可行軌跡中選擇最優軌跡,需要從多個維度進行評估,使機器人能夠沿著最優軌跡安全到達目標位置。評價函數如下:

其中,head(v,ω)用于測量在當前選擇的采樣速度下,模擬軌跡終點方向與目標位置方向之間的角度偏差。dist(v,ω)為速度向量(v,ω)模擬的軌跡與最近障礙物的距離,得分越低,機器人與障礙物碰撞的概率越大；σ為平滑函數。α,β,γ為3個評價指標的加權系數[2]。

2.2 改進的動態窗口方法

傳統的動態窗口方法具有良好的動態避障性能,但由于陷入局部區域無法到達目標的致命缺陷,難以根據全局環境信息規劃全局最優路徑。為了解決這個問題,筆者充分考慮了jump-A*算法得到的全局路徑信息,改進了原動態窗口方法的評價函數。改進后的動態窗口方法可以動態避開障礙物并確保其全局最優性。改進后的評估函數表達式寫為:

方程中的head(v,ω)替換為JPHead(v,ω),它測量模擬軌跡的末端和距離當前軌跡最近的跳躍點之間的方位角偏差。優化的動態窗口方法保證了在動態路徑規劃中沿著全局最優路徑的輪廓平滑的全局最優路徑。改進的動態窗口方法的流程如下:

首先初始化,獲取機器人的運動學模型,判斷是否達到了目標位置,如果達到了目標位置,那么機器人速度采樣,模擬運動軌跡,使用全局改進的評估函數,通過jump-A*算法得到的路徑信息,選擇最優軌跡,機器人按照最佳軌跡移動；以至于得到最優路徑[3]。

3 實驗與結果

為了驗證上面提到的jump-A*算法和改進的動態窗口方法的有效性,MATLAB中建立網格環境,對jump-A*算法結合跳躍點搜索和集成全局路徑信息的改進動態窗口方法進行了2次靜態仿真實驗,如圖2所示。

圖2 兩種不同算法在簡單和復雜靜態實驗環境下的仿真結果

通過仿真結果,無論是簡單環境還是復雜境與jump-A*算法相比,具有全局路徑信息的改進動態窗口方法可以解決jump-A*算法在相同網格大小和相同障礙物的轉折點處曲率不連續的問題分布環境,生成的路徑比jump-A*算法更平滑,融合算法也具有全局最優性能。無論障礙物的位置、形狀和大小如何變化,融合算法都能在滿足全局優化的基礎上規劃出更平滑的路徑。此外,改進的動態窗口方法融合了全局路徑信息,克服了原有動態窗口方法陷入局部最優的缺點,達到了該融合算法的設計預期。