基于蟻群粒子群融合的多機器人協同路徑規劃算法

黃 駿，朱 強

(蕪湖職業技術學院 智能制造學院，安徽 蕪湖 241006)

隨著科技的不斷發展，智能機器人被應用到工業、物流業、電力行業等越來越多的領域。規劃科學合理的避障路徑是決定智能機器人作業效率及作業執行效果的關鍵[1]。多機器人在協同作業過程中，易發生相互碰撞，極大影響作業效率。李洋等[2]基于自適應步長快速擴展隨機樹的方法提出了一種雙臂機器人協同路徑規劃算法，提高了碰撞檢測的有效性。董朝瑞等[3]設計了一種基于預約格柵方法的多機器人動態路徑規劃算法，提高了倉儲機器人協同作業的系統效率。彭湘等[4]通過引入半自由柵格和半障礙柵格概念，融合蟻群算法得到了多地形情況下移動機器人的最佳路徑規劃。劉劍等[5]以揀貨智能機器人為研究對象，結合所設定的能耗與移動間距等目標函數，構建出3層布谷鳥模型，進而得到機器人協同路徑規劃。該方法雖然可以快速得到不同類型食品揀貨機器人規劃作業路徑，卻不能完全避免機器人間的碰撞，協同規劃效果不佳。萬逸飛等[6]以降低機器人運行耗時、提升路徑平滑度等為研究目標,采用多目標及協同算法,對多目標函數的協調路徑規劃問題進行求解,得到了多機器人協同路徑規劃。此方法所規劃的協同路徑雖然在避障與避碰撞方面均表現良好,但所用算法的運算過程過于煩瑣,整體規劃效率較低。

粒子群算法是通過對鳥群搜索食物的過程實施仿真而產生的一種全局性優化算法，該算法具有搜索速度快、全局搜索性能強、平穩性好等特點，但針對組合優化問題的處理效果稍差[7]。而蟻群算法是通過對蟻群搜索食物的過程實施仿真的一種算法，同時也是一種通過概率搜索最優路徑的啟發式全局優化算法。該算法搜索最優路徑時主要依據路徑的信息素與啟發函數2種參數值[8-9]。蟻群算法具有收斂性能好、魯棒性及搜索準確性高等特點，尤其適用于處理組合優化問題，其缺點主要為搜索效率稍差、運算量高、易陷入局部最優等[10]。為此，本研究通過融合粒子群算法與蟻群算法，獲得蟻群粒子群融合算法，在暫不考慮機器人間干擾的情況下，確定各機器人全局最優避障路徑，再結合多機器人協同作業避碰規則，規劃出免碰撞的最佳機器人間協同路徑，為多機器人協同作業效率與安全性的提升提供保障。

1 多機器人協同路徑規劃算法

多機器人協同路徑規劃要解決的主要問題是避障路徑規劃和協同作業避碰，最終獲得可避障與避碰的多機器人最優協同路徑。

1.1 多機器人協同作業的環境建模與機器人約束條件設定

1.1.1 建立多機器人協同作業環境的柵格模型

在規劃多機器人協同路徑之前，先選用柵格法構建多機器人協同作業環境模型[11]。在建模之前，對相關條件進行設定：

1)各機器人均以1.18 m/s的速度移動；

2)機器人的實際規格不予以考量；

3)以各個柵格的中點坐標作為各自柵格的坐標；

4)當障礙物的大小小于單個柵格時，也視其為一個柵格；

5)機器人的作業運動環境為二維空間。

按上述設定條件創建多機器人協同作業環境柵格模型，其結構如圖1所示。

在圖1中，白色柵格與黑色柵格分別代表自由區域與障礙物區域，各機器人作業運動時需避開全部障礙物區域，在自由區域內完成作業運動。其中，柵格j與二維空間內的坐標(xj，yj)相對應，將柵格空間內按著橫、縱坐標方向的行、列柵格數量設定為Mx與My。將圖內左上角第1個柵格設定為首個柵格，其坐標為(0.5,5.5);將首個柵格右側的柵格依次設定為柵格2～6,并按條件設定柵格的坐標。每個柵格坐標同其序號之間的關聯式為

(1)

式中,mod(j/Mx)與cell(j/My)分別為j/Mx的余數和j/My的整數。

柵格經過二維平面化處理后,經由各機器人自身傳感器實時采集作業環境信息,通過膨化操作處理作業環境內的各個障礙物,令其占據若干個柵格[12-13]。設Ai(x0,y0)與Qi(x1,y1)為第i個機器人的運動初始點與終點坐標,以柵格信息為依據,在兩點之間為機器人查詢符合約束條件的最佳路徑。按此方法獲取全部機器人的最佳路徑。

1.1.2 設定機器人約束條件

在規劃機器人路徑的過程中，需設定位移、避障、結束運動等約束條件[14]。設Bi為第i個機器人的路徑，它包含多個柵格序號，即Bi=(bi1，bi2，…，bik)，其中，k為路徑中的總柵格數。該機器人最短路徑長度Di為

(2)

式中，n為機器人的總數量。

機器人約束條件設定如下：

1)位移約束條件：此約束條件是對機器人的運動方向實施約束，設定其僅可朝向左、右、前、后4個方向產生平面位移運動與暫停，且單次位移運動只能選擇一個方向。約束條件表示為

(3)

式中：(xc，yc)為機器人行走至第c步時所對應的坐標，l為常數。

2)避障約束條件：該約束條件是對機器人距障礙物的間距實施約束，約束條件表示為

(4)

式中，(xe，ye)為障礙物柵格的坐標。

3)結束運動約束條件：該約束條件約定機器人抵達目標點時才可以結束路徑的搜索。約束條件表示為

(5)

由公式(2)可知，如果機器人由c-2步至c-1步的過程中所行走的步數為1，且不考慮是向前還是向后運動，那么，當機器人由c-1步至c步時，既能夠待在原地不動(也就是步數為0)，也能夠繼續運動1步。但是，如果機器人由c-2步至c-1步的過程中的步數為0時，即機器人待在原地不動，則此時機器人留在此處。

1.2 基于蟻群粒子群融合的多機器人避障路徑規劃過程

1.2.1 粒子群算法下多機器人最優參考路徑預規劃

初始階段任意分布在解區間的一組粒子構成了算法的起始狀態，其作用是為了提高后續迭代的效率及效果。在通過粒子群算法預規劃各機器人最優參考路徑過程中，可采取對各粒子的速度與位置持續更新的方式獲得最優解，即各機器人的最優參考路徑。粒子位置與速度更新的表達式為

(6)

式中:Xij(t)為第(i,j)個粒子的初始位置,Xij(t+1)為t+1時刻更新后的位置;Vij(t)與Vij(t+1)為粒子的初始速度與更新之后的速度;μ為加權系數;σ1與σ2為學習因子;rand(·)為隨機數,且其取值范圍為(0,1);hB與Bi j,B分別為當前粒子群的全局最優解與第(i,j)個粒子的最優解。

在建立的柵格模型內,確定障礙物、終點、初始點的坐標,并將各粒子視為對應機器人,對全部粒子的位置與速度、粒子群算法的各參數均進行初始化處理。運用公式(6)持續更新各粒子的位置與速度,連續迭代至最高迭代次數,μ值緩慢降低,實現全局最優解及個體最優解的反復更新調整。得到的最優解即為各機器人的最優參考路徑,從而完成了各機器人的路徑預規劃。

1.2.2 蟻群算法下多機器人全局最優避障路徑

(7)

在規劃路徑過程中，螞蟻柵格路徑的啟發函數和信息素濃度這2類參數值可正向決定螞蟻選擇此柵格作為可行柵格的概率。在初始柵格處放置螞蟻，在公式(7)的基礎上，螞蟻由所處柵格j向之后柵格j+1運動的概率Pj+1的計算公式為

(8)

式中：δj為啟發函數，γ為期望啟發因子，Ji為螞蟻所處柵格j的全部后續可行柵格集合，m為該集合的總數量。由此，2個柵格之間路徑的啟發函數δj，j+1的計算公式為

(9)

式中：Lj，j+1為所處柵格j與可行柵格j+1的間距，ω1為Lj，j+1的權重系數，Lj+1，Q為可行柵格j+1距目標柵格Q的距離，ω2為Lj+1，Q的權重系數。

(10)

(11)

最佳路徑上的信息素濃度與迭代次數成正比關系，當達到最高迭代次數之后，結束路徑搜索過程，確定全局最優避障路徑。

1.3 基于作業避碰規則的多機器人協同路徑規劃

為有效防止各機器人相互之間的碰撞，需進一步規劃出多機器人協同避碰路徑，實現多機器人的協同作業。為實現此目標，需設定多機器人協同作業避碰規則[15]，并以此規則得到最佳或者接近最佳的路徑組合，即多機器人最佳協同路徑，最終實現多機器人協同路徑規劃目標。

(12)

由此，根據式(2)可完成多機器人協同路徑規劃。

2 實驗仿真與結果分析

以某變電站的多個智能巡檢機器人為例，運用本文所提算法對此類機器人巡檢作業中的協同路徑實施規劃，通過規劃結果檢驗本文所提算法的實際應用性能。

從該變電站的智能巡檢機器人中抽選出2個尺寸規格相同的機器人A和B,在MATLAB 2017軟件環境下進行仿真實驗,實驗關鍵參數設定見表1。

表1 實驗關鍵參數設定

在上述實驗條件下,先通過本文所提算法創建2個實驗機器人協同作業環境的柵格模型(圖2)。

2.1 路徑規劃效果測試

使用本文算法中的基礎粒子群算法預規劃出各機器人的最優參考路徑。預規劃效果如圖3所示。

注：灰色柵格—機器人的初始點與目標點；灰色實線—機器人A的路徑；黑色虛線—機器人B的路徑。

以路徑預規劃結果為基礎，繼續融合蟻群算法繼而獲得各機器人的全局最優避障路徑，結果如圖4所示。

由圖3和圖4可知，預規劃最優參考路徑與全局最優避障路徑均能夠有效避開所有障礙柵格，但預規劃的2個機器人的最優參考路徑的長度均高于融合蟻群算法規劃所得的路徑?？梢?，本文所提算法規劃所得的最優避障路徑更為理想。

由于運用本文所提算法所得的2個機器人全局最優避障路徑存在重合碰撞路徑，所以依據作業避碰規則得到2個機器人的最終協同路徑規劃結果(圖5)。

由圖5可知,運用本文所提算法最終得到的2個機器人協同路徑中,通過令機器人A在黑色實線路徑上[坐標范圍為(14.5,13.5)～(16.5,13.5)]折返一次,可將2個機器人的重合碰撞路徑消除掉,同時未改變最優路徑,從而實現了多機器人協同路徑規劃。

2.2 耗時測試

為進一步檢驗本文所提算法的綜合性能，對規劃過程中各階段的耗時進行統計，結果見表2。

表2 規劃過程中各階段耗時統計結果 單位：ms

由表2可知，本文所提算法對2個機器人路徑規劃的整體耗時結果相差不大，且平均耗時低于200 ms。

3 結語

在多機器人共同作業情況下，科學合理的多機器人協同路徑是保障作業效率與效果的關鍵。本文以粒子群算法預規劃所得最優參考路徑作為蟻群算法的信息素加強值，實現了多個機器人最優全局避障路徑的規劃；在此基礎上，為避免協同作業時多個機器人之間產生的相互碰撞，引入作業避碰規則，消除了各機器人協同作業時的碰撞路徑，獲得了最終多機器人協同路徑。實驗仿真結果表明，本文所提算法規劃效率較高，能保障多機器人協同路徑規劃的時效性，綜合性能表現較好。