唐建平, 宋紅生, 王東署

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

0 引言

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

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

1 問題描述

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

2 環(huán)境建模

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

本文利用柵格法模擬機(jī)器人的工作環(huán)境，建立環(huán)境模型.為實(shí)現(xiàn)設(shè)想的路徑規(guī)劃算法，在機(jī)器人運(yùn)動空間建模時作如下假定：1)移動機(jī)器人在二維有限空間中運(yùn)動；2)所有動態(tài)障礙物的運(yùn)動軌跡均為已知,即動態(tài)障礙物運(yùn)動路徑確定，而隨時間變化的規(guī)律未知；機(jī)器人勻速運(yùn)動；3)機(jī)器人每走一步即走一個柵格的中心點(diǎn),任意時刻機(jī)器人能探測到以當(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)前所走過的節(jié)點(diǎn).τij(t)表示t時刻在(i,j)邊上殘留的信息量，令初始時刻各條邊上的信息量為同一常數(shù)，τij(0)=τ0(τ0為常數(shù)).設(shè)置實(shí)驗(yàn)迭代次數(shù)NG=1，最大代數(shù)為NGMAX.

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

在時刻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)中所走路徑的長度.

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

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

4 基于滾動窗口的局部避障策略

4.1 基于滾動窗口的局部避障原理

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

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

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

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

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

5 仿真

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

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

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

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

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

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

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

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

圖3 正面碰撞圖

圖4 側(cè)面碰撞

6 總結(jié)

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

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

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

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

[4] 賈修一,于紹越,商琳,等.基于Rough集和蟻群算法的屬性約簡方法[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ì)會,徐心和.一種新的進(jìn)化算法-蟻群算法[J].系統(tǒng)工程理論與實(shí)踐,2007(3)：2-6.