孫紹華， 王魁生， 張?zhí)裉?/p>

(西安石油大學(xué) 計(jì)算機(jī)學(xué)院， 陜西 西安 710065)

0 引 言

Mirosot機(jī)器人平臺(tái)一般由視覺子系統(tǒng)、 通信子系統(tǒng)、 決策子系統(tǒng)以及機(jī)器人子系統(tǒng)4部分組成， 其決策系統(tǒng)如何根據(jù)視覺系統(tǒng)采集到的障礙物信息并結(jié)合實(shí)際的機(jī)器人狀態(tài)進(jìn)行合理的路徑規(guī)劃是非常重要的.

機(jī)器人避障路徑規(guī)劃一般可以分為兩級(jí)： 全局規(guī)劃和局部規(guī)劃， 即整體目標(biāo)分解為局部目標(biāo)， 再由局部規(guī)劃實(shí)現(xiàn)局部目標(biāo). 與此同時(shí)需滿足各種約束條件： 路徑最短、 躲避障礙、 經(jīng)過設(shè)定點(diǎn)、 耗時(shí)最短等[1]. 但是不同的算法在解決問題的過程中具有不同的側(cè)重.

文獻(xiàn)[2]認(rèn)為機(jī)器人決策應(yīng)該產(chǎn)生平滑的路徑以避免機(jī)器人反復(fù)停止和重新開始所造成的損耗， 提出了利用改進(jìn)的蜂群算法結(jié)合三次貝塞爾曲線進(jìn)行路徑規(guī)劃的解決方案. 文獻(xiàn)[3-5]在對(duì)比人工勢(shì)場(chǎng)法和遺傳算法的基礎(chǔ)上， 更加側(cè)重路徑規(guī)劃的時(shí)間和空間復(fù)雜度優(yōu)化， 提出基于模糊控制的機(jī)器人避障路徑算法， 并在結(jié)論處提出可以采用集成算法結(jié)合各個(gè)算法優(yōu)勢(shì)進(jìn)一步改進(jìn)路徑規(guī)劃問題. 文獻(xiàn)[6]提出基于遺傳算法的機(jī)器人避障路徑規(guī)劃算法， 該算法基于階段性路徑實(shí)現(xiàn)思路進(jìn)行設(shè)計(jì). 文獻(xiàn)[7]認(rèn)為蟻群算法在復(fù)雜環(huán)境下進(jìn)行路徑規(guī)劃時(shí)存在問題， 因此設(shè)計(jì)了一種新的動(dòng)態(tài)搜索誘導(dǎo)算子以改進(jìn)蟻群算法性能. 文獻(xiàn)[1，8]提出改進(jìn)粒子群算法實(shí)現(xiàn)機(jī)器人路徑規(guī)劃， 并且注重優(yōu)化算法的實(shí)時(shí)性， 保證路徑規(guī)劃的效率. 文獻(xiàn)[1]將粒子群算法與遺傳算法相互結(jié)合提出交叉算子和變異算子實(shí)現(xiàn)機(jī)器人路徑規(guī)劃算法的快收斂和高效率. 文獻(xiàn)[8]提出一種結(jié)合Ferguson樣條描述和改進(jìn)粒子群優(yōu)化算法的路徑優(yōu)化方法， 將路徑規(guī)劃問題轉(zhuǎn)化為三次樣條曲線參數(shù)優(yōu)化問題， 借助改進(jìn)的具有速度變異的粒子群算法進(jìn)行路徑優(yōu)化.

通過研究上述文獻(xiàn)， 發(fā)現(xiàn)基于Mirosot平臺(tái)機(jī)器人路徑規(guī)劃算法的設(shè)計(jì)均忽略機(jī)器人自身構(gòu)造的影響， 并且未考慮機(jī)器人在帶球情況下的路徑規(guī)劃問題， 致使在實(shí)際應(yīng)用環(huán)境中單獨(dú)機(jī)器人避障效果較好， 但卻無(wú)法完成帶球避障路徑規(guī)劃， 反復(fù)出現(xiàn)丟球等現(xiàn)象.

綜上所述， 本文結(jié)合機(jī)器人構(gòu)造提出限制角度δ， 設(shè)計(jì)適應(yīng)值因子wk， 改進(jìn)文獻(xiàn)[6]中的遺傳算法， 設(shè)計(jì)機(jī)器人帶球避障路徑規(guī)劃算法， 并對(duì)改進(jìn)算法進(jìn)行實(shí)驗(yàn)驗(yàn)證.

1 外觀構(gòu)造限制條件

Mirosot半自主型機(jī)器人要求每個(gè)機(jī)器人尺寸不能超過7.5 cm×7.5 cm×7.5 cm， 如圖 1 所示. 球體為直徑為42.7 mm的高爾夫球. 比賽要求機(jī)器人抓球或持球不能超過球體體積的30%， 見圖 2. 由于機(jī)器人球槽包含兩側(cè)， 本文僅進(jìn)行單側(cè)分析， 另一側(cè)同理.

圖 1 機(jī)器人效果圖Fig.1 Robot design sketch

圖 2 持球尺寸限制Fig.2 Size limit of holding the ball

根據(jù)比賽規(guī)則要求， 機(jī)器人持球深度不能超過12.81 mm.

42.7×30%=12.81.

(1)

如圖 3 所示， 機(jī)器人在帶球運(yùn)動(dòng)過程中， 根據(jù)球體直徑以及機(jī)器人尺寸計(jì)算得出， 球體與機(jī)器人接觸實(shí)際深度為11.14 mm.

(2)

圖 3 持球尺寸標(biāo)注Fig.3 Dimensioning of robot

按照比賽規(guī)則設(shè)計(jì)的機(jī)器人在進(jìn)行帶球運(yùn)動(dòng)時(shí)， 無(wú)法滿足機(jī)器人和球體接觸的極限深度12.81 mm， 即30%， 機(jī)器人與球體接觸的實(shí)際最大深度為11.14 mm， 即26%， 見圖 4.

(3)

在實(shí)際機(jī)器人帶球避障過程中， 如果機(jī)器人旋轉(zhuǎn)角度超過δ， 則會(huì)造成球體脫離， 即δ為機(jī)器人帶球運(yùn)動(dòng)時(shí)的旋轉(zhuǎn)限制角.

圖 4 實(shí)際尺寸Fig.4 The actual size

2 設(shè)計(jì)適應(yīng)值函數(shù)

根據(jù)文獻(xiàn)[6]遺傳算法中所提出的適應(yīng)值函數(shù)， 結(jié)合上文中結(jié)論， 對(duì)適應(yīng)值函數(shù)進(jìn)行改進(jìn)， 使算法選取的路徑點(diǎn)滿足機(jī)器人旋轉(zhuǎn)限制角條件.

首先， 以目標(biāo)點(diǎn)G和初始點(diǎn)S建立搜索范圍空間， 假設(shè)SG之間距離為L(zhǎng)， 以L為長(zhǎng)，L/2為寬做一矩形， 矩形內(nèi)機(jī)器人為障礙點(diǎn)， 如圖 5 所示.

圖 5 避障路徑搜索空間Fig.5 Obstacle path search space

其中， 以Pk=(x(k),y(k)),k=1,…,n表示路徑點(diǎn)， 以O(shè)Rj，j=1,…,q表示障礙物機(jī)器人， 取障礙物機(jī)器人中心點(diǎn)(xj,yj)表示障礙物位置，r表示以機(jī)器人為中心點(diǎn)的圓的半徑.

則改進(jìn)后適應(yīng)值函數(shù)如下

fi=uk+vj,k+wk,

(4)

(5)

(6)

(7)

式(4)中：fi為第i條路徑的適應(yīng)值大小，uk表示路徑點(diǎn)k躲避障礙物的程度，vj,k表示路徑點(diǎn)k與障礙物j之間的距離大于機(jī)器人半徑r的程度，wk表示路徑點(diǎn)k滿足轉(zhuǎn)向角度δk∈δ的程度.

式(5)中：Lk為路徑點(diǎn)k至目標(biāo)點(diǎn)G在SG上的距離，lk為路徑點(diǎn)至目標(biāo)點(diǎn)G的距離， 如圖 6 所示，α表示路徑點(diǎn)規(guī)避障礙物程度在適應(yīng)值函數(shù)中所占比重.

圖 6 路徑點(diǎn)接近程度Fig.6 Path point proximity

圖 7 旋轉(zhuǎn)角度限制Fig.7 Rotation Angle limit

3 改進(jìn)遺傳算法

根據(jù)文獻(xiàn)[6]中的遺傳算法設(shè)計(jì)， 步驟如下：

1) 首先進(jìn)行路徑編碼， 將場(chǎng)地路徑點(diǎn)變?yōu)槿旧w編碼.

2) 選擇合適的路徑群體數(shù)目M， 交叉概率pc和變異概率pm.

3) 隨機(jī)產(chǎn)生一個(gè)初始群體M.

4) 利用適應(yīng)值函數(shù)fi計(jì)算每條路徑的適應(yīng)值大小， 進(jìn)而求出適應(yīng)值總和F=∑fi，i=1,…,M.

6) 按照預(yù)先設(shè)定的交叉概率進(jìn)行交叉.

7) 按照預(yù)先設(shè)定的變異概率進(jìn)行變異.

8) 判斷是否滿足條件， 滿足則執(zhí)行， 不滿足則繼續(xù)迭代.

本文基于上述算法步驟， 結(jié)合前文結(jié)論所改進(jìn)的適應(yīng)值函數(shù)fi， 實(shí)現(xiàn)機(jī)器人帶球避障路徑規(guī)劃.

4 實(shí) 驗(yàn)

根據(jù)上述算法步驟， 分別對(duì)單獨(dú)機(jī)器人帶球避障效果和整體比賽效果進(jìn)行實(shí)驗(yàn)驗(yàn)證. 將本設(shè)計(jì)算法應(yīng)用于Mirosot機(jī)器人3V3場(chǎng)地平臺(tái)上， 編程環(huán)境為Microsoft Visual C++ 6.0.

實(shí)驗(yàn)一： 設(shè)置3個(gè)靜態(tài)機(jī)器人障礙物， 1個(gè)帶球避障機(jī)器人， 如圖 8 所示. 原算法和改進(jìn)算法各進(jìn)行30次實(shí)驗(yàn)， 共計(jì)60次實(shí)驗(yàn)， 實(shí)驗(yàn)結(jié)果如表 1 所示.

圖 8 靜態(tài)避障Fig.8 Static obstacle avoidance

表 1 實(shí)驗(yàn)1結(jié)果

表 1 數(shù)據(jù)表明， 原算法無(wú)法實(shí)現(xiàn)機(jī)器人帶球避障， 改進(jìn)后帶球避障成功率為53.3%， 有效提升了帶球避障成功率.

實(shí)驗(yàn)二： 進(jìn)行3V3機(jī)器人對(duì)抗賽， 雙方各3名機(jī)器人為參賽隊(duì)員， 其中1名為守門員， 其余2名為攻守隊(duì)員， 如圖 9 所示. 上下半場(chǎng)各比賽 5 min， 藍(lán)方為原算法實(shí)現(xiàn)的帶球避障效果， 黃方為改進(jìn)算法后實(shí)現(xiàn)效果， 實(shí)驗(yàn)結(jié)果如表 2 所示.

圖 9 動(dòng)態(tài)避障Fig.9 Dynamic obstacle avoidance

表 2 實(shí)驗(yàn)2結(jié)果

全場(chǎng)比賽共計(jì)10 min(600 s)， 藍(lán)方(原算法)全場(chǎng)帶球時(shí)長(zhǎng)為145 s， 占比24.17%； 黃方(改進(jìn)算法)全場(chǎng)帶球時(shí)長(zhǎng)為455 s， 占比75.83%. 帶球時(shí)長(zhǎng)數(shù)據(jù)表明， 黃方在控球時(shí)間上處于絕對(duì)優(yōu)勢(shì)地位. 全場(chǎng)總進(jìn)球數(shù)為6， 其中藍(lán)方進(jìn)球數(shù)為1， 黃方進(jìn)球數(shù)為5， 最終比賽黃方獲得勝利.

5 結(jié) 論

本文綜合前人的研究成果， 引入機(jī)器人外觀構(gòu)造變量， 在原有遺傳算法的基礎(chǔ)之上設(shè)計(jì)機(jī)器人帶球避障遺傳算法， 并提出了機(jī)器人旋轉(zhuǎn)角度限制條件δ和適應(yīng)值因子wk.

設(shè)計(jì)單獨(dú)機(jī)器人帶球避障和整體比賽效果兩個(gè)實(shí)驗(yàn)對(duì)算法進(jìn)行驗(yàn)證， 實(shí)驗(yàn)結(jié)果表明， 改進(jìn)算法的帶球避障成功率提升了53.3%， 比賽控球時(shí)間占比為75.83%， 并最終以進(jìn)球數(shù)的絕對(duì)優(yōu)勢(shì)取得比賽勝利.

本文采用階段性路徑規(guī)劃算法， 即遺傳算法進(jìn)行研究， 在實(shí)驗(yàn)中如文獻(xiàn)[2]所述， 機(jī)器人出現(xiàn)明顯的抖動(dòng)情況， 這也是影響帶球效果的主要原因， 在未來(lái)的研究中可以將旋轉(zhuǎn)角度限制因子引入蜂群等連續(xù)性路徑規(guī)劃算法中進(jìn)行改進(jìn).