足球机器人之策略及路径设计

DepartmentofElectricalEngineering,SouthernTaiwanUniversityRoboticInteractionLearningLab1足球機器人之策略及路徑設計研究生：王國揚指導教授：邱俊賢博士Proceedingsof2006CACSAutomaticControlConferenceSt.John'sUniversity,Tamsui,Taiwan,Nov.10-11,2006DepartmentofElectricalEngineering,SouthernTaiwanUniversity2RoboticInteractionLearningLab大綱摘要前言研究動機與目的文獻探討足球機器人之策略設計廣義預測控制應用結論及未來發展參考文獻DepartmentofElectricalEngineering,SouthernTaiwanUniversity3RoboticInteractionLearningLab摘要本文主要探討足球機器人策略以及路徑設計與研究。提出使用模糊控制的方法快速分配每個機器人角色及職責的方法。其中，模糊控制器是根據我方機器人到達目標的距離及角度決定每一支機器人的角色及任務。在策略方面我們將提出射門模式以及避障模式來幫助我方機器人得分。在路徑規劃上，提出一套以支援向量機為理論修正我方機器人路徑，並且使用同樣的方法修正我方機器人到達目標的最佳速度。最後加入廣義預測控制來幫助我方機器人預估目標下一次的位置或動作來幫助整個策略更加完善。DepartmentofElectricalEngineering,SouthernTaiwanUniversity4RoboticInteractionLearningLab前言在生產製造業裡，單一機器人可以取代人力是無庸置疑，但是在複雜的工作環境下，多重式機器人合作工作方式會比單一機器人來操控所有的工作來的有效率但也較為複雜，例如在系統架構中如何決定角色分配，當系統不理想時如何調整角色分配。多重式機器人系統近年來為許多科學家所深入討論以及研究，足球機器人就是多重式機器人的一種，所涉及領域包含控制理論、影像處理、人工智慧、感測訊號等。DepartmentofElectricalEngineering,SouthernTaiwanUniversity5RoboticInteractionLearningLab研究動機與目的機器人足球賽的構想起源於加拿大哥倫比亞大學AlanMackworth教授發表的一篇”OnSeeingRobots”[1]的論文，之後受到學者熱烈的迴響，認為足球機器人比賽跨多種學術領域整合了機器人學、通訊與電腦技術、決策與對策，模糊神經網路、人工智慧控制等。它最終目標在公元2050年的世界盃足賽，發展出能贏人類足球員的人型足球機器人。DepartmentofElectricalEngineering,SouthernTaiwanUniversity6RoboticInteractionLearningLab文獻探討﹙1﹚黃玉翰，機器人足球賽兩階段控制策略之設計與研究，國立成功大學電機工程學系碩士論文，2005。DepartmentofElectricalEngineering,SouthernTaiwanUniversity7RoboticInteractionLearningLab文獻探討﹙2﹚陳建成，以適應性Q-Learning為基礎發展足球機器人合作策略，國立中正大學電機工程研究所碩士論文，2002。DepartmentofElectricalEngineering,SouthernTaiwanUniversity8RoboticInteractionLearningLab文獻探討﹙3﹚陳柏堯，機器人足球員之硬體製作、路徑規畫與競爭策略，國立雲林科技大學電機工程學系碩士論文，2000。危機感知行為模組攻擊防禦感知競爭感知方位感知決策中心影像處理後的資料最佳競爭策略DepartmentofElectricalEngineering,SouthernTaiwanUniversity9RoboticInteractionLearningLab足球機器人之策略設計支援向量機說明支援向量機修正機器人角度支援向量機修正機器人速度角色分配射門角度避障模式DepartmentofElectricalEngineering,SouthernTaiwanUniversity10RoboticInteractionLearningLab支援向量機說明支援向量機(SupportVectorMachine，簡稱SVM)由貝爾實驗室Vapnik博士於1990年依統計學習理論為基礎，而發展出來的機器學習系統。其基本思維為建構樣本堅或特徵空間中的最優超平面，使得超平面與不同類別的樣本集之間的距離為最大。支援向量機是一個有效訓練的機器學習系統。首先，我們將討論支援向量分類。DepartmentofElectricalEngineering,SouthernTaiwanUniversity11RoboticInteractionLearningLab支援向量分類支援向量機的目的主要是設計一個容易計算的機器學習方法，在高維度的特徵空間裡面找到分類超平面並找出其最佳歸納的方式，同時，它具備處理大約十萬個訓練樣本的能力。這個歸納的方法主要是清楚地引導如何提升控制能力以及防止在所控制的超平面中超越最大極限，最佳化的方法就是利用數學技巧去尋找SVM的最佳超平面，不同的歸納法將會有不同的限制，就像以下這種演算法：就是極限最大化，極限所分類的就是支援向量的個數，接下來我們將介紹最大極限分類的方法。DepartmentofElectricalEngineering,SouthernTaiwanUniversity12RoboticInteractionLearningLab最大極限分類最大極限方類法主要是在最大分類超平面上分離資料，並且判定範圍並不能依靠維度空間，這個分離的方法將會在核函數歸納找到其特徵空間，支援向量機所使用的第一個策略就是最大極限分類法，那就是在核函數歸納的特徵空間中找到其最大極限超平面。這個策略將會減少系統的凸面問題，使在線性不等式的約束情況中的二次函數縮減到最小。DepartmentofElectricalEngineering,SouthernTaiwanUniversity13RoboticInteractionLearningLab支援向量機修正機器人角度1/9在足球機器人中，路徑選擇扮演相當重要的角色。我們希望機器人能在最短時間內到達目標點，因此我們設計一套以支援向量機為基礎的最佳路徑設計，以確保能在最短時間及最佳路徑到達目標。支援向量機的方法是從線性可分情況下的最優分類超平面發展而來，所謂的最優分類面就是要求分類面不但能將兩類樣本正確分開，而且使分類間隔為最大。如圖1所示：DepartmentofElectricalEngineering,SouthernTaiwanUniversity14RoboticInteractionLearningLab支援向量機修正機器人角度2/9L:w+b=0L1:w+b=L2:w+b='''ww222iy2iy圖1：支援向量機示意圖DepartmentofElectricalEngineering,SouthernTaiwanUniversity15RoboticInteractionLearningLab支援向量機修正機器人角度3/9Step1.由圖2我們可以計算出機器人與必需航向目標的角度：RxxyyRbRb1tanRobot1Balld圖1：機器人到達目標的距離與機器人轉向目標的夾角示意圖DepartmentofElectricalEngineering,SouthernTaiwanUniversity16RoboticInteractionLearningLab支援向量機修正機器人角度4/9Step2.假設訓練數據為：Step3.為了找出分割超平面，需求解下面的二次規劃問題，其中約束條件為：2,2,,,2,1,,,,1,''1'inillyliRyy500,,2,1,2222''iybwybwiiii500,,2,1,2'ibwyiiDepartmentofElectricalEngineering,SouthernTaiwanUniversity17RoboticInteractionLearningLab支援向量機修正機器人角度5/9並求解下列函數的最小值：Step4.由於上式為二次方程式，而限制式為線性方程式，此形式屬於典型的二次規劃問題，因此使用日格朗乘子解決這個具有線性約束的二次規劃問題，可得：221ww0,221,,5001'2iiiiibwywbwLDepartmentofElectricalEngineering,SouthernTaiwanUniversity18RoboticInteractionLearningLab支援向量機修正機器人角度6/9Step5.但是如此的模式在使用支援向量機時，仍不易求出最佳解，解決的方法是找出其對偶問題：Step6.代入之後可以求得新的為：5001''50010iiiiiiiiywywwL05001iiiybLjijijijiiDyyL,''21DepartmentofElectricalEngineering,SouthernTaiwanUniversity19RoboticInteractionLearningLab支援向量機修正機器人角度7/9Step7.在求對偶問題的最佳解時，每一個日格朗係數都會對應到每一筆訓練資料；如果代表該資料是此問題的支援向量，會落在區分平面的邊界上。最後可得到最終的分類函數：5001''sgniiiibyfDepartmentofElectricalEngineering,SouthernTaiwanUniversity20RoboticInteractionLearningLab支援向量機修正機器人角度8/9圖4：使用支援向量機時機器人到達目標路徑圖3：未使用支援向量機時機器人到達目標路徑DepartmentofElectricalEngineering,SouthernTaiwanUniversity21RoboticInteractionLearningLab支援向量機修正機器人角度9/9圖6：使用支援向量機時機器人到達目標路徑圖5：未使用支援向量機時機器人到達目標路徑DepartmentofElectricalEngineering,SouthernTaiwanUniversity22RoboticInteractionLearningLab支援向量機修正機器人速度1/6首先，我們將設計一個模糊控制器去設計足球機器人左右輪的速度，並且使用支援向量機來改善模糊控制器，使模糊控制器的輸出是最佳值。我們將使用與前面相同的數學結構支援向量機來幫助我們找尋到最佳的機器人速度。DepartmentofElectricalEngineering,SouthernTaiwanUniversity23RoboticInteractionLearningLab支援向量機修正機器人速度2/6首先，我們可以設計一個任意的模糊控制器。並且任意定義規則庫。SMSMVSd(inch)0201030MBBVB405060NMNSZNBPSPMPB00300600900300600900圖7：距離歸屬函數圖8：角度歸屬函