一種移動(dòng)機(jī)器人動(dòng)態(tài)環(huán)境下的路徑規(guī)劃

唐建平, 宋紅生, 王東署

(1.鄭州大學(xué) 電氣工程學(xué)院 河南 鄭州 450001；2.鄭州大學(xué) 國(guó)際教育學(xué)院 河南 鄭州 450001)

0 引言

移動(dòng)機(jī)器人路徑規(guī)劃問(wèn)題是指在有障礙物的環(huán)境中，給定起始點(diǎn)和終止點(diǎn)，尋找一條較優(yōu)的運(yùn)動(dòng)路徑，使機(jī)器人能安全、無(wú)碰撞的行走且路徑最短[1].當(dāng)前靜態(tài)環(huán)境下路徑規(guī)劃主要是采用全局規(guī)劃的方法并采用相應(yīng)算法對(duì)路徑進(jìn)行優(yōu)化，如遺傳算法、神經(jīng)網(wǎng)絡(luò)和模糊算法等[2].而在動(dòng)態(tài)未知環(huán)境中，由于環(huán)境等因素的局限性，研究起來(lái)比較復(fù)雜，逐漸成為研究的熱點(diǎn).近年來(lái)，很多學(xué)者針對(duì)未知環(huán)境下的機(jī)器人路徑規(guī)劃做了大量研究，并取得了一定的成果.其中有代表性的成果是滾動(dòng)窗口規(guī)劃方法[3].該算法以起始點(diǎn)到機(jī)器人和機(jī)器人到目標(biāo)點(diǎn)之間的距離作為啟發(fā)信息構(gòu)造代價(jià)函數(shù)，以此引導(dǎo)子目標(biāo)的映射，在子目標(biāo)引導(dǎo)下，局部視野窗口向子目標(biāo)或沿障礙物滾動(dòng).但該算法不具備智能性，只能靠復(fù)雜的邏輯判斷進(jìn)行滾動(dòng)，容易沿障礙再滾回到原處，形成死鎖和振蕩，規(guī)劃的路徑也難以達(dá)到全局最優(yōu).

針對(duì)上述不足，本文采用全局路徑規(guī)劃和局部避障規(guī)劃相結(jié)合的思想，針對(duì)環(huán)境中存在靜態(tài)障礙物和動(dòng)態(tài)障礙物的情況，提出了一種動(dòng)態(tài)未知環(huán)境中自主機(jī)器人路徑規(guī)劃的新方法.相對(duì)于其他算法，蟻群算法對(duì)初始路線要求不高，而且在搜索過(guò)程中不需要進(jìn)行人工的調(diào)整，并且所需參數(shù)少，故首先采用蟻群算法規(guī)劃一條趨于目標(biāo)的全局優(yōu)化路徑，然后在此全局優(yōu)化路徑的指引下采用滾動(dòng)窗口的動(dòng)態(tài)避障和信息反饋的策略進(jìn)行局部避障規(guī)劃.采用這種全局指導(dǎo)下的局部避障的方法能確保機(jī)器人安全無(wú)碰撞且路徑較優(yōu)，從而為動(dòng)態(tài)環(huán)境下自主機(jī)器人路徑規(guī)劃提供了一種新思路.

1 問(wèn)題描述

設(shè)機(jī)器人的工作空間為二維平面上的有限平面區(qū)域，其中分布著有限個(gè)已知靜態(tài)障礙物Sobsi(i=1,…,n)和有限個(gè)未知?jiǎng)討B(tài)障礙物Dobsi(i=1,…,m).將機(jī)器人模型化為點(diǎn)狀機(jī)器人，并且無(wú)全局環(huán)境信息.在任一時(shí)刻，它只能實(shí)時(shí)探測(cè)到以其當(dāng)前位置為中心，r為半徑區(qū)域內(nèi)的環(huán)境信息(包括障礙物位置、速度).路經(jīng)規(guī)劃的目的是使機(jī)器人由起點(diǎn)Pinit安全無(wú)碰地到達(dá)終點(diǎn)Pgoal.本文提出的方法分為趨向于目標(biāo)的全局運(yùn)動(dòng)規(guī)劃和躲避障礙物的局部運(yùn)動(dòng)規(guī)劃.全局路徑規(guī)劃根據(jù)環(huán)境感知模塊提供的靜止障礙物信息，采用蟻群算法確定出一條未考慮動(dòng)態(tài)障礙物的初始全局優(yōu)化路徑，然后，機(jī)器人按照全局優(yōu)化路徑趨向于目標(biāo)，期間通過(guò)傳感器不斷探測(cè)滾動(dòng)窗口內(nèi)的動(dòng)態(tài)障礙物信息，根據(jù)對(duì)障礙物的預(yù)測(cè)判斷會(huì)不會(huì)發(fā)生碰撞，從而安全到達(dá)目標(biāo)并且保證路徑較優(yōu).

2 環(huán)境建模

環(huán)境建模的目的是建立一個(gè)便于計(jì)算機(jī)模擬進(jìn)行路徑規(guī)劃使用的環(huán)境模型.環(huán)境建模是機(jī)器人路徑規(guī)劃的重要環(huán)節(jié)，是實(shí)現(xiàn)物理空間到算法處理抽象空間的一個(gè)映射[4].

本文利用柵格法模擬機(jī)器人的工作環(huán)境，建立環(huán)境模型.為實(shí)現(xiàn)設(shè)想的路徑規(guī)劃算法，在機(jī)器人運(yùn)動(dòng)空間建模時(shí)作如下假定：1)移動(dòng)機(jī)器人在二維有限空間中運(yùn)動(dòng)；2)所有動(dòng)態(tài)障礙物的運(yùn)動(dòng)軌跡均為已知,即動(dòng)態(tài)障礙物運(yùn)動(dòng)路徑確定，而隨時(shí)間變化的規(guī)律未知；機(jī)器人勻速運(yùn)動(dòng)；3)機(jī)器人每走一步即走一個(gè)柵格的中心點(diǎn),任意時(shí)刻機(jī)器人能探測(cè)到以當(dāng)前柵格中心點(diǎn)為中心，r為半徑區(qū)域內(nèi)的環(huán)境信息.

3 基于蟻群算法趨向目標(biāo)的全局路徑規(guī)劃

3.1 螞蟻算法步驟

Step1初始化.

每一輪螞蟻的數(shù)目為m，將螞蟻放置在出發(fā)點(diǎn)S，并把S加入到禁忌表tabuk中(k=1,2,3,…).列表tabuk記錄了每一輪螞蟻k當(dāng)前所走過(guò)的節(jié)點(diǎn).τij(t)表示t時(shí)刻在(i,j)邊上殘留的信息量，令初始時(shí)刻各條邊上的信息量為同一常數(shù)，τij(0)=τ0(τ0為常數(shù)).設(shè)置實(shí)驗(yàn)迭代次數(shù)NG=1，最大代數(shù)為NGMAX.

Step2根據(jù)策略選擇下一節(jié)點(diǎn)j.

在時(shí)刻t，螞蟻從節(jié)點(diǎn)i轉(zhuǎn)移到節(jié)點(diǎn)j的概率為

其中，allowedk={1,2,…,n}表示螞蟻k下一步允許選擇的所有節(jié)點(diǎn).α和β分別表示路徑上信息量和啟發(fā)式因子ηij的重要程度.啟發(fā)式因子ηij表示螞蟻從節(jié)點(diǎn)i轉(zhuǎn)移到節(jié)點(diǎn)j的期望程度，通常取ηij=1/dij,dij表示節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的距離.

Step3信息素更新.

式中，Q表示信息素強(qiáng)度，它在一定程度上影響算法的收斂速度；Lk表示第k只螞蟻在本次循環(huán)中所走路徑的長(zhǎng)度.

Step4NG++，若NG>NGMAX，則停止，否則轉(zhuǎn)到Step 2.

Step5輸出最優(yōu)路徑，算法結(jié)束.

4 基于滾動(dòng)窗口的局部避障策略

4.1 基于滾動(dòng)窗口的局部避障原理

基于滾動(dòng)窗口的路徑規(guī)劃算法的基本原理如下所述.1)場(chǎng)景預(yù)測(cè)：在滾動(dòng)的每一步，機(jī)器人根據(jù)其探測(cè)到的局部窗口范圍內(nèi)的環(huán)境信息，用啟發(fā)式方法生成局部子目標(biāo)，并對(duì)動(dòng)態(tài)障礙物的運(yùn)動(dòng)進(jìn)行預(yù)測(cè)，判斷機(jī)器人行進(jìn)過(guò)程中是否可能與動(dòng)態(tài)障礙物相碰撞.2)滾動(dòng)窗口優(yōu)化：機(jī)器人根據(jù)窗口內(nèi)的環(huán)境信息及預(yù)測(cè)結(jié)果，選擇局部規(guī)劃算法，確定向子目標(biāo)行進(jìn)的局部路徑，并實(shí)施當(dāng)前策略，即依據(jù)所規(guī)劃的局部路徑行進(jìn)一步，窗口相應(yīng)向前滾動(dòng).3)反饋初始化：在新的滾動(dòng)窗口產(chǎn)生后，根據(jù)傳感器所獲取的最新信息，對(duì)窗口內(nèi)的環(huán)境及障礙物運(yùn)動(dòng)狀況進(jìn)行更新[6].

4.2 針對(duì)各種預(yù)測(cè)情況的避碰策略

1)若預(yù)測(cè)到將要發(fā)生機(jī)器人和動(dòng)態(tài)障礙物正面相撞的情況時(shí)，機(jī)器人必須放棄原行進(jìn)計(jì)劃，即時(shí)生成局部子目標(biāo)，并將碰撞點(diǎn)所在柵格設(shè)置為臨時(shí)靜態(tài)障礙物，然后采用蟻群算法在當(dāng)前位置與局部子目標(biāo)之間重新規(guī)劃出一條局部避碰路徑，以替代原有路徑.

2)若預(yù)測(cè)到將要發(fā)生機(jī)器人和動(dòng)態(tài)障礙物側(cè)面相撞的情況時(shí)，機(jī)器人只需在原地等待Δt時(shí)間后，再按照原規(guī)劃路徑行進(jìn).

3)若預(yù)測(cè)到機(jī)器人與動(dòng)態(tài)障礙物不會(huì)發(fā)生任何碰撞，則直接按原規(guī)劃路徑行進(jìn).

5 仿真

將機(jī)器人工作平面劃分成20×20個(gè)柵格，起始柵格序號(hào)取1，目標(biāo)柵格序號(hào)取400.障礙物柵格的序號(hào)隨機(jī)生成.蟻群算法中參數(shù)取值如下，m=20,α=1,β=1,C=0.5,ρ=0.7,Q=100.

5.1 存在靜態(tài)障礙物情況下的仿真

在全局未知靜態(tài)環(huán)境下，通過(guò)蟻群算法尋找出全局優(yōu)化路徑.圖1是大多數(shù)螞蟻選擇前往目標(biāo)點(diǎn)的一條路徑，這條路徑就是所要的最優(yōu)路徑，即機(jī)器人的移動(dòng)路徑.圖2為最短路徑隨迭代次數(shù)變化的收斂曲線圖，灰線代表普通蟻群算法所得到的平均路徑長(zhǎng)度和最短路徑長(zhǎng)度，黑線代表改進(jìn)后蟻群算法所得到的平均路徑長(zhǎng)度和最短路徑長(zhǎng)度.改進(jìn)后的螞蟻算法收斂速度更快，迭代10次就得到收斂的路徑解，算法的收斂已趨于穩(wěn)定.求得最短路徑為32.382 0.

5.2 存在未知障礙物情況下的仿真

1)預(yù)測(cè)正面碰撞.圖3中粗直線表示動(dòng)態(tài)障礙物運(yùn)動(dòng)軌跡，由左下向左上運(yùn)動(dòng)，機(jī)器人在按照全局優(yōu)化路徑行走過(guò)程中預(yù)測(cè)到行走路線和運(yùn)動(dòng)障礙物的軌跡有交點(diǎn)，并且會(huì)發(fā)生正面碰撞.此時(shí)機(jī)器人放棄原行進(jìn)計(jì)劃重新規(guī)劃出一條局部避碰路徑，以替代圖1所示的原有路徑.

2)預(yù)測(cè)側(cè)面碰撞.圖4中粗直線表示障礙物運(yùn)動(dòng)軌跡，動(dòng)態(tài)障礙物由左下向右上運(yùn)動(dòng)，軌跡如圖4，機(jī)器人在進(jìn)行過(guò)程中預(yù)測(cè)到可能發(fā)生側(cè)面碰撞，準(zhǔn)備采取原地等待障礙物先通過(guò)的避碰策略.

以上仿真實(shí)驗(yàn)結(jié)果表明，用蟻群算法可以得到較優(yōu)的全局路徑；在局部避碰規(guī)劃中，所采用的各種避碰策略能使機(jī)器人安全避開(kāi)動(dòng)態(tài)障礙物.全局路徑規(guī)劃和局部避碰策略的結(jié)合，可以有效確保機(jī)器人從起始點(diǎn)安全運(yùn)動(dòng)到目標(biāo)點(diǎn)，且解決了機(jī)器人運(yùn)動(dòng)過(guò)程中可能會(huì)遇到的死鎖和振蕩現(xiàn)象.

圖2 最短路徑隨迭代次數(shù)變化的收斂曲線

圖3 正面碰撞圖

圖4 側(cè)面碰撞

6 總結(jié)

本文針對(duì)動(dòng)態(tài)環(huán)境中自主機(jī)器人路徑規(guī)劃問(wèn)題，提出了一種由趨于目標(biāo)的全局運(yùn)動(dòng)規(guī)劃和躲避障礙物的局部運(yùn)動(dòng)規(guī)劃相結(jié)合的路徑規(guī)劃新方法.該方法采用基于蟻群算法的全局路徑規(guī)劃和基于滾動(dòng)窗口的局部避碰規(guī)劃相結(jié)合的總體策略，較好地解決了路徑規(guī)劃中整體與局部的關(guān)系，同時(shí)兼顧了可行路徑的安全性和優(yōu)化性.仿真實(shí)驗(yàn)結(jié)果證明了本文算法的有效性，但本文只討論了障礙物運(yùn)動(dòng)軌跡為已知情況下的路徑規(guī)劃問(wèn)題，針對(duì)動(dòng)態(tài)障礙物更為復(fù)雜的一般情況還有待于進(jìn)一步研究.

[1] 李磊,葉濤,譚民,等.移動(dòng)機(jī)器人技術(shù)研究現(xiàn)狀與未來(lái)[J].機(jī)器人，2002，24(1)：475-480.

[2] 俞輝,裴振奎,陳繼東.一種改進(jìn)的蟻群聚類算法[J].鄭州大學(xué)學(xué)報(bào)：理學(xué)版，2010,42(3):59-62.

[3] 席裕庚.一類動(dòng)態(tài)不確定環(huán)境下機(jī)器人的滾動(dòng)路徑規(guī)劃[J].自動(dòng)化學(xué)報(bào),2009，28(2)：3-5.

[4] 賈修一,于紹越,商琳,等.基于Rough集和蟻群算法的屬性約簡(jiǎn)方法[J].廣西師范大學(xué)學(xué)報(bào)：自然科學(xué)版,2006,24(4)：83-86.

[5] Dorigo M,Gambardella L M,Middendorf M,et al.Guest editorial: special section on ant colony optimization[J].IEEE Transactions on Evolutionary Computation,2002,6(4): 317-319.

[6] 張紀(jì)會(huì),徐心和.一種新的進(jìn)化算法-蟻群算法[J].系統(tǒng)工程理論與實(shí)踐,2007(3)：2-6.