薛 丹, 孫喜慶, 白文峰*

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

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

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

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

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

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

0 引 言

近年來，足球機(jī)器人各方面的研究工作不斷深入，其中路徑規(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)的缺點(diǎn)。

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

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

1 問題描述

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

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

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

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

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

滿足

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

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

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

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

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

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

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

2.1 個體編碼

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

2.2 種群初始化

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

2.3 蟻群遺傳算法

機(jī)器人路徑問題可看做是一個組合優(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ù)的隨機(jī)局部決策策略移動，也就是路徑和生物信息素。通過移動，每個螞蟻構(gòu)建一個問題的解決方案[5]。

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

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

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

1)初始化。

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

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

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

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

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

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

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

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

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

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

3 計算機(jī)仿真

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

圖1 文中算法得到的路徑

由于路徑段與障礙物之間的間隙過小，在運(yùn)動過程中，可能會發(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)，綠色次之。綜合考慮各項(xiàng)指數(shù)，紅色最優(yōu)，即文中所用算法得到的曲線最優(yōu)。

4 結(jié) 語

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

[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ì)陽,雷宇欣.微分進(jìn)化優(yōu)化神經(jīng)網(wǎng)絡(luò)KUKA機(jī)器人逆運(yùn)動學(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ī)器人的誤差分析與仿真[J].長春工業(yè)大學(xué)學(xué)報：自然科學(xué)版，2012,33(3):328-332.

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

[10] 潘攀.足球機(jī)器人路徑規(guī)劃算法的研究及其仿真[J].計算機(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