多移動(dòng)機(jī)器人路徑無障礙智能規(guī)劃算法仿真

熊 焰,劉金庫(kù)

(華東理工大學(xué)工程訓(xùn)練中心,上海 201424)

1 引言

物流行業(yè)在社會(huì)運(yùn)行中地位與日俱增,促使移動(dòng)機(jī)器人技術(shù)得到了迅速地發(fā)展?；谝苿?dòng)機(jī)器人自帶的導(dǎo)航定位功能,人們得以在倉(cāng)儲(chǔ)物流的過程中大幅度增加工作效率,減少不必要的人力勞動(dòng)。但是當(dāng)倉(cāng)儲(chǔ)環(huán)境較為復(fù)雜或者移動(dòng)機(jī)器人的數(shù)量過多時(shí),機(jī)器人總是會(huì)發(fā)生無意識(shí)的碰撞,導(dǎo)致無法順利完成倉(cāng)儲(chǔ)物流的任務(wù),為此對(duì)復(fù)雜環(huán)境下的多移動(dòng)機(jī)器人路徑規(guī)劃進(jìn)行設(shè)計(jì)與研究。

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

2 復(fù)雜環(huán)境多移動(dòng)機(jī)器人路徑無障礙規(guī)劃方法

2.1 群體智能路徑規(guī)劃優(yōu)化算法設(shè)計(jì)

移動(dòng)機(jī)器人在復(fù)雜環(huán)境內(nèi)完成路徑規(guī)劃的本質(zhì)為:將所處環(huán)境變?yōu)橐阎h(huán)境,同時(shí)逐步迭代計(jì)算不同的路徑長(zhǎng)度,并注意比較路徑長(zhǎng)短。其中最短的一條路徑就是該算法下移動(dòng)機(jī)器人的路徑規(guī)劃設(shè)計(jì)。而多移動(dòng)機(jī)器人的路徑規(guī)劃,則需要綜合考慮所有機(jī)器人的路徑,從單一的路徑計(jì)算,轉(zhuǎn)變?yōu)槿后w性的規(guī)劃設(shè)計(jì),通過蟻群算法,可以實(shí)現(xiàn)啟發(fā)性的隨機(jī)智能搜索。算法中的每一個(gè)個(gè)體在面臨位置選擇時(shí),都需要向不同的方向移動(dòng),而在障礙區(qū)域內(nèi),障礙物就起到了一個(gè)約束的作用,使個(gè)體不會(huì)向障礙阻隔的方向移動(dòng)。其中的最優(yōu)解即表示不限定路徑的前提下,機(jī)器人在可行解的空間內(nèi)反復(fù)迭代的最大值[4]。如果運(yùn)算量過大,則容易造成路徑冗長(zhǎng)的現(xiàn)象,此時(shí)就需要對(duì)其進(jìn)行簡(jiǎn)化處理。在設(shè)計(jì)群體性的智能路徑優(yōu)化時(shí),算法內(nèi)應(yīng)該設(shè)置禁忌表,進(jìn)行隱式的通信,通過引導(dǎo)路徑規(guī)劃的倒數(shù)值,將啟發(fā)式因子參數(shù)與信息素相結(jié)合,得到啟發(fā)因子比重的更新函數(shù)

(1)

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

(2)

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

(3)

式中,hk表示路徑信息素采樣的周期。通過該公式,可以得到一個(gè)有助于多個(gè)移動(dòng)機(jī)器人進(jìn)行路徑規(guī)劃的算法。

2.2 計(jì)算多移動(dòng)機(jī)器人碰撞風(fēng)險(xiǎn)

從起點(diǎn)到達(dá)最終點(diǎn),需要保證機(jī)器人不與復(fù)雜環(huán)境內(nèi)的任何物體相接觸,其中包括路障和另外的機(jī)器人,因此在保證移動(dòng)機(jī)器人安全的前提下,需要根據(jù)時(shí)間與空間的差異,設(shè)置移動(dòng)路徑。其中,當(dāng)路徑與障礙物不存在重疊情況時(shí),公式為

(4)

(5)

式中,hi,j表示第i個(gè)移動(dòng)機(jī)器人在位置為j時(shí)的安全情況;p表示該位置點(diǎn)是否為障礙點(diǎn)。在考慮路徑安全性的前提下,計(jì)算碰撞風(fēng)險(xiǎn)函數(shù),可以得到公式

(6)

式中,G(fc,fs)表示機(jī)器人移動(dòng)的位置與障礙物位置的相對(duì)距離;δ表示障礙物的影響距離[8]。在機(jī)器人與障礙物之外,還需要建立移動(dòng)機(jī)器人工作空間的二維模型?？臻g中的任意一點(diǎn)都存在慣性坐標(biāo)系以及旋轉(zhuǎn)坐標(biāo)系之間的轉(zhuǎn)換關(guān)系,以此建立矩陣

(7)

式中,(x1,y1)表示空間中移動(dòng)機(jī)器人的起始點(diǎn);(x2,y2)表示空間中移動(dòng)機(jī)器人的終點(diǎn);α表示慣性坐標(biāo)系轉(zhuǎn)換后的角度。據(jù)此生成多個(gè)機(jī)器人行駛過程中碰撞的風(fēng)險(xiǎn)

(8)

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

2.3 智能規(guī)劃多移動(dòng)機(jī)器人最短無障礙路徑

在復(fù)雜環(huán)境下,需要針對(duì)以上算法以及碰撞風(fēng)險(xiǎn)的公式,智能規(guī)劃多移動(dòng)機(jī)器人的最短無障礙路徑,即遍歷在不與其它障礙物以及機(jī)器人相碰撞的前提下最短路徑,其算法流程如圖1所示。

圖1 無障礙最短路徑流程設(shè)計(jì)

如圖1所示,需要首先初始化機(jī)器人以及環(huán)境地圖的相關(guān)參數(shù),并設(shè)置最大迭代次數(shù)。在搜索局部最優(yōu)路徑的過程中,令函數(shù)維度為10,則此時(shí)的函數(shù)可行性可以表示為

(9)

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

3 仿真設(shè)計(jì)

3.1 柵格地圖仿真模型的構(gòu)建及參數(shù)設(shè)置

測(cè)試文中設(shè)計(jì)的多移動(dòng)機(jī)器人在路徑中的無障礙規(guī)劃方法的有效性需建立一個(gè)柵格地圖模型。設(shè)柵格地圖Hr=〈vx,rf〉,其中Hr表示一個(gè)有向的定點(diǎn)連接圖,vx表示圖中的節(jié)點(diǎn)集合;rf表示各節(jié)點(diǎn)間路徑集合[15]。,據(jù)此建立地圖矩陣,可以表示為:

(10)

根據(jù)矩陣構(gòu)成鄰接矩陣的柵格模型,附帶頂點(diǎn)的權(quán)值鄰接節(jié)點(diǎn),如圖2所示。

圖2 柵格地圖模型

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

圖3 背景環(huán)境仿真模型

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

3.2 路徑優(yōu)化測(cè)試

對(duì)比文中設(shè)計(jì)的路徑規(guī)劃方法、文獻(xiàn)[1]提出的預(yù)測(cè)和模糊控制方法、文獻(xiàn)[2]提出的改進(jìn)A～*算法+動(dòng)態(tài)窗口法以及文獻(xiàn)[3]提出的改進(jìn)灰狼優(yōu)化算法的應(yīng)用效果,在圖4所示的仿真柵格地圖中,對(duì)搜索路徑完成迭代測(cè)試,四種算法的迭代結(jié)果如圖4所示。

圖4 路徑收斂曲線

如圖4所示,面對(duì)圖3中的背景環(huán)境,四種路徑規(guī)劃方法均在不同此時(shí)的迭代以內(nèi)完成路徑的最佳搜索。其中改進(jìn)灰狼優(yōu)化算法得到最優(yōu)結(jié)果的迭代次數(shù)最小,其它三種方法均在之后存在一定的重復(fù)現(xiàn)象,這是因?yàn)樵诘玫揭粋€(gè)相對(duì)優(yōu)化結(jié)果之后,通過算法又獲取了更優(yōu)解,并繼續(xù)進(jìn)行迭代優(yōu)化。當(dāng)算法迭代次數(shù)大于400次時(shí),可以得到本文算法下的最優(yōu)解為保證實(shí)驗(yàn)結(jié)果的準(zhǔn)確性,需要分別設(shè)計(jì)三條不同的實(shí)驗(yàn)路徑,如果三條路徑中,文中算法的路線長(zhǎng)度均為小于其它算法,則表示該算法得到了優(yōu)化。每種環(huán)境下,障礙物的覆蓋率差距較大,分別設(shè)置三個(gè)機(jī)器人在該算法下的路徑規(guī)劃,如圖5所示。

圖5 不同路徑規(guī)劃測(cè)試

圖5所示的四種仿真算法下,三個(gè)機(jī)器人所行走的路徑分別使用不同灰度的柵格顯示,且在柵格上使用數(shù)字標(biāo)注作為路徑的步數(shù)。其中兩個(gè)機(jī)器人在規(guī)劃過程中可能會(huì)發(fā)生路徑?jīng)_突的現(xiàn)象,此時(shí)則將其標(biāo)注為白色的柵格形式,并在其中使用“x/y”的形式標(biāo)注數(shù)字。對(duì)應(yīng)柵格背景圖像,可以得到如表1所示的算法測(cè)試數(shù)據(jù)對(duì)比結(jié)果。

表1 路徑長(zhǎng)度對(duì)比結(jié)果

通過表1中的數(shù)據(jù)結(jié)果可知,在起始點(diǎn)與終點(diǎn)相同的情況下,文中算法仿真得到的三個(gè)機(jī)器人所規(guī)劃的路徑分別為24m、21m、22m,且機(jī)器人規(guī)劃的路徑不存在沖突現(xiàn)象。其它三種算法在路徑1的路徑規(guī)劃結(jié)果均為28,在路徑2中的規(guī)劃結(jié)果為25m、21m、25m,在路徑3中的規(guī)劃結(jié)果為26m、22m、26m,路徑?jīng)_突的柵格數(shù)量分別為2個(gè)、4個(gè)、1個(gè)。由此可見,該多移動(dòng)機(jī)器人路徑無障礙規(guī)劃方法較傳統(tǒng)方法更好,優(yōu)化了路徑的規(guī)劃距離,且減少了路徑?jīng)_突現(xiàn)象。

4 結(jié)束語(yǔ)

本文通過群體智能路徑規(guī)劃優(yōu)化算法的設(shè)計(jì),對(duì)多移動(dòng)機(jī)器人路徑無障礙規(guī)劃進(jìn)行了優(yōu)化,并對(duì)其進(jìn)行仿真測(cè)試。該方法可以大幅度優(yōu)化移動(dòng)機(jī)器人在復(fù)雜環(huán)境內(nèi)的路徑規(guī)劃程度,并以整體性的思維,對(duì)復(fù)雜環(huán)境內(nèi)的多個(gè)移動(dòng)機(jī)器人進(jìn)行協(xié)調(diào)規(guī)劃,防止機(jī)器人之間發(fā)生碰撞。然而由于在局部規(guī)劃以外,還需要考慮多移動(dòng)機(jī)器人整體規(guī)劃的問題,本文的路徑規(guī)劃運(yùn)行速度有待提高,需要進(jìn)一步優(yōu)化算法的效率,才能使多移動(dòng)機(jī)器人的路徑無障礙規(guī)劃方法更具實(shí)用性,使其能夠?qū)崟r(shí)運(yùn)用在實(shí)際的物流中。