復雜環境中煤礦智能機器人巡檢路徑動態規劃

閆萍

(開灤(集團)有限責任公司，河北，唐山 063018)

0 引言

隨著工業自動化水平的不斷提高，智能機器人在煤礦勘測、運輸與救援等方面發揮著越來越重要的作用[1]。在復雜的礦井環境中，機器人依靠自主導航技術實現自由運動，因此該技術中的路徑規劃算法決定了智能機器人的移動路徑的合理性和移動效率[2]。傳統的動態窗口算法雖然應用較為普遍，但其所規劃的路徑較長，規劃速度較慢且實時性較差，嚴重影響了機器人的工作效率[3]。為此，提出了一種負載環境中煤礦智能機器人巡檢路徑的動態規劃算法，通過空間粒子最佳位置的選取確定下一時間段機器人的最佳移動速度，從而有效提高了智能機器人在復雜環境中所規劃移動路線的合理性。

1 DWA算法原理

對于智能機器人在所處環境中的運動方式，傳統DWA動態窗口法(Dynamic Window Approach)的驅動原理是根據機器人的具體位置和移動速度設定范圍，將其路徑規劃過程轉換為對移動速度進行選擇的過程，以最合理運動軌跡下的移動速度作為決定下一個時間段驅動力大小的依據[4]。

首先，機器人依據整體運動環境和自身移動速度的限制來約束采樣速度。其速度的設定區間[5]如式(1),

Va={(v,ω)|0≤v≤vmax,-ωmax≤ω≤ωmax}

(1)

式中，v，ω分別表示機器人移動過程中的線速度和角速度，vmax，ωmax則分別表示線速度與角速度的最大值。

在不同大小的驅動力矩作用下，機器人的加減速度也被限制在一定范圍內，因此，在長度固定為θt的間隔時間段內，機器人最高移動速度的變化區間為式(2),

Vg=(v,ω)=

(2)

為了避免機器人在移動過程中與障礙物發生碰撞，必須保證機器人在接近障礙物之前即停止運動，在此條件下其移動速度限定區間[6]表述為式(3),

(3)

式中，dist(v，ω)代表當前規劃路徑上障礙物與機器人之間的距離。

綜合以上速度約束條件，機器人的移動速度集合應為式(4),

Vf=Va∩Vg∩Vz

(4)

完成速度采樣，然后在以上速度集中以固定的行進速度進行采樣，通過評價函數對采樣效率進行評價為式(5),

(5)

式中，heading(v，ω)表示機器人在當前采樣速度下移動至某一段規劃路徑的端點時機器人行進方向與整條路徑終點之間的角度差，velocity(v，ω)表示從采樣速度中提取的線速度，a，β，γ均為權值參數，為了使三者的中權重較為接近以保證評價質量，在進行速度評價之前對它們進行歸一化處理，使其數值落在[0，1]區間內。

在a=0.4，β=0.2，γ=0.4的條件下，利用評價函數H對機器人的移動速度集[(0,2)m/s，(-50,50)rad/s]進行評價，H值最大時所對應的(v，ω)便可作為下一個時間段機器人的移動速度。通過DWA算法獲取的機器人規劃路徑如圖1所示。圖1中圓形與正方形黑色物體為路徑上的障礙物。由圖1中的軌跡可見，當障礙物分布較為密集時機器人智能繞開該區域，由此增加了機器人運動路徑的總長度。

圖1 通過DWA算法得到的機器人規劃路徑

2 算法優化設計

利用上述評價函數對速度采樣空間進行評價是一個較為漫長的過程，因此，在復雜的環境中，基于DWA算法的機器人行進路徑過長，且機器人規劃路徑的效率很低，不能及時獲取最優速度，造成環境中存在障礙物密集分布區域時機器人無法規劃出合理的行進路徑。本文基于膜計算(Membrane Computing,MC)和粒子群(Particle Swarm Optimization,PSO)的MCPSO-DWA算法對傳統DWA算法進行優化，縮短機器人的行進路程，提高其工作效率。

2.1 設計思路

首先將機器人的移動速度空間Vf轉換為以線速度v為橫坐標、角速度ω為縱坐標的二維坐標空間[6]，轉換后的坐標空間如圖2所示。其中，(vmin，vmax)與(-ωmax，ωmax)分別表示機器人的移動速度約束范圍，陰影區域S表示機器人的速度限制區間。在這里引入粒子群算法，那么S就對應成為算法中的粒子搜索區間，而(vmin，vmax)以及(-ωmax，ωmax)則對應該區間的邊界，S中的任意一點(v，ω)對應粒子在坐標空間中的位置X。在坐標空間中X持續更新，最后依據最優粒子的位置得到最優移動速度(v，ω)。

圖2 速度限制坐標空間

構建一個由m個基本膜和1個表層膜所組成的單層膜。在速度限制區域S中提取出Q個粒子，其中每個粒子的位置都對應一個機器人在某個時間段內的移動速度(v，ω)，粒子位置與移動速度的原始表達式分別為式(6)和式(7)。

X=[(vmax,ωmax)-(vmax,-ωmax)]×r+(vmax,ωmax)

(6)

V=[(vmax,ωmax)-(vmin,ωmin)]×0.1×(2r-1)

(7)

式中，r為一個隨機數，其取值區間為[0,1]。

將Q個粒子等分為m份(每份粒子數量為D)并注入每個基本膜中，設包含在第k(k=1，2…，m)個基本膜中的第d(d=1，2…，D)個粒子的初始位置為Xkd，初始速度為Vkd，通過式(5)評價基本膜中的粒子，依據評價函數值找到每個基本膜中的最優粒子，再將m個最優粒子發送到表層膜進行對比，由此得到整個粒子群中的最優粒子，表層面將該粒子信息返回給各基本膜，基本膜中的粒子參照群中最優粒子的位置和速度進行更新，以此形成整個粒子群的反復迭代更新，直至得到最優粒子位置，即可確定機器人在下一個時間段內的移動速度。在每一個固定間隔的時間段內機器人都以最優速度行進，直至到達路徑終點。

2.2 算法實現流程

本文所提出的改進后的算法實現流程如下。

步驟一：智能機器人依據自身的驅動能力和所在環境的復雜性設定速度限制區間Vf。

步驟二：完成速度限制區間向二維坐標區間的轉換。

步驟三：構建單層膜，從限制區域S中提取出Q個粒子，通過式(6)和式(7)計算粒子的位置和移速，等分到各基本膜中，在這里需要分別對迭代次數N、慣性權重ωmin和ωmax、學習因子c1和c2、適應度函數闕值δ進行設置[7]。

步驟四：利用式(5)對各基本膜中的粒子進行評價，得到所有粒子的適應值H0kd，即粒子在基本膜中的歷史最優評價分數Pkdbest，將所有粒子的Pkdbest進行對比，得到最高評分的即為該基本膜中的最優粒子Gkbest。

步驟五：按照既定規則Rk將各基本膜中的Gkbest發送到表層膜并互相進行比較，其中評分最高的即為粒子群中的最優粒子Gbest。

步驟六：按照既定規則R′k將Gbest信息返回給各基本膜，膜中的各個粒子按照式(1)和式(2)進行位置和速度的更新。

步驟七：再次對基本膜中的粒子進行評價，更新Pkdbest和Gbest，得到較之前更優的粒子。

步驟八：通過反復迭代持續更新粒子群，直到迭代到第N次或Gbest的適應值為δ，依據當下時刻Gbest粒子的坐標值得到機器人在下一個時間段內的移動速度[8]。

步驟九：機器人按輸出的速度行進并判斷是否已到達路徑終點，若已到達則停止行進，反之則由步驟一進入下一個時間段移動速度的計算流程[9]。

算法流程見圖3。

圖3 算法流程圖

3 實驗及結果分析

為了驗證本文所提出算法的有效性和性能優勢，在復雜程度不同的多種環境中將本文算法與傳統DWA算法的性能進行對比，考察煤礦智能機器人的行進路程長度、行進時間和穿越障礙物密集分布區域的能力。

3.1 實驗參數

仿真實驗在Python3.7軟件環境中進行，機器人的工作環境按圖2的形式設定。本文所提出算法的具體參數設定如表1所示。從速度坐標區間的粒子群中提取出20個粒子，基本膜數量為4個，每個基本膜中分配5個粒子。傳統DWA算法的具體參數設定如表2所示，障礙物半徑設定為0.5 m。

表1 本文算法的參數設定

表2 參數設定

3.2 實驗結果與分析

首先在復雜程度不同的4種環境中驗證本文算法MCPSO-DWA的性能，環境復雜度由低到高，其中的環境3和環境4障礙物分布密度較大(障礙物8個以上)。機器人在上述各種環境中分別基于DWA算法和本文算法所規劃出的最優路徑如圖4所示。由圖4(a)和圖4(b)可見，在相對簡單的環境中，通過2種算法所規劃的路徑都能從障礙物間穿過，路徑都較為合理且長度基本接近。而在圖4(c)和圖4(d)所示的復雜環境中，本文算法所規劃的路徑能夠使機器人安全穿越障礙物，相較于DWA算法明顯更為合理。

2種算法下規劃路徑的分段數量和每一段的評價次數如圖5所示。由圖5(a)和圖5(b)可見，在環境1和環境2中DWA算法所規劃的路徑分段數分別為58個和75個，結合表2中設定的參數，每一段都會完成800次評價；在同樣環境中本文算法所規劃的路徑分段數分別為64個和70個，每一段都的評價次數為粒子群算法中G best的適應值為(時迭代次數與粒子數量的乘積。由圖5(c)和圖5(d)可見，在環境3和環境4中法所規劃的路徑分段數分別為76個和124個，相比DWA算法分段數量有所減少，可見本文算法能夠提升機器人的行進速度。

本文算法的路徑分段數量與每一段迭代次數的關系如圖6所示。由圖中的折線形式可見，在環境1和環境2中本文算法每一段路徑的迭代次數范圍為5-30，結合圖5(a)和圖5(b)可得每一段得評價次數為100-600，均少于DWA算法對應的數值。在環境3和環境4中,本文算法每一段路徑的迭代次數范圍為10-35，結合圖5(c)和圖5(d)可得每一段的評價次數為200-700，均少于DWA算法對應的數值。

通過2種算法所獲取的規劃路徑的具體數據如表3所示。表中數據顯示，在最簡單的環境1中，本文算法在總行進時間和路徑分段數量上與DWA算法較為接近，但路徑總長度相較于DWA算法縮短了8.77%；環境2和環境3的復雜度有所增加，本文算法規劃路徑所需的時間比DWA算法分別減少了8.66%和15.53%，同時規劃路徑總長度也縮短了2.3%和6.71%；在最為復雜的環境4中，本文算法的路徑分段數量比DWA算法少41個，規劃耗時減少了31.55%，路徑總長度縮短了10.02%。

表3 2種算法所得規劃路徑具體數據

(a)環境1

(a)環境1

圖6 本文算法下路徑分段數量與評價迭代次數的關系

在4種環境中機器人的移動速度統計如圖7所示。由圖7可知,在最簡單的環境1中，2種算法下機器人的行進速度存在一定差距，DWA比本文算法快0.12 m/s；但隨著環境復雜程度的增加，在其余3種環境下均是本文算法的行進速度更快，分別比DWA算法快出0.05 m/s、0.08 m/s、和0.19 m/s，說明本文算法在復雜環境種比DWA算法擁有更高的行動效率。

圖7 2種算法下機器人的移動速度

在障礙物呈U型分布的環境中，基于其它算法智能機器人所規劃的路徑常常被阻斷，現有研究結果表明，A-DWA(Adaptive-DWA，自適應DWA)算法[10]具有適應性強、路徑規劃高度合理的特征，為了進一步驗證本文算法MCPSO-DWA的性能優勢，在包含U型分布障礙物的環境中對本文算法、A-DWA算法與DWA算法規劃的路徑進行對比，3種算法的規劃結果如圖8所示。

圖8 包含U型分布障礙物環境中3種算法規劃的行進路徑

由圖8可見，A-DWA算法和DWA算法均與障礙物發生碰撞，機器人的行進路徑被中斷，而本文算法則能夠成功引導機器人繞過U型障礙物分布區域并最終到達目的地。由此可以證明本文算法能夠滿足引導智能機器人在高度復雜的環境中規劃合理行進路徑的需求。

4 總結

為了解決基于傳統DWA算法的煤礦智能機器人在復雜環境中所規劃的行進路徑不合理、工作效率較低的問題，提出了一種優化的動態規劃算法MCPSO-DWA，將機器人的速度限制空間轉換為能夠標示粒子位置的二維坐標空間，引入粒子群算法在膜計算中優化了機器人移動速度的限制區間，有效提高了機器人路徑規劃的合理性和規劃效率。通過仿真實驗證明，本文所提出的算法相較于其它同類算法具有明顯的性能優勢，適于在煤礦智能機器人的自主導航系統中應用和推廣。