足球機(jī)器人之策略及路徑設(shè)計

1、Department of Electrical Engineering, Southern Taiwan University足球機(jī)器人之策略及路徑設(shè)計足球機(jī)器人之策略及路徑設(shè)計 研究生：王國揚(yáng)研究生：王國揚(yáng)指導(dǎo)教授：邱俊賢博士指導(dǎo)教授：邱俊賢博士Proceedings of 2006 CACS Automatic Control Conference St. Johns University, Tamsui, Taiwan, Nov. 10-11, 2006Robotic Interaction Learning Lab1Department of Electrical Engineeri

2、ng, Southern Taiwan University大綱大綱n摘要n前言n研究動機(jī)與目的n文獻(xiàn)探討n足球機(jī)器人之策略設(shè)計n廣義預(yù)測控制應(yīng)用n結(jié)論及未來發(fā)展n參考文獻(xiàn)Robotic Interaction Learning Lab2Department of Electrical Engineering, Southern Taiwan University摘要摘要n本文主要探討足球機(jī)器人策略以及路徑設(shè)計與研究。提出使用模糊控制的方法快速分配每個機(jī)器人角色及職責(zé)的方法。n其中，模糊控制器是根據(jù)我方機(jī)器人到達(dá)目標(biāo)的距離及角度決定每一支機(jī)器人的角色及任務(wù)。在策略方面我們將提出射門模式以及避障

3、模式來幫助我方機(jī)器人得分。n在路徑規(guī)劃上，提出一套以支援向量機(jī)為理論修正我方機(jī)器人路徑，並且使用同樣的方法修正我方機(jī)器人到達(dá)目標(biāo)的最佳速度。n最後加入廣義預(yù)測控制來幫助我方機(jī)器人預(yù)估目標(biāo)下一次的位置或動作來幫助整個策略更加完善。Robotic Interaction Learning Lab3Department of Electrical Engineering, Southern Taiwan University前言前言n在生產(chǎn)製造業(yè)裡，單一機(jī)器人可以取代人力是無庸置疑，但是在複雜的工作環(huán)境下，多重式機(jī)器人合作工作方式會比單一機(jī)器人來操控所有的工作來的有效率但也較為複雜，例如在系統(tǒng)架構(gòu)中

4、如何決定角色分配，當(dāng)系統(tǒng)不理想時如何調(diào)整角色分配。n多重式機(jī)器人系統(tǒng)近年來為許多科學(xué)家所深入討論以及研究，足球機(jī)器人就是多重式機(jī)器人的一種，所涉及領(lǐng)域包含控制理論、影像處理、人工智慧、感測訊號等。Robotic Interaction Learning Lab4Department of Electrical Engineering, Southern Taiwan University研究動機(jī)與目的研究動機(jī)與目的n機(jī)器人足球賽的構(gòu)想起源於加拿大哥倫比亞大學(xué)Alan Mackworth教授發(fā)表的一篇”O(jiān)n Seeing Robots”1的論文，之後受到學(xué)者熱烈的迴響，認(rèn)為足球機(jī)器人比賽跨多種學(xué)

5、術(shù)領(lǐng)域整合了機(jī)器人學(xué)、通訊與電腦技術(shù)、決策與對策，模糊神經(jīng)網(wǎng)路、人工智慧控制等。 n它最終目標(biāo)在公元2050年的世界盃足賽，發(fā)展出能贏人類足球員的人型足球機(jī)器人。Robotic Interaction Learning Lab5Department of Electrical Engineering, Southern Taiwan University文獻(xiàn)探討文獻(xiàn)探討1 1n黃玉翰，機(jī)器人足球賽兩階段控制策略之設(shè)計與研究機(jī)器人足球賽兩階段控制策略之設(shè)計與研究，國立成功大學(xué)電機(jī)工程學(xué)系碩士論文，2005。 Robotic Interaction Learning Lab6Department

6、of Electrical Engineering, Southern Taiwan University文獻(xiàn)探討文獻(xiàn)探討2 2n陳建成，以適應(yīng)性以適應(yīng)性 Q-Learning 為基礎(chǔ)發(fā)展足球機(jī)器為基礎(chǔ)發(fā)展足球機(jī)器人合作策略人合作策略，國立中正大學(xué)電機(jī)工程研究所碩士論文，2002。 Robotic Interaction Learning Lab7Department of Electrical Engineering, Southern Taiwan University文獻(xiàn)探討文獻(xiàn)探討3 3n陳柏堯，機(jī)器人足球員之硬體製作、路徑規(guī)畫與機(jī)器人足球員之硬體製作、路徑規(guī)畫與競爭策略競爭策略，國立

7、雲(yún)林科技大學(xué)電機(jī)工程學(xué)系碩士論文，2000。Robotic Interaction Learning Lab8Department of Electrical Engineering, Southern Taiwan University足球機(jī)器人之策略設(shè)計足球機(jī)器人之策略設(shè)計n支援向量機(jī)說明n支援向量機(jī)修正機(jī)器人角度n支援向量機(jī)修正機(jī)器人速度n角色分配n射門角度n避障模式Robotic Interaction Learning Lab9Department of Electrical Engineering, Southern Taiwan University支援向量機(jī)說明支援向量機(jī)說明n

8、支援向量機(jī)(Support Vector Machine，簡稱SVM)由貝爾實(shí)驗(yàn)室Vapnik博士於1990年依統(tǒng)計學(xué)習(xí)理論為基礎(chǔ)，而發(fā)展出來的機(jī)器學(xué)習(xí)系統(tǒng)。其基本思維為建構(gòu)樣本堅或特徵空間中的最優(yōu)超平面，使得超平面與不同類別的樣本集之間的距離為最大。支援向量機(jī)是一個有效訓(xùn)練的機(jī)器學(xué)習(xí)系統(tǒng)。首先，我們將討論支援向量分類。 Robotic Interaction Learning Lab10Department of Electrical Engineering, Southern Taiwan University支援向量分類支援向量分類n支援向量機(jī)的目的主要是設(shè)計一個容易計算的機(jī)器學(xué)習(xí)方法，

9、在高維度的特徵空間裡面找到分類超平面並找出其最佳歸納的方式，同時，它具備處理大約十萬個訓(xùn)練樣本的能力。這個歸納的方法主要是清楚地引導(dǎo)如何提升控制能力以及防止在所控制的超平面中超越最大極限，最佳化的方法就是利用數(shù)學(xué)技巧去尋找SVM的最佳超平面，不同的歸納法將會有不同的限制，就像以下這種演算法：就是極限最大化，極限所分類的就是支援向量的個數(shù)，接下來我們將介紹最大極限分類的方法。 Robotic Interaction Learning Lab11Department of Electrical Engineering, Southern Taiwan University最大極限分類最大極限分類n

10、最大極限方類法主要是在最大分類超平面上分離資料，並且判定範(fàn)圍並不能依靠維度空間，這個分離的方法將會在核函數(shù)歸納找到其特徵空間，支援向量機(jī)所使用的第一個策略就是最大極限分類法，那就是在核函數(shù)歸納的特徵空間中找到其最大極限超平面。這個策略將會減少系統(tǒng)的凸面問題，使在線性不等式的約束情況中的二次函數(shù)縮減到最小。Robotic Interaction Learning Lab12Department of Electrical Engineering, Southern Taiwan University支援向量機(jī)修正機(jī)器人角度支援向量機(jī)修正機(jī)器人角度 1/91/9n在足球機(jī)器人中，路徑選擇扮演相當(dāng)重

11、要的角色。我們希望機(jī)器人能在最短時間內(nèi)到達(dá)目標(biāo)點(diǎn)，因此我們設(shè)計一套以支援向量機(jī)為基礎(chǔ)的最佳路徑設(shè)計，以確保能在最短時間及最佳路徑到達(dá)目標(biāo)。支援向量機(jī)的方法是從線性可分情況下的最優(yōu)分類超平面發(fā)展而來，所謂的最優(yōu)分類面就是要求分類面不但能將兩類樣本正確分開，而且使分類間隔為最大。如圖1所示：Robotic Interaction Learning Lab13Department of Electrical Engineering, Southern Taiwan University支援向量機(jī)修正機(jī)器人角度支援向量機(jī)修正機(jī)器人角度 2/92/9圖1：支援向量機(jī)示意圖Robotic Interact

12、ion Learning Lab14Department of Electrical Engineering, Southern Taiwan University支援向量機(jī)修正機(jī)器人角度支援向量機(jī)修正機(jī)器人角度 3/93/9Step 1.由圖2我們可以計算出機(jī)器人與必需航向目 標(biāo)的角度：RxxyyRbRb1tan圖1：機(jī)器人到達(dá)目標(biāo)的距離與機(jī)器人轉(zhuǎn)向目標(biāo)的夾角示意圖Robotic Interaction Learning Lab15Department of Electrical Engineering, Southern Taiwan University支援向量機(jī)修正機(jī)器人角度支援向量機(jī)

13、修正機(jī)器人角度 4/94/9Step 2. 假設(shè)訓(xùn)練數(shù)據(jù)為：Step 3.為了找出分割超平面，需求解下面的二次 規(guī)劃問題，其中約束條件為： 2,2, 2 , 1 ,1,1inillyliRyy500, 2 , 1,22 22 iybwybwiiii500, 2 , 1,2 ibwyiiRobotic Interaction Learning Lab16Department of Electrical Engineering, Southern Taiwan University支援向量機(jī)修正機(jī)器人角度支援向量機(jī)修正機(jī)器人角度 5/95/9並求解下列函數(shù)的最小值：Step 4.由於上式為二次方程

14、式，而限制式為線性方 程式，此形式屬於典型的二次規(guī)劃問題，因 此使用日格朗乘子解決這個具有線性約束的 二次規(guī)劃問題，可得： 221ww 0,221,50012iiiiibwywbwLRobotic Interaction Learning Lab17Department of Electrical Engineering, Southern Taiwan University支援向量機(jī)修正機(jī)器人角度支援向量機(jī)修正機(jī)器人角度 6/96/9Step 5.但是如此的模式在使用支援向量機(jī)時，仍不 易求出最佳解，解決的方法是找出其對偶問 題：Step 6.代入之後可以求得新的為：500150010iii

15、iiiiiywywwL05001iiiybLjijijijiiDyyL,21Robotic Interaction Learning Lab18Department of Electrical Engineering, Southern Taiwan University支援向量機(jī)修正機(jī)器人角度支援向量機(jī)修正機(jī)器人角度 7/97/9Step 7.在求對偶問題的最佳解時，每一個日格朗係 數(shù)都會對應(yīng)到每一筆訓(xùn)練資料；如果代表該 資料是此問題的支援向量，會落在區(qū)分平面 的邊界上。最後可得到最終的分類函數(shù)： 5001sgniiiibyfRobotic Interaction Learning Lab1

16、9Department of Electrical Engineering, Southern Taiwan University支援向量機(jī)修正機(jī)器人角度支援向量機(jī)修正機(jī)器人角度 8/98/9圖4：使用支援向量機(jī)時機(jī)器人到達(dá)目標(biāo)路徑圖3：未使用支援向量機(jī)時機(jī)器人到達(dá)目標(biāo)路徑Robotic Interaction Learning Lab20Department of Electrical Engineering, Southern Taiwan University支援向量機(jī)修正機(jī)器人角度支援向量機(jī)修正機(jī)器人角度 9/99/9圖6：使用支援向量機(jī)時機(jī)器人到達(dá)目標(biāo)路徑圖5：未使用支援向量機(jī)時機(jī)器

17、人到達(dá)目標(biāo)路徑Robotic Interaction Learning Lab21Department of Electrical Engineering, Southern Taiwan University支援向量機(jī)修正機(jī)器人速度支援向量機(jī)修正機(jī)器人速度 1/61/6n首先，我們將設(shè)計一個模糊控制器去設(shè)計足球機(jī)器人左右輪的速度，並且使用支援向量機(jī)來改善模糊控制器，使模糊控制器的輸出是最佳值。我們將使用與前面相同的數(shù)學(xué)結(jié)構(gòu)支援向量機(jī)來幫助我們找尋到最佳的機(jī)器人速度。Robotic Interaction Learning Lab22Department of Electrical Engin

18、eering, Southern Taiwan University支援向量機(jī)修正機(jī)器人速度支援向量機(jī)修正機(jī)器人速度 2/62/6n首先，我們可以設(shè)計一個任意的模糊控制器。並且任意定義規(guī)則庫。圖7：距離歸屬函數(shù)圖8：角度歸屬函數(shù)Robotic Interaction Learning Lab23Department of Electrical Engineering, Southern Taiwan University支援向量機(jī)修正機(jī)器人速度支援向量機(jī)修正機(jī)器人速度 3/63/6n輸出經(jīng)由模糊規(guī)則庫解模糊化計算出左右輪個別轉(zhuǎn)速，此規(guī)則庫具有49條規(guī)則，如表1所示。接著將使用重心解模糊化法來計

19、算機(jī)器人左右輪個別轉(zhuǎn)速。表1：模糊規(guī)則庫Robotic Interaction Learning Lab24Department of Electrical Engineering, Southern Taiwan University支援向量機(jī)修正機(jī)器人速度支援向量機(jī)修正機(jī)器人速度 4/64/6n接著我們定義一個簡單的運(yùn)動方程式來幫助支援向量機(jī)的分類及訓(xùn)練：llrrrrlllraarsrprwrqsnpmwyqxdrsincossincosRobotic Interaction Learning Lab25Department of Electrical Engineering, South

20、ern Taiwan University支援向量機(jī)修正機(jī)器人速度支援向量機(jī)修正機(jī)器人速度 5/65/6n定義狀態(tài)變數(shù)為：n我們可以得到狀態(tài)方程式：n最後可得到：lrxxsxpxwxqxnxmxyxxx10987654321 , , , , , , , ,TlrrrllTaarrrrspwqxxxxxxxxxx sin cos sin cos 1098765432 165xxGVl87xxGVrRobotic Interaction Learning Lab26Department of Electrical Engineering, Southern Taiwan University支援向

21、量機(jī)修正機(jī)器人速度支援向量機(jī)修正機(jī)器人速度 6/66/6圖9：使用SVM得到的速度圖10：使用一般FLC得到的速度Robotic Interaction Learning Lab27Department of Electrical Engineering, Southern Taiwan University修正角度及速度結(jié)果修正角度及速度結(jié)果Robotic Interaction Learning Lab28Department of Electrical Engineering, Southern Taiwan University角色分配角色分配 1/31/3n在足球機(jī)器人比賽當(dāng)中，任務(wù)

22、分配扮演相當(dāng)重要的角色。五個足球機(jī)器人中，指派一機(jī)器人為守門員，另一機(jī)器人為防守員，其餘三個機(jī)器人當(dāng)為攻擊角色。但是當(dāng)三個機(jī)器人同時追球時，反而不會產(chǎn)生好的效果，所以我們希望只利用一機(jī)器人當(dāng)主攻擊者角色，其它兩個機(jī)器人當(dāng)作助攻者角色。因此我們?nèi)齻€攻擊機(jī)器人的任務(wù)不是固定的，而是隨著球在場地上不同的情形，主、助攻的角色將會隨時轉(zhuǎn)換。Robotic Interaction Learning Lab29Department of Electrical Engineering, Southern Taiwan University角色分配角色分配 2/32/3n我們可以把模糊規(guī)則定義如下：65,The

23、n 60or 60 and 40 if:Rule954,Then 6030or 6030 and 40 if:Rule843,Then 3030 and 40 if:Rule754,Then 60or 60 and 4020 if:Rule643,Then 6030or 6030 and 4020 if:Rule532,Then 3030 and 4020 if:Rule443,Then 60or 60 and 20 if:Rule332,Then 6030or 6030 and 20 if:Rule2,Then 3030 and 20 if:Rule1ddfwdddfwdddfwdddfwd

24、ddfwdddfwdddfwdddfwdddfwd輸出w代表經(jīng)由模糊運(yùn)算得到的權(quán)重值Robotic Interaction Learning Lab30Department of Electrical Engineering, Southern Taiwan University角色分配角色分配 3/33/3n在一般區(qū)域裡，我們再比較三個機(jī)器人的值，就可以把最小值的機(jī)器人定義為主要追逐球的角色，其餘的兩個機(jī)器人則扮演幫助的角色。 n在防守區(qū)域裡，除了守門員及防守者之外，其餘我方的機(jī)器人也必須扮演攔截球以及妨礙對方機(jī)器人射門的動作，也藉由判斷三個機(jī)器人的值來決定最小值的我方機(jī)器人作攔截球的動作其

25、餘兩個機(jī)器人則扮演妨礙對方機(jī)器人射門的任務(wù)。 Robotic Interaction Learning Lab31Department of Electrical Engineering, Southern Taiwan University射門角度射門角度 1/31/3n當(dāng)我方機(jī)器人把球帶到敵方球門區(qū)域時，為了增加得分的機(jī)會，在射門時不希望我方機(jī)器人只是盲目的攻擊，所以我們增加一個射門角度的判斷來幫助得分的能力。如圖11所示： Robotic Interaction Learning Lab32Department of Electrical Engineering, Southern Ta

26、iwan University射門角度射門角度 2/32/32222lbPbPLbPbPyyxxmxxyyRxxyypRPRP1tanRxxyyaRbRb1tan圖11:射門角度示意圖首先我們可以知道 xxyymbgbgL1 yxyxyxRRRggbb,mmLL21，而且可以知道 Robotic Interaction Learning Lab33Department of Electrical Engineering, Southern Taiwan University射門角度射門角度 3/33/3圖12:到達(dá)攻擊點(diǎn)射門角度示意圖Robotic Interaction Learning L

27、ab34Department of Electrical Engineering, Southern Taiwan University射門角度結(jié)果射門角度結(jié)果Robotic Interaction Learning Lab35Department of Electrical Engineering, Southern Taiwan University避障模式避障模式 1/41/4n當(dāng)我方機(jī)器人在場上執(zhí)行追球的動作時，如果有敵方機(jī)器人位於我方路徑上，那麼我方機(jī)器人將無法準(zhǔn)確到達(dá)目標(biāo)而會產(chǎn)生碰撞，所以我們必須設(shè)計一避障規(guī)劃，已使機(jī)器人在到達(dá)目標(biāo)的過程中不會有所阻礙如圖13所示： Robotic

28、 Interaction Learning Lab36Department of Electrical Engineering, Southern Taiwan University避障模式避障模式 2/42/4圖13:避障示意圖 Robotic Interaction Learning Lab37Department of Electrical Engineering, Southern Taiwan University避障模式避障模式 3/43/4mxxyymLbrbrL212L2l2222lrPrPLrPrPyyxxmxxyyyxPP ,bxLyLm 1:11. 我們可以得知2. 給定

29、 線段長度為 ：可求得：Robotic Interaction Learning Lab38Department of Electrical Engineering, Southern Taiwan University避障模式避障模式 4/44/43L4L3l 222222331yyxxyxPAPAllmbAmAlyxAA ,yxCC ,3. 給定 以及 線段長度為 ：我們就可以得到 Robotic Interaction Learning Lab39Department of Electrical Engineering, Southern Taiwan University避障結(jié)果避障結(jié)

30、果Robotic Interaction Learning Lab40Department of Electrical Engineering, Southern Taiwan University廣義預(yù)測控制應(yīng)用廣義預(yù)測控制應(yīng)用 1/71/7n當(dāng)我們經(jīng)由前面得到機(jī)器人的最佳速度之後，就可以運(yùn)用廣義預(yù)測控制來計算機(jī)器人的下一次位置，已達(dá)到更好的路徑以及更快速追尋到目標(biāo)。廣義預(yù)測控制的設(shè)計將可以幫我們更快速在下一取樣時間內(nèi)預(yù)測目標(biāo)下一次的位置。n當(dāng)結(jié)合前面所提到的最佳角度、最佳速度以及預(yù)測控制之後就可以從下面的步驟實(shí)現(xiàn)，以確保我們所提出的策略將會是一個有效的策略。Robotic Interact

31、ion Learning Lab41Department of Electrical Engineering, Southern Taiwan University廣義預(yù)測控制應(yīng)用廣義預(yù)測控制應(yīng)用 2/72/7nStep 1.雖然這是一個非線性運(yùn)動，但是我們可以用極短的取樣時間來使系統(tǒng)變成線性運(yùn)動狀態(tài)。nStep 2.首先我們可以從圖14 得到以下的資訊：（1）機(jī)器人的位置 ，（2）目標(biāo)上一次位置 ，（3）目標(biāo)現(xiàn)在位置 ，並設(shè)立取樣時間 。yxRR ,yxGFGF ,yxGG ,0T圖14 取樣時間Robotic Interaction Learning Lab42Department of

32、Electrical Engineering, Southern Taiwan University廣義預(yù)測控制應(yīng)用廣義預(yù)測控制應(yīng)用 3/73/7nStep 3.經(jīng)由目標(biāo)上一次位置以及現(xiàn)在位置，我們可以由下列的方程式計算出它們之間的距離 ，以及目標(biāo)移動速度 。 nStep 4.當(dāng)計算出目標(biāo)速度 之後，我們可以利用目標(biāo)速度 、目標(biāo)方向以及取樣時間 ，設(shè)計一廣義預(yù)測控制來估算目標(biāo)下一次位置 ，如下列方程式以及圖15所表示： 0d0V220yyxxGGFGGFd000/TdV 0V0V0TyxGLGL ,xxyyxxyyyyxxGLGGLGGGFGGFGLGGLGd220Robotic Intera

33、ction Learning Lab43Department of Electrical Engineering, Southern Taiwan University廣義預(yù)測控制應(yīng)用廣義預(yù)測控制應(yīng)用 4/74/7n接下來將把上列的方程式解聯(lián)立求得目標(biāo)下一次位置 。yxGLGL ,圖15 目標(biāo)下一次位置Robotic Interaction Learning Lab44Department of Electrical Engineering, Southern Taiwan University廣義預(yù)測控制應(yīng)用廣義預(yù)測控制應(yīng)用 5/75/7nStep 5.接著將透過機(jī)器人的中心速度 ，以及機(jī)器人到達(dá)現(xiàn)在目標(biāo)的距離 ，計算出機(jī)器人到達(dá)目標(biāo)所需的時間 ，如下列方程式所表示：（當(dāng)中 代表機(jī)器人左輪速度、 代表機(jī)器人右輪速度）。n比較 以及 ，如果 ，那機(jī)器人將會追尋我們所預(yù)測的目標(biāo)下一次位置；如果 ，機(jī)器人將追尋目標(biāo)現(xiàn)在位置。重複Step