多移動機器人路徑無障礙智能規劃算法仿真

熊 焰,劉金庫

(華東理工大學工程訓練中心,上海 201424)

1 引言

物流行業在社會運行中地位與日俱增,促使移動機器人技術得到了迅速地發展。基于移動機器人自帶的導航定位功能,人們得以在倉儲物流的過程中大幅度增加工作效率,減少不必要的人力勞動。但是當倉儲環境較為復雜或者移動機器人的數量過多時,機器人總是會發生無意識的碰撞,導致無法順利完成倉儲物流的任務,為此對復雜環境下的多移動機器人路徑規劃進行設計與研究。

文獻[1]設計了一種結合預測與模糊控制的移動機器人路徑規劃算法,針對復雜未知環境下的路徑冗余問題以及局部障礙問題,將障礙躲避控制在一個較為模糊的區間內,設定轉角累加以及優勢判斷,輔助移動機器人擺脫角落鎖死的困境,并在一定程度上減少冗余路段,提高運行效率。該方法主要用于避免移動機器人在復雜路徑內,難以準確到達目的地的問題,強化路徑規劃的穩定性,但是其應用的優越性不明顯。文獻[2]提出了一種改進的A～*算法以及動態窗口算法相結合的混合路徑規劃方法,可以同時對多個移動機器人進行實時路徑規劃,這樣的算法運算效率極快,并且可以多線程同時工作,具有極大的現實意義,然而其運行結果的優化性較差。文獻[3]有效地提高了移動機器人在路徑規劃過程中的自適應權重,減少了機器人的移動距離,引入改進灰狼優化算法,更新種群位置,平衡收斂速度,約束了機器人行走的路徑長度,提高了全局優化的效率。然而該方法只適用于單一機器人的路徑規劃,無法對多個移動機器人進行綜合性的路徑設計,容易造成機器人碰撞,進而導致物流無法順利進行。基于以上文獻,對復雜環境下的多移動機器人路徑路徑無障礙規劃實現優化設計,并進行仿真測試。

2 復雜環境多移動機器人路徑無障礙規劃方法

2.1 群體智能路徑規劃優化算法設計

移動機器人在復雜環境內完成路徑規劃的本質為:將所處環境變為已知環境,同時逐步迭代計算不同的路徑長度,并注意比較路徑長短。其中最短的一條路徑就是該算法下移動機器人的路徑規劃設計。而多移動機器人的路徑規劃,則需要綜合考慮所有機器人的路徑,從單一的路徑計算,轉變為群體性的規劃設計,通過蟻群算法,可以實現啟發性的隨機智能搜索。算法中的每一個個體在面臨位置選擇時,都需要向不同的方向移動,而在障礙區域內,障礙物就起到了一個約束的作用,使個體不會向障礙阻隔的方向移動。其中的最優解即表示不限定路徑的前提下,機器人在可行解的空間內反復迭代的最大值[4]。如果運算量過大,則容易造成路徑冗長的現象,此時就需要對其進行簡化處理。在設計群體性的智能路徑優化時,算法內應該設置禁忌表,進行隱式的通信,通過引導路徑規劃的倒數值,將啟發式因子參數與信息素相結合,得到啟發因子比重的更新函數

(1)

式中,Hk(t)表示t時刻內機器人可移動的位置集合;i、j分別表示機器人移動的起始點位置與終點位置;δij(t)表示t時刻內從位置i到位置j的信息素濃度;kp表示期望啟發式的因子參數;μij(t)p表示t時刻機器人的下一個可移動位置;d表示可移動位置的數量[5]。當算法完成第一次探索之后,需要根據各路徑上的信息素濃度,對路徑進行比較,去掉不合適的路徑后,繼續更新參數

(2)

式中,δij(t+1)表示下一步的機器人可移動位置。若在某一時刻,算法中的機器人進入了路徑的死角,則需要針對全局路徑中的信息素進行穩定性優化[6,7]。通過迭代抽樣的方式進行最優路徑的局部最優采樣,局部采樣公式為

(3)

式中,hk表示路徑信息素采樣的周期。通過該公式,可以得到一個有助于多個移動機器人進行路徑規劃的算法。

2.2 計算多移動機器人碰撞風險

從起點到達最終點,需要保證機器人不與復雜環境內的任何物體相接觸,其中包括路障和另外的機器人,因此在保證移動機器人安全的前提下,需要根據時間與空間的差異,設置移動路徑。其中,當路徑與障礙物不存在重疊情況時,公式為

(4)

(5)

式中,hi,j表示第i個移動機器人在位置為j時的安全情況;p表示該位置點是否為障礙點。在考慮路徑安全性的前提下,計算碰撞風險函數,可以得到公式

(6)

式中,G(fc,fs)表示機器人移動的位置與障礙物位置的相對距離;δ表示障礙物的影響距離[8]。在機器人與障礙物之外,還需要建立移動機器人工作空間的二維模型。空間中的任意一點都存在慣性坐標系以及旋轉坐標系之間的轉換關系,以此建立矩陣

(7)

式中,(x1,y1)表示空間中移動機器人的起始點;(x2,y2)表示空間中移動機器人的終點;α表示慣性坐標系轉換后的角度。據此生成多個機器人行駛過程中碰撞的風險

(8)

式中,hma,ka和hmb,kb分別表示復雜環境內機器人a與機器人b在第m條路徑的第k個行駛操作;dha表示機器人a在該條路段與的存在形式;dhb表示機器人b在該條路段的存在形式;vh表示機器人的統一形式速度;f(p)表示機器人之間碰撞的危險度函數[9]。通過式(6)以及式(8)可以分別計算多移動機器人在環境內形式與障礙物以及其它機器人碰撞的風險。

2.3 智能規劃多移動機器人最短無障礙路徑

在復雜環境下,需要針對以上算法以及碰撞風險的公式,智能規劃多移動機器人的最短無障礙路徑,即遍歷在不與其它障礙物以及機器人相碰撞的前提下最短路徑,其算法流程如圖1所示。

圖1 無障礙最短路徑流程設計

如圖1所示,需要首先初始化機器人以及環境地圖的相關參數,并設置最大迭代次數。在搜索局部最優路徑的過程中,令函數維度為10,則此時的函數可行性可以表示為

(9)

式中,g(xn)表示最大迭代次數為n的情況下,函數的可行性;xi表示第i個局部環境的最優解;xj表示整體環境的最優解[10-12]。當迭代達到最大時,選擇其中的某條路徑,并判斷機器人是否與障礙物或者其它機器人發生碰撞,若發生碰撞,則需要重新選擇路徑,若未發生碰撞,則可以繼續下一個區域的測試。以此得到所有局部區域的最優解,然后搜索全局最優路徑,并建立相關的可行性檔案。時刻更新全局最優解,并輸出最終結果[13,14]。。根據以上方式,可以通過設計群體智能路徑規劃優化算法,獲得多移動機器人無障礙路徑的智能規劃方法。

3 仿真設計

3.1 柵格地圖仿真模型的構建及參數設置

測試文中設計的多移動機器人在路徑中的無障礙規劃方法的有效性需建立一個柵格地圖模型。設柵格地圖Hr=〈vx,rf〉,其中Hr表示一個有向的定點連接圖,vx表示圖中的節點集合;rf表示各節點間路徑集合[15]。,據此建立地圖矩陣,可以表示為:

(10)

根據矩陣構成鄰接矩陣的柵格模型,附帶頂點的權值鄰接節點,如圖2所示。

圖2 柵格地圖模型

根據矩陣(10)繪制的圖2中,黑色方塊為障礙物,白色透明方塊為可以通行的區域。在測試多移動機器人的路徑規劃算法中,設置機器人的數量為3,且每一個機器人的單向移動速度均相同,為防止碰撞,兩個機器人在相聚1m時,由其中編號靠后的一方躲避,機器人距障礙物0.5m時避讓。此時搜索空間的上限為max=300,下限為min=200[16]。在系統中初始化機器人的信息,分別設定機器人的傳感器組件,導入地圖信息,并為機器人設置相應的環境背景如圖3所示。

圖3 背景環境仿真模型

如圖3所示,在仿真程序中設定三個機器人的初始地點坐標以及終點坐標,其中A1(2,16)、A2(14,17)、A3(19,4)分別表示機器人的初始地點坐標,B1(9,4)、B2(2,8)、B3(11,15)分別表示機器人的終點坐標,將三個移動機器人分別從A1移動到B1,A2移動到B2,A3移動到B3。

3.2 路徑優化測試

對比文中設計的路徑規劃方法、文獻[1]提出的預測和模糊控制方法、文獻[2]提出的改進A～*算法+動態窗口法以及文獻[3]提出的改進灰狼優化算法的應用效果,在圖4所示的仿真柵格地圖中,對搜索路徑完成迭代測試,四種算法的迭代結果如圖4所示。

圖4 路徑收斂曲線

如圖4所示,面對圖3中的背景環境,四種路徑規劃方法均在不同此時的迭代以內完成路徑的最佳搜索。其中改進灰狼優化算法得到最優結果的迭代次數最小,其它三種方法均在之后存在一定的重復現象,這是因為在得到一個相對優化結果之后,通過算法又獲取了更優解,并繼續進行迭代優化。當算法迭代次數大于400次時,可以得到本文算法下的最優解為保證實驗結果的準確性,需要分別設計三條不同的實驗路徑,如果三條路徑中,文中算法的路線長度均為小于其它算法,則表示該算法得到了優化。每種環境下,障礙物的覆蓋率差距較大,分別設置三個機器人在該算法下的路徑規劃,如圖5所示。

圖5 不同路徑規劃測試

圖5所示的四種仿真算法下,三個機器人所行走的路徑分別使用不同灰度的柵格顯示,且在柵格上使用數字標注作為路徑的步數。其中兩個機器人在規劃過程中可能會發生路徑沖突的現象,此時則將其標注為白色的柵格形式,并在其中使用“x/y”的形式標注數字。對應柵格背景圖像,可以得到如表1所示的算法測試數據對比結果。

表1 路徑長度對比結果

通過表1中的數據結果可知,在起始點與終點相同的情況下,文中算法仿真得到的三個機器人所規劃的路徑分別為24m、21m、22m,且機器人規劃的路徑不存在沖突現象。其它三種算法在路徑1的路徑規劃結果均為28,在路徑2中的規劃結果為25m、21m、25m,在路徑3中的規劃結果為26m、22m、26m,路徑沖突的柵格數量分別為2個、4個、1個。由此可見,該多移動機器人路徑無障礙規劃方法較傳統方法更好,優化了路徑的規劃距離,且減少了路徑沖突現象。

4 結束語

本文通過群體智能路徑規劃優化算法的設計,對多移動機器人路徑無障礙規劃進行了優化,并對其進行仿真測試。該方法可以大幅度優化移動機器人在復雜環境內的路徑規劃程度,并以整體性的思維,對復雜環境內的多個移動機器人進行協調規劃,防止機器人之間發生碰撞。然而由于在局部規劃以外,還需要考慮多移動機器人整體規劃的問題,本文的路徑規劃運行速度有待提高,需要進一步優化算法的效率,才能使多移動機器人的路徑無障礙規劃方法更具實用性,使其能夠實時運用在實際的物流中。