足球機器人避障及防側(cè)翻問題研究

薛 丹, 孫喜慶, 白文峰*

(1.長春工業(yè)大學(xué) 電氣與電子工程學(xué)院， 吉林 長春 130012；2.長春理工大學(xué)光電信息學(xué)院， 吉林 長春 130114)

足球機器人避障及防側(cè)翻問題研究

薛 丹1,2, 孫喜慶1, 白文峰1*

(1.長春工業(yè)大學(xué) 電氣與電子工程學(xué)院， 吉林 長春 130012；2.長春理工大學(xué)光電信息學(xué)院， 吉林 長春 130114)

應(yīng)用擴展地圖,采用改進遺傳算法以及蟻群與遺傳結(jié)合算法相結(jié)合來優(yōu)化機器人運行路徑的長度、平滑性和安全性3個目標(biāo)。

機器人； 路徑規(guī)劃； 擴展地圖； 遺傳算法； 蟻群遺傳算法

0 引 言

近年來，足球機器人各方面的研究工作不斷深入，其中路徑規(guī)劃問題可以分為傳統(tǒng)方法和智能方法。傳統(tǒng)方法有圖形搜索、人工勢場、網(wǎng)格方法等，這些傳統(tǒng)的研究方法盡管可以較好地解決路徑規(guī)劃問題，但是搜索效率低[1-3]。智能算法以蟻群算法、遺傳算法、神經(jīng)網(wǎng)絡(luò)為代表，因其效率高而得到廣泛的應(yīng)用，當(dāng)然智能算法在應(yīng)用過程中也有其相應(yīng)的缺點。

因足球機器人不是單一的機器人運動，所以，足球機器人路徑規(guī)劃不是只求長度最短的單一目標(biāo)的優(yōu)化。在機器人進行足球比賽過程中，會遇到很多隨機的問題，主要是足球機器人之間的碰撞，足球機器人自身的側(cè)翻[4]。對于碰撞問題可分為動態(tài)障礙物和靜態(tài)障礙物，所以，在大多數(shù)現(xiàn)實情況下，機器人與障礙物一定要保持有效的安全空間。此外，機器人在應(yīng)用時，還要考慮到路徑中可能存在的小夾角，如果存在這樣的夾角，機器人的車輪可能遭到一定的磨損，嚴(yán)重一點的會使得機器人不再沿著規(guī)劃的軌跡行駛，甚至可能導(dǎo)致機器人的側(cè)翻，因此，機器人路徑規(guī)劃問題是有多個最優(yōu)解的，并且是難以找到精確解的[5]。對此，提出了能有效地使機器人可以從起點無碰撞且無翻滾的運動到終點的解決方法，盡管這些解決方法存在著一些缺點，但是已經(jīng)取得了一些研究成果。

因足球機器人路徑規(guī)劃要考慮到路徑的長度、平滑性、安全性，所以這是一個多目標(biāo)優(yōu)化問題。此問題首先考慮機器人的碰撞和翻滾，此時可考慮應(yīng)用擴展碰撞地圖[4]。

1 問題描述

將每個機器人假設(shè)為一個平移和轉(zhuǎn)動被獨立控制的輪式驅(qū)動機器人，因此無翻滾狀態(tài)下的機器人描述如下[6]：

kXb-kYb-kZb是一個機器人框架，機器人的寬度、重心的高度分別為wb和h。此時平移速度v由足球機器人從起點到目標(biāo)點采用的梯形速度曲線決定。

但是考慮到安全問題，在機器人行進過程中可以加入偏移速度Δv，此時的無翻滾狀態(tài)即被描述為：

換句話說，只要足球機器人的運行速度被控制在式(2)的上限和下限之間，它就不會在運動中翻滾。對于固定障礙物的無碰撞路徑，可以先將機器人運行環(huán)境假定為一個有邊界的二維場地，其中分布著若干靜態(tài)障礙物Ox1,Ox2,…,Oxn，機器人應(yīng)在每一個節(jié)點(障礙物附近)處有效的停止，并且轉(zhuǎn)向下一個節(jié)點，由此便產(chǎn)生從起點到終點的由幾條直線組成的無翻滾路徑。這里起點設(shè)為A，終點設(shè)為B。多目標(biāo)路徑設(shè)為L={l1,l2,…,ln}，li是指規(guī)劃路徑L的i節(jié)點，且

足球機器人路徑規(guī)劃是多目標(biāo)優(yōu)化，將路徑簡化為

滿足

對于f1(l),f2(l),f3(l)我們用如下方程作出定義。

定義1表示路徑總長度的長度指數(shù)由下式確定：

定義2表示所有向量路徑段角度和的平滑指數(shù)由下式確定：

定義3表示每個路徑段和障礙物之間最短距離和的安全指數(shù)由下式獲得：

當(dāng)滿足這4個條件：

機器人將無翻滾地完成路徑的尋優(yōu)。在這4個條件中，條件(a)是對機器人速度范圍的限定，機器人在此速度范圍內(nèi)運動，才可能保持穩(wěn)定的狀態(tài)，不會在運動過程中未碰上障礙物的情況下翻滾；條件(b)、(c)、(d)是機器人在條件(a)的范圍內(nèi)運動所要求的目標(biāo)函數(shù)，當(dāng)3個函數(shù)都是極小值時，所得曲線是機器人路徑規(guī)劃的最優(yōu)目標(biāo)。

2 改進型遺傳算法的多目標(biāo)路徑規(guī)劃

2.1 個體編碼

對于個體固定長度的編碼方法主要采用一組固定的一維坐標(biāo)尺寸，也就是將機器人工作領(lǐng)域的X軸分成n段，保證了每個獨立節(jié)點在X軸上都有其固定的坐標(biāo)[8]。這種編碼方法可以簡單而直接地看作在Y軸的一維編碼。但是由于在X軸上獨立節(jié)點總數(shù)和每個節(jié)點間的距離是固定的，所以缺乏靈活性。因此，采用可變長度的二維浮點數(shù)編碼：(x1,y1)→(x2,y2)→…→(xnc,ync)。個體編碼長度是可變的，其值取決于機器人工作領(lǐng)域中障礙物分布的復(fù)雜度。在集中的地區(qū)增加障礙物數(shù)量，使路徑更加平滑和安全，但在只有幾個障礙物的地區(qū)將會減小自適應(yīng)。這種編碼方式將會加強搜索的精度和靈活性。此外，一定要保證每個獨立節(jié)點的X坐標(biāo)在個體編碼中是有序增殖的，這樣才能保證在進化過程中路徑是保持向需要的方向進化的[8]。

2.2 種群初始化

種群初始化的方法是根據(jù)遺傳算法隨機選擇的。但是，隨著機器人路徑規(guī)劃在有隨機障礙物的環(huán)境中進行，隨機初始化路徑在進化過程中總是無效的。為了解決路徑規(guī)劃中的種群初始化問題，學(xué)者們提出了多種改進方法。例如，申曉寧[9]等認(rèn)為，因為起點和終點是已知的，當(dāng)環(huán)境中沒有障礙物的時候，兩點間的直線最短，此時該直線應(yīng)該是最短且最平滑的路徑。在此類信息的啟發(fā)下，這條直線附近將隨機生成一些初始化路徑。然而，只在比較理想的環(huán)境中這種方法才可以獲得較好的效果，一旦應(yīng)用在復(fù)雜環(huán)境中，特別是在起點和終點間有障礙物的情況下，這種方法的有效性是很低的。

2.3 蟻群遺傳算法

機器人路徑問題可看做是一個組合優(yōu)化的問題，以S=S1,S2,…,Sn為基本組成部分的問題。一個子集C代表一個解決方案：F是可行解的集合，當(dāng)且僅當(dāng)C∈F時，C是可行解。在解的范圍上定義成本函數(shù)Y，Y：2s→R，最終找出最優(yōu)解C*，C*∈F，且Y(C*)≤Y(C)，C∈F。他們采用基于雙參數(shù)的隨機局部決策策略移動，也就是路徑和生物信息素。通過移動，每個螞蟻構(gòu)建一個問題的解決方案[5]。

即使所有機器人都找到了可行解，因賽場上的信息具有時變性，所以得到的可行解未必是最優(yōu)解，因此，必須根據(jù)局部信息和全局信息對生物信息素進行更新，并要滿足以下原則[10]：

式中:Lk----機器人走過的路徑長度。

應(yīng)用蟻群遺傳算法進行機器人路徑規(guī)劃主要包括以下流程[11]：

1)初始化。

①設(shè)置系統(tǒng)的初始參數(shù)：出發(fā)點、目標(biāo)點、迭代次數(shù)。

②設(shè)置初始的信息素?fù)]發(fā)系數(shù)：各條路徑上的信息素強度、各障礙物信息素值。

③將每個機器人(螞蟻)放置在初始狀態(tài)節(jié)點上。

2)主回路(迭代次數(shù)的總數(shù))。

①構(gòu)建蟻群決策方案：計算每只螞蟻的路徑選擇概率；每只螞蟻應(yīng)用轉(zhuǎn)移函數(shù)構(gòu)建路徑，從一個節(jié)點移動到另一個節(jié)點。

②通過局部搜索計算螞蟻爬行路徑的優(yōu)化函數(shù)。

③檢測最佳路徑：根據(jù)信息的動態(tài)更新，及時進行路徑尋優(yōu)。

④更新軌跡：此輪路徑規(guī)劃結(jié)束。調(diào)整每條路徑上的信息素比例，完成每個螞蟻的信息素更新。

⑤根據(jù)信息素步道，確定所選路徑是否為最優(yōu)解，若是，則輸出最優(yōu)解；否則繼續(xù)進行機器人路徑規(guī)劃。

在沒有障礙物的情況下，足球機器人按式(1)和式(2)確定平移的速度和框架。

3 計算機仿真

本系統(tǒng)的計算機仿真是應(yīng)用MS Visual Studio環(huán)境編程實驗的。規(guī)劃路徑如圖1所示。

圖1 文中算法得到的路徑

由于路徑段與障礙物之間的間隙過小，在運動過程中，可能會發(fā)生碰撞。文中所用算法得到的路徑長度短、平滑，與障礙物之間也有一些安全間隙，以此來保證一定的安全性。

蟻群遺傳算法仿真路徑如圖2所示。

圖2 蟻群遺傳算法仿真路徑

由圖2可以得出蟻群遺傳算法仿真路徑簡化曲線，如圖3所示。

圖3 蟻群遺傳算法仿真路徑簡化曲線

對于圖3分析見表1。

表1 路徑曲線圖分析表

注：Ⅰ.紅色曲線； Ⅱ.藍(lán)色曲線； Ⅲ.綠色曲線。

經(jīng)過分段比較：在長度指數(shù)方面，紅色曲線長度最短，藍(lán)色次之，綠色最長；在平滑指數(shù)方面，紅色曲線最優(yōu)，藍(lán)色次之，綠色較差；在安全指數(shù)方面，紅色和藍(lán)色最優(yōu)，綠色次之。綜合考慮各項指數(shù)，紅色最優(yōu)，即文中所用算法得到的曲線最優(yōu)。

4 結(jié) 語

對機器人運動過程中的無翻滾和無側(cè)翻的路徑規(guī)劃,該方法有望應(yīng)用于不平地形上偵查和勘測。而基于混合算法的多目標(biāo)機器人路徑規(guī)劃算法也被提出，它將傳統(tǒng)算法中單一的以路徑最短為目標(biāo)，擴展為3個目標(biāo)：長度、安全性、平滑性。這種算法在尋求最優(yōu)路徑時是比較有效的。計算機仿真結(jié)果表明，雖然文中提出的智能算法還存在著一些有待提高的問題，但是它解決了一些傳統(tǒng)算法的缺點，在實際情況下也是比較可行的，使得機器人路徑的獲得更加具有靈活性。

[1] C Alexopoulos, P M Griffin. Path planning for a mobile robot IEEE trans on system [J]. Man and Cybernetics,1992,22(2):318-322.

[2] Y Keron, J Borenstein. Potential field methods and their inherent limitation for mobile robot navigation [C]//Proceedings of the Internation Conference on Robotics and Automation. California: [s.n.],1991:1398-1404.

[3] 白文峰,劉紀(jì)陽,雷宇欣.微分進化優(yōu)化神經(jīng)網(wǎng)絡(luò)KUKA機器人逆運動學(xué)求解[J].長春工業(yè)大學(xué)學(xué)報：2017,38(2):162-166.

[4] Jae Byung Park. Multiple mobile robot path planning for rollover prevention and collision avoidance [C]//2011 11thInternational Conference on Control,Automation and Systems. Korea: [s.n.],2011:1732-1734.

[5] S Geetha, G Muthu Chitra, V Jayalakshmi. Multi objective mobile robot path planning based on hybrid Algorithm [J]. [S.l.]: Anna University of Technology,2011:251-255.

[6] J B Park, J H Lee, B H Lee. Rollover-free navigation for a mobile agent in an unstructured environment [J]. IEEE Trans on SMC-Part B Cybernetics,2006，36(4)：835-848.

[7] Zheng Jinhua. Multi-objective evolutionary algorithm and its application[M]. [S.l.]: Science Press,2007.

[8] 魏厚忠，薛丹，焦立奇，等.基于KUKA6自由度機器人的誤差分析與仿真[J].長春工業(yè)大學(xué)學(xué)報：自然科學(xué)版，2012,33(3):328-332.

[9] 申曉寧，郭毓，陳慶偉，等.基于多目標(biāo)優(yōu)化的撓性航天器姿態(tài)機動路徑規(guī)劃[J].南京理工大學(xué)學(xué)報，2006,30(6)：659-663.

[10] 潘攀.足球機器人路徑規(guī)劃算法的研究及其仿真[J].計算機仿真，2012,29(4)：181-184.

[11] M A Nada, AL-Salami. System evolving using ant colony optimization Algorithm[J]. Journal of Computer Science，2009,5(5):380-387.

Studyonobstacleavoidanceandrolloverofasoccerrobot

XUE Dan1,2, SUN Xiqing1, BAI Wenfeng1*

(1.School of Electrical & Electronic Engineering, Changchun University of Technology, Changchun 130012， China；2.College of Optical and Electronical Information Changchun University of Science and Technology, Changchun 130114， China)

With the extended map, the improved genetic algorithm and combined ant colony with genetic algorithm are used to optimize the following objects of a soccer robot such as path length, smoothness and safety.

robot； path planning； extended map； genetic algorithm； genetic algorithm and ant colony algorithm.

2017-01-25

薛 丹(1986-)，女，漢族，吉林長春人，長春工業(yè)大學(xué)碩士研究生，主要從事智能控制及軌道交通信號與控制方向研究,E-mail:273518365@qq.com. *通訊作者：白文峰(1962-)，男，漢族，吉林長春人，長春工業(yè)大學(xué)教授，碩士，主要從事智能儀器與智能控制方向研究,E-mail:baiwenfeng@ccut.edu.cn.

10.15923/j.cnki.cn22-1382/t.2017.5.12

TP 242.6

A

1674-1374(2017)05-0472-05