PAGE足球機器人畢業(yè)論文PAGEPAGE57足球機器人畢業(yè)論文題目：足球機器人路徑規(guī)劃的研究與實現(xiàn)專業(yè)：自動化摘要足球機器人系統(tǒng)是一個典型的多智能體系統(tǒng)，是一個實時動態(tài)的對抗性的復(fù)雜環(huán)境，它為人工智能技術(shù)的理論研究和模型測試提供了一個標準的實驗平臺。路徑規(guī)劃是智能機器人的一個重要研究課題，在這樣一個具有高度實時性和競爭性的平臺上研究路徑規(guī)劃是一個極具挑戰(zhàn)性的課題。目前用于路徑規(guī)劃的方法很多，如人工勢場法、中垂線法、柵格法、貝塞爾曲線法、可視圖法及各種人工智能方法如遺傳算法，神經(jīng)網(wǎng)絡(luò)等等。但這些方法在高度動態(tài)性和實時性環(huán)境中的研究還都存在些問題，有待進一步完善。本課題從靜態(tài)環(huán)境中研究足球機器人的路徑規(guī)劃問題，全文主要包括如下內(nèi)容：第一章介紹了足球機器人的研究背景并在此基礎(chǔ)上簡單的介紹了足球機器人路徑規(guī)劃。第二章具體分析了足球機器人系統(tǒng)、路徑規(guī)劃策略以及足球機器人環(huán)境模型等問題。第三章分析了現(xiàn)今采用的路徑規(guī)劃典型算法：人工勢場法、柵格法、中垂線法和遺傳算法。第四章在對各種算法進行綜合分析的基礎(chǔ)上，將遺傳算法基于前人的基礎(chǔ)上加入種群間的遷移并應(yīng)用在本文的路徑規(guī)劃中。用matlab對遺傳算法和人工勢場法進行編程和仿真。最后，我們對全文內(nèi)容進行總結(jié)。關(guān)鍵詞：路徑規(guī)劃；足球機器人；遺傳算法；人工勢場；中垂線法AbstractSoccerrobotsystemisatypicalmulti-agentsystemandreal-timedynamiccompetitiveenvironment,whichprovidesastandardofexperimentalplatformforthetheoreticalresearchofartificialintelligencetechnologyandmodeltest.Pathplanningisoneofthemostimportantresearchsubjectsinintelligentrobot,andtheresearchofpathplanningisachallengingtaskontheplatformwithhighlyreal-timeandcompetitive.Recentlymanymethodsareusedinpath-planning,suchasartificialpotentialfield,theperpendicularbisectormethod,thegrid,Besselmethodandviewmethodandvariousartificialintelligencemethodsuchasgeneticalgorithms,neuralnetworks,etc.Butthesemethodshavesomeproblemsintheheightandtheresearchdynamicreal-timeenvironment,theyshouldbefurtherimproved.Thissubjectmainlyresearchsoccerrobotpathplanningproblemfromthestaticenvironment.Thetextmainlyincludesthefollowingcontents:Thefirstchapterintroducestheresearchbackgroundofthesoccerrobot,andonthebasisofitbriefintroductionthesoccerrobotpathplanning.Thesecondchapteranalysistheproblemsuchasthesoccerrobotsystem,thepathplanningstrategyandtheenvironmentalmodelofsoccerrobotindetailed.Thethirdchapteranalysisthetypicalpathplanningalgorithmusedcurrentlysuchastheartificialpotentialfieldmethod,gridmethod,theperpendicularbisectormethodandgeneticalgorithms.Thefourthchapter,basedontheanalysisofthevariousalgorithm,jointhepopulationmigrationinthegeneticalgorithmwhichisbasedonthebasisofformerinthispathplanning.thegeneticalgorithmandartificialpotentialfieldmethodaresimulatedandprogrammedbytheMATLAB.Finally,wesummarizethecontentofthewholetext.Keywords:path-planning;soccerrobot;geneticalgorithm;theartificialpotentialfield;perpendicularbisectormethod目錄摘要 IAbstract II第一章緒言 11.1研究背景 11.1.1機器人足球概述 11.1.2課題國內(nèi)外研究現(xiàn)狀 21.1.3足球機器人比賽的發(fā)展 31.2機器人足球路徑規(guī)劃概述 41.2.1足球機器人路徑規(guī)劃的描述 41.2.2足球機器人路徑規(guī)劃的 41.2.3足球機器人路徑規(guī)劃的特點 41.2.4足球機器人路徑規(guī)劃的分類及現(xiàn)狀 5第二章足球機器人系統(tǒng) 62.1足球機器人系統(tǒng) 62.1.1足球機器人體系結(jié)構(gòu) 62.1.2視覺子系統(tǒng) 62.1.3決策子系統(tǒng) 72.1.4決策子系統(tǒng)模型 72.1.5通訊子系統(tǒng) 92.1.6小車子系統(tǒng) 92.2路徑規(guī)劃 92.2.1路徑規(guī)劃(底層決策) 92.2.2路徑策略 92.2.3最優(yōu)運動規(guī)劃 112.3足球機器人系統(tǒng)環(huán)境模型 122.3.1球場模型 122.3.2機器人小車模型 122.3.3球的運動學(xué)方程 14第三章足球機器人路徑規(guī)劃方法 153.1柵格法 153.1.1柵格法簡介 153.1.2柵格法進行路徑規(guī)劃 163.2人工勢場法 173.2.1人工勢場法簡介 173.3中垂線法 183.4遺傳算法法 193.4.1遺傳算法的簡介 193.4.2遺傳算法的特點 203.4.3遺傳算法的基本原理 213.5對各種方法的綜合評價 28第四章matlab實現(xiàn)人工勢場、遺傳算法的仿真 304.1環(huán)境建模 304.2運動方程的建立 314.3遺傳算法的仿真實現(xiàn) 324.3.1初始種群設(shè)置 324.3.2障礙物的檢測 334.3.3初始參數(shù)設(shè)置 354.3.4適應(yīng)度函數(shù)的選取 364.3.5遺傳操作的過程 394.3.6遺傳算法路徑規(guī)劃仿真與實現(xiàn) 434.4人工勢場法路徑規(guī)劃仿真與實現(xiàn) 46第五章總結(jié) 53參考文獻 54致謝 56第一章緒言1.1研究背景1.1.1機器人足球概述足球機器人屬于第三代智能機器人。機器人足球比賽，是近年來在國際上迅速開展起來的高技術(shù)對抗活動，它是體育與高科技結(jié)合的產(chǎn)物，比賽融入了機器人學(xué)、機電一體化技術(shù)、通訊與計算機技術(shù)、機器人視覺與傳感融合技術(shù)、決策與對策、智能控制等多學(xué)科高新技術(shù)。1992年加拿大哥倫比亞大學(xué)教授AlnaMacwkortnl在一次國際人工智能會議上首次提出機器人足球的思想，旨在推動人工智能學(xué)科的發(fā)展，為智能機器人提出了一個新的具有標志性和挑戰(zhàn)性的課題。同時，機器人足球的倡導(dǎo)者則提出了他們新的夢想：在2050年，一個全自主的類人型機器人足球隊，按照國際足聯(lián)的規(guī)則，戰(zhàn)勝當時的人類足球世界杯冠軍隊。這個夢想被看作是繼1997年IBM公司研制的計算機深藍（DeepBlue）戰(zhàn)勝了國際象棋大師卡斯帕洛夫（Kasparov）之后的人工智能歷史上又一個里程碑項目。目前國際上有組織的機器人足球比賽有兩大系列FIRA和Robocup。FIRA是國際機器人足球協(xié)會聯(lián)合會（FIRA-FederationofInternationalRobotsoccer），簡稱國際機器人足聯(lián)，成立于1997年6月5日，總部設(shè)在韓國大田的韓國科學(xué)（技術(shù)）院（KAIST）。目前已有30余個國家的近百個學(xué)校與科研院所為其成員單位，主要分布在亞洲、澳洲、北美和南美洲等地。FIRA的比賽項目主要有：超微機器人足球比賽Narosot，微型機器人足球比賽Mirosot，仿真機器人足球比賽Simurosot，小型機器人足球比賽Rboosot，自主式機器人足球比賽Kheperasot，類人機器人足球比賽Hurosot和機器人標準動作比賽Benchmark。從1995年至今，F(xiàn)IRA機器人足球比賽己經(jīng)經(jīng)歷了10年的發(fā)展，而且在中國，越來越多的科研院所、高等學(xué)府把FIRA機器人足球研究工作當成是提高領(lǐng)域研究的手段。另一國際組織Robocup（TheRobotworldCupInitiative）是國際人工智能學(xué)會組織的國際機器人足球協(xié)會。成立于1996年，總部設(shè)在日本名古屋，主席是SONY公司計算機科學(xué)研究院的北野宏明教授。每年舉辦一次，吸引了眾多的大學(xué)和科研機構(gòu)的參加。1998年，我國成立了FIRA中國分會，并組織了相應(yīng)的機器人足球隊參加世界杯比賽，取得了較好的成績。我國于2001年在北京舉辦了第六屆機器人足球世界杯比賽?？梢哉f，在國家有關(guān)機構(gòu)和學(xué)術(shù)界的支持和努力下，中國的和器人足球事業(yè)已經(jīng)邁步走向國際舞臺。1.1.2課題國內(nèi)外研究現(xiàn)狀機器人的研究發(fā)展迅速，應(yīng)用的范圍十分廣泛。就目前來看，機器人的發(fā)展仍然處于初級的階段，需要去完成的工作仍然很多，特別是在許多具體的環(huán)境中仍要具體問題具體分析。在機器人中有一類機器人叫做進化機器人，它用進化算法來實現(xiàn)機器人控制、機構(gòu)等方面的優(yōu)化，在路徑規(guī)劃運用中，主要是能夠進化出合適的運動軌跡。D.F10reano和F.Mondada成功地用Khepera機器人實現(xiàn)了一個進化系統(tǒng)。自從John.R.Koza提出遺傳規(guī)劃（GeneticProgramming，GP）以來，遺傳規(guī)劃已經(jīng)在許多方面得到了應(yīng)用，如纏繞的螺旋線的分辨（SpiralClassification），圖像壓縮（Imagecompression），符號回歸（Symbolicregression）等問題。遺傳規(guī)劃在機器人路徑規(guī)劃中的應(yīng)用也是國外許多學(xué)者研究的目標，并且己經(jīng)出現(xiàn)了許多令人興奮的成果。其中，比較早、影響也比較大的是人工螞蟻的問題，這些應(yīng)用遺傳規(guī)劃來規(guī)劃路徑的螞蟻能夠自主地尋找食物并吃掉食物，而且能夠避開障礙。除了人工螞蟻問題外還有割草機問題，在割草機問題中，割草機必須要在執(zhí)行一次程序后割草機能夠到達正方形草坪的每一個部分。其環(huán)境及任務(wù)與人工螞蟻問題的環(huán)境基本相似，但也有不同。其行為包括：MOW，TURNLETF，JUMP；沒有傳感器來感知環(huán)境；所有動作在程序的一次執(zhí)行中完成。另一個問題是函數(shù)的返回值不同，在割草機問題中各數(shù)的返回值不同，造成了實現(xiàn)的復(fù)雜性。在機器人沿墻運動方面也有研究，Dain.R.A己經(jīng)開發(fā)了一種基于測距儀的仿真移動機器人，導(dǎo)航策略在不同的環(huán)境中測試以獲得穩(wěn)定的解決方案，仿真實驗也證明了這一點。國內(nèi)外對自主移動機器人的導(dǎo)航和避障問題己經(jīng)做了大量的研究工作，比如哈爾濱工業(yè)大學(xué)機器人研究所在1996年11月研制成功一個“導(dǎo)游小姐”，該機器人能夠?qū)崿F(xiàn)避障和自主路徑規(guī)劃，識別障礙物的類型，具有一定的語音功能，具有極強的遙控功能。這個機器人能夠根據(jù)傳感器信息自主規(guī)劃路徑。由行走部分、行使控制器、顯示器、語音識別系統(tǒng)和大量的傳感器組成。行走部分采用差速驅(qū)動的方式。既可以在線仿真，也可以顯示機器人行走的路徑和某個時刻導(dǎo)游機器人所在的位置。大面積寬闊地面的清掃工作一直是一項繁重的體力勞動，人工清掃費時、費力且工作效率低，將機器人用于清掃服務(wù)，具有廣闊的應(yīng)用前景。為實現(xiàn)適合我國國情的寬闊地面自動清掃，清華大學(xué)與香港中文大學(xué)合作，聯(lián)合研制開發(fā)出一種全方位移動清掃機器人。國內(nèi)在遺傳規(guī)劃方面研究主要是西安建筑科技大學(xué)，云慶夏教授編寫的《進化算法》比較詳細介紹了遺傳規(guī)劃相關(guān)內(nèi)容。另外，上海交通大學(xué)自動化所利用C++語言也對該算法在機器人沿墻移動問題進行了仿真實驗，通過對移動機器人的行為策略進行符號型編碼，然后對這些策略的組合（GP算法個體）進行自然選擇、優(yōu)勝劣汰，最后進化出滿足任務(wù)需要的優(yōu)良個體。這些個體實際上就是機器人沿墻移動的一系列指令有序組合。最后的仿真結(jié)果說明了應(yīng)用GP算法來演化移動機器人沿墻走行為的有效性。近年來，自主式水下機器人由于其在海底資源探測上的優(yōu)勢而受到各國的關(guān)注，但因為水下環(huán)境十分復(fù)雜導(dǎo)致一般的規(guī)劃方法都難以奏效，而水下環(huán)境的擁擠程度相對較低，機器人工作在同一區(qū)域的可能性較大，這一特征恰好有利于基于事例的規(guī)劃方法的應(yīng)用，因此該方法被廣泛的用于解決水下機器人的路徑規(guī)劃問題。1.1.3足球機器人比賽的發(fā)展從最近幾年的機器人足球賽來看，主要有如下幾個特點：1）發(fā)展迅速，比賽規(guī)模逐年擴大。2004年6月27日至7月3日2）競爭激烈，比賽水平提高很快。由于參賽隊伍多，好多球隊實力很接近，因此競爭非常激烈。每一次世界杯球隊排名都會與上一屆有很大的變化，這表明機器人足球已經(jīng)受到各國的高度重視，每次比賽各隊的水平都有明顯的提高，也會出現(xiàn)一些新穎的軟、硬件設(shè)計和巧妙的戰(zhàn)術(shù)配合。3）研究不斷深入，比賽類型不斷升級。各隊都在不斷探索新方法、新思路，以求進一步提高隊伍的水平，也出現(xiàn)了一些新的足球機器人類型，如1999年增加了SONY公司四足機器狗足球賽，2000年出現(xiàn)了擬人雙足機器人踢球表演等。為了提高機器人足球的水平，世界各國不僅加大了人力、物力和財力上的投入，而且在研究上也不斷深入，所有這些都成為推動足球機器人發(fā)展的重要因素。1.2機器人足球路徑規(guī)劃概述1.2.1足球機器人路徑規(guī)劃的描述機器人的最優(yōu)路徑規(guī)劃問題，就是依據(jù)某個或某些優(yōu)化準則（如工作代價最小、行走路線最短、行走時間最短等），在其工作空間中找到一條從起始狀態(tài)到目標狀態(tài)的能避開障礙物的最優(yōu)路徑。機器人路徑規(guī)劃是智能機器人的一個重要的課題，是機器人智能性的一個重要體現(xiàn)。在靜態(tài)環(huán)境和動態(tài)環(huán)境下進行路徑規(guī)劃與實時避障是解決機器人應(yīng)用的一個非常重要的問題，而動態(tài)不確定環(huán)境下的機器人路徑規(guī)劃則是實際研究與應(yīng)用的一個重點和難點。1.2.2足球機器人路徑規(guī)劃的在足球機器人中，路徑規(guī)劃的目的主要有兩個：一是為了完成某項動作，二是為了避障實現(xiàn)安全的運行。在現(xiàn)在的足球機器人系統(tǒng)中主要還是采用雙輪差驅(qū)動的輪式機器人，這種機器人的運動模型是一種典型的非完整性約束系統(tǒng)，機器人為了完成某項動作，比如射門，就必須沿著一定的路徑運動才能完成規(guī)定動作，這類路徑規(guī)劃可歸結(jié)為由初始勢態(tài)（位置和方向）到目標勢態(tài)（位置和方向）的路徑規(guī)劃，路徑規(guī)劃的好壞直接影響到動作執(zhí)行的速度和準確性。在充滿對抗的機器人足球系統(tǒng)中，機器人之間的碰撞是不可避免的，為了在比賽中取得先機在決策系統(tǒng)中就必須要考慮到避障問題。因此，路徑規(guī)劃在是研究足球機器人系統(tǒng)中的重要的一部分，要想使一個足球機器人系統(tǒng)在比賽中獲得優(yōu)勢必須在決策層中把路徑規(guī)劃問題放在首要問題，不管是在運動過程中還是在射門中，都需要用到路徑規(guī)劃的問題。1.2.3足球機器人路徑規(guī)劃的特點足球機器人系統(tǒng)是一個實時動態(tài)的不確定的復(fù)雜環(huán)境，其路徑規(guī)劃具有如下特點：1）復(fù)雜性：機器人足球系統(tǒng)是一個實時的、動態(tài)的復(fù)雜多機器人系統(tǒng)。在這種動態(tài)時變環(huán)境中，機器人路徑規(guī)劃非常復(fù)雜，且需要很大的計算量。2）隨機性：機器人足球是一個充滿對抗的復(fù)雜環(huán)境，對方機器人的運動是難以預(yù)測的，動態(tài)障礙物的出現(xiàn)也帶有隨機性。機器人足球系統(tǒng)還有噪聲因素：包括感知噪聲和動作實現(xiàn)噪聲。從視覺部分得到的信息必定是有一定延時的。同時，由于電機的物理性質(zhì)，也無法保證小車一定會根據(jù)所得到的命令準確無誤的運動，往往存在很多隨機性和不確定因素。3）多約束：機器人的運動存在幾何約束和物理約束。幾何約束是指機器人的形狀制約，而物理約束是指機器人的速度和加速度。4）多目標：機器人運動過程中路徑性能要求存在多種目標，如路徑最短，時間最優(yōu)，安全性能最好，能源消耗最小。但它們之間往往存在沖突。實現(xiàn)起來比較困難了。1.2.4足球機器人路徑規(guī)劃的分類及現(xiàn)狀人們應(yīng)用人工智能技術(shù)在路徑規(guī)劃領(lǐng)域做了大量研究工作，探索出了很多有效的求解方法。其中一些應(yīng)用范圍很廣，另外一些應(yīng)用范圍則極為有限。它們之間也不是互相排斥的，各有優(yōu)缺點，因而常常結(jié)合起來共同地實現(xiàn)路徑規(guī)劃。路徑規(guī)劃問題已有的研究方法可以分為全局型方法、局部型方法以及混合型方法三種。全局規(guī)劃方法，依照已獲取的環(huán)境信息給機器人規(guī)劃出一條路徑。規(guī)劃路徑的精確程度取決于獲取環(huán)境信息的準確程度。全局方法通?？梢詫ふ易顑?yōu)解，但是需要預(yù)先知道環(huán)境的準確信息，并且計算量很大。局部規(guī)劃方法，側(cè)重于考慮機器人當前的局部環(huán)境信息，讓機器人具有良好的避碰能力。很多機器人導(dǎo)航方法通常是局部的方法，因為它的信息獲取僅僅依靠傳感器系統(tǒng)獲取的信息，并且隨著環(huán)境的變化實時的發(fā)生變化。和全局規(guī)劃方法相比較，局部規(guī)劃方法更具有實時性和實用性。缺陷是僅僅依靠局部信息，有時會產(chǎn)生局部極點，無法保證機器人能順利到達目的地?；旌闲头椒ㄔ噲D結(jié)合全局和局部的優(yōu)點，將全局規(guī)劃的“粗”路徑作為局部規(guī)劃的子目標，從而引導(dǎo)機器人最終找到目標點。從機器人工作環(huán)境的角度區(qū)分規(guī)劃方法，可以分為靜態(tài)確定環(huán)境規(guī)劃方法和動態(tài)時變環(huán)境規(guī)劃方法。目前許多研究工作集中在靜態(tài)環(huán)境下，如裝配機器人；在動態(tài)環(huán)境下的規(guī)劃問題己經(jīng)引起了人們的重視，并且己經(jīng)取得了一些成果，這將是今后的一個發(fā)展方向。從機器人路徑規(guī)劃發(fā)展歷史來分，可分傳統(tǒng)方法和智能方法。傳統(tǒng)路徑規(guī)劃方法主要有自由空間法、圖搜索法、柵格法和人工勢場法。智能方法主要有模糊方法、神經(jīng)網(wǎng)絡(luò)和遺傳算法等。第二章足球機器人系統(tǒng)2.1足球機器人系統(tǒng)2.1.1足球機器人體系結(jié)構(gòu)圖2.1從硬件角度劃分足球機器人系統(tǒng)由以下四個部分組成：①三個機器人小車構(gòu)成的機器人小車子系統(tǒng)；②一個位于球場正上方約2米的攝像機、圖像識別系統(tǒng)組成的視覺子系統(tǒng)；③由一個至少2個頻道的無線電發(fā)射板組成的通訊子系統(tǒng)；④為各個機器人提供各種動作的決策子系統(tǒng)。其相互聯(lián)系如圖2.1所示，決策子系統(tǒng)處理來自視覺子系統(tǒng)的識別場景數(shù)據(jù)，做出決策，通過通訊子系統(tǒng)發(fā)出命令，由機器人小車完成一定的動作。2.1.2視覺子系統(tǒng)由置于球場上方的攝像頭及相關(guān)軟硬件構(gòu)成。主要任務(wù)是以一定周期、快速地采集、處理賽場上的彩色圖像，然后將處理結(jié)果送給決策子系統(tǒng)。圖2.2各子系統(tǒng)之間的關(guān)系2.1.3決策子系統(tǒng)決策子系統(tǒng)在比賽進行過程中擔當“教練”的角色。對于采用共軸平行的兩輪獨立驅(qū)動的移動機器人，決策子系統(tǒng)的輸入信息是視覺系統(tǒng)獲取的環(huán)境信息，包括球的位置，己方和對方機器人的位置及方向等，輸出信息是本方5個機器人的左右輪輪速和擊球控球命令。決策子系統(tǒng)是機器人足球比賽的核心，是人工智能等相關(guān)理論在機器人足球系統(tǒng)中的集中體現(xiàn)。2.1.4決策子系統(tǒng)模型決策子系統(tǒng)處理來自視覺的實時場景辨識數(shù)據(jù)，做出決策、發(fā)出命令，通過無線通訊給機器人小車，決策子系統(tǒng)相當于機器人的“大腦”，視覺子系統(tǒng)相當于機器人的“眼睛”，機器人小車相當于機器人的“手腳”。決策子系統(tǒng)是本論文研究的一個重點，決策子系統(tǒng)主要解決足球機器人多智能體協(xié)作和運動控制的問題。決策子系統(tǒng)的任務(wù)是根據(jù)視覺子系統(tǒng)送到的目標信息，經(jīng)過決策后產(chǎn)生機器人運動控制指令。決策子系統(tǒng)的輸入是目標信息，輸出是機器人運動控制指令，它是一個非結(jié)構(gòu)化的知識型系統(tǒng)。一般認為，決策子系統(tǒng)由決策模型和機器人行為控制兩部分組成。決策模型主要完成攻防態(tài)勢判斷、隊形確定、角色和任務(wù)分配；機器人行為控制則包括動態(tài)避碰和運動控制，如圖2.3所示決策。決策子系統(tǒng)要求具有較高的實時性和靈活性，其靈活性指靈活地實現(xiàn)攻防策略、陣型變化、戰(zhàn)術(shù)配合及足球機器人運動。圖2.3機器人控制決策子系統(tǒng)是一個知識型輸入輸出系統(tǒng)，它是一個軟件，所以決策子系統(tǒng)的結(jié)構(gòu)和機制不是唯一的，但決策子系統(tǒng)應(yīng)該能夠滿足下列要求：1、實時性這個要求與視覺子系統(tǒng)的要求類似，系統(tǒng)的工作頻率確定后，決策子系統(tǒng)的工作頻率與之相同。因此，決策子系統(tǒng)的結(jié)構(gòu)和算法應(yīng)當盡量簡化。2、靈活性足球比賽是一種競爭性、對抗性很強的運動，機器人足球比賽也不例外。比賽場上的形勢瞬息萬變，決策子系統(tǒng)必須能夠準確判斷攻防態(tài)勢，靈活實現(xiàn)比賽陣型變化和戰(zhàn)術(shù)配合，同時機器人的運動必須流暢。如何實現(xiàn)決策子系統(tǒng)要求的實時性和靈活性，也就是說如何更好的規(guī)劃足球機器人的路徑，使其更好的達到時間最優(yōu)和路徑最優(yōu)，是本子系統(tǒng)研究重點解決的問題。本節(jié)根據(jù)robocup系統(tǒng)多智能體協(xié)作的特點，提出適用于機器人足球比賽的底層決策及其最優(yōu)路徑規(guī)劃的思路。2.1.5通訊子系統(tǒng)在機器人足球比賽中，計算機根據(jù)視覺系統(tǒng)采集的信息做出辨識和決策，通過無線通訊裝置指揮場上機器人完成相應(yīng)的戰(zhàn)術(shù)動作。因此無線通訊系統(tǒng)就成為在機器人閉環(huán)控制系統(tǒng)成為決策子系統(tǒng)和機器人小車子系統(tǒng)的橋梁，其主要任務(wù)就是要將計算機的命令準確無誤的傳送給機器人，使機器人能準確接受和完成命令。2.1.6小車子系統(tǒng)在整個足球機器人系統(tǒng)這個閉環(huán)控制系統(tǒng)中，機器人小車充當執(zhí)行機構(gòu)的角色。所以，小車性能在賽場上表現(xiàn)的好壞直接反映了整個足球機器人系統(tǒng)的優(yōu)劣。小車子系統(tǒng)相當于我們的執(zhí)行機構(gòu)，所有的算法和要完成的動作都是靠它來執(zhí)行，進而小車須在實際操作中完善和改進，使其能夠完成其他子系統(tǒng)對它的控制。2.2路徑規(guī)劃2.2.1路徑規(guī)劃（底層決策）路徑規(guī)劃問題就是找到一條從當前點到目標點的無碰且時間最優(yōu)的路徑。由于足球機器人競賽具有高度對抗、高速運動、動態(tài)環(huán)境和實時決策等特點，所以，路徑規(guī)劃的成功與否直接關(guān)系到比賽結(jié)果的成敗。因此，路徑規(guī)劃任務(wù)在足球機器人系統(tǒng)中占有很重要的地位。與一般的運動規(guī)劃問題相比，足球機器人規(guī)劃問題具有一個明顯的特點；碰撞問題涉及規(guī)劃的策略、路徑和軌跡三個層次，貫穿規(guī)劃的設(shè)計、執(zhí)行和監(jiān)督過程，任務(wù)、路徑和軌跡都成為受事件驅(qū)動的短時規(guī)劃行為。這樣，原來層次化的規(guī)劃模型就難以奏效了。足球機器人規(guī)劃問題的復(fù)雜性還在于：多個智能體的高速運動、運動速度與方向的復(fù)雜變化、復(fù)雜的碰撞行為和高度實時性要求。很多傳統(tǒng)的規(guī)劃方法是針對一個靜態(tài)的封閉環(huán)境設(shè)計的，并且具有較高的時間復(fù)雜度。如采用位姿空間描述和圖搜索的求解方法等，很難滿足實時性能的要求。探索適合于足球機器人在動態(tài)環(huán)境下的多智能體規(guī)劃方法，已經(jīng)引起研究人員的關(guān)注。2.2.2路徑策略路徑規(guī)劃的策略具體可以分為：全局路徑規(guī)劃的方法和局部路徑規(guī)劃，全局路徑規(guī)劃的方法有：拓撲法、可視圖法和柵格法等。拓撲法是將規(guī)劃空間分割成具有拓撲特征子空間，并建立拓撲網(wǎng)絡(luò)，在拓撲網(wǎng)絡(luò)上尋找起始點到目標點的拓撲路徑,最終由拓撲路徑求出幾何路徑。其缺點是建立拓撲網(wǎng)絡(luò)的過程相當復(fù)雜，特別在增加障礙物時如何有效地修正已經(jīng)存在的拓撲網(wǎng)絡(luò)及如何提高圖形速度是有待解決的問題?？梢晥D法視機器人為一點，將機器人、目標點和多邊形障礙物的各頂點進行組合連接，要求機器人和障礙物各頂點之間、目標點和障礙物各頂點之間以及各障礙物頂點與頂點之間的連線，均不能穿越障礙物，即直線是可視的。搜索最優(yōu)路徑的問題就轉(zhuǎn)化為從起始點到目標點經(jīng)過這些可視直線的最短距離問題。運用優(yōu)化算法，可刪除一些不必要的連線以簡化視圖，縮短搜索時間。該法能夠求得最短路徑，但假設(shè)機器人的尺寸大小忽略不計，使得機器人通過障礙物定點時離障礙物太近甚至接觸并且搜索時間長。柵格法是由W.E.Howde在1968年提出的。柵格法將機器人工作環(huán)境分解成一系列具有二值信息的網(wǎng)格單元，工作空間中障礙物的位置和大小一致，并且在機器人運動過程中，障礙物的位置和大小不發(fā)生變化。用尺寸相同的柵格對機器人的二維工作空間進行劃分，柵格的大小以機器人自身的尺寸為準。若某個柵格范圍內(nèi)不含任何障礙物，則稱此柵格為自由柵格；反之，稱為障礙柵格。自由空間和障礙物均可表示為柵格塊的集成。柵格的標識方法有兩種：直角坐標法和序號法多采用四叉樹或八叉樹表示工作環(huán)境，并通過優(yōu)化算法完成路徑搜索。該方法以柵格為單位記錄環(huán)境信息，柵格粒度越小，障礙物的表示會越精確，但同時會占用大量的存儲空間，算法的搜索范圍將按指數(shù)增加。柵格的粒度太大，規(guī)劃的路徑會很不精確。所以柵格粒度的大小的確定，是柵格法的主要問題。局部路徑規(guī)劃的主要方法有：人工勢場法、遺傳算法和模糊邏輯算法。人工勢場法是由Khatib提出的一種虛擬力法。人工勢場法是傳統(tǒng)算法中較成熟且高產(chǎn)的規(guī)劃方法。這種方法的基本思想是把機器人在環(huán)境中的運動視為一種在抽象的人造受力場中的運動，即在環(huán)境中建立人工勢場的負梯度方向指向系統(tǒng)的運動控制方向。目標點對移動機器人產(chǎn)生引力，障礙物對機器人產(chǎn)生斥力，其結(jié)果是使機器人沿“勢峰”間的“勢谷”前進。引力和斥力的合力作為機器人的加速力來控制機器人的運動方向和計算機器人的位置。這類方法突出的優(yōu)點是系統(tǒng)的路徑生成與控制直接與環(huán)境實現(xiàn)了閉環(huán)，從而大大加強了系統(tǒng)的適應(yīng)性與避障性能。但是人工勢場法也存在幾個主要的缺陷：（1）陷阱區(qū)域。（2）在相近的障礙物之間不能發(fā)現(xiàn)路徑。（3）在障礙物前振蕩。（4）在狹窄通道中擺動。遺傳算法（GA）是一種基于自然選擇和自然遺傳的全局優(yōu)化算法，他采用從自然界選擇、遺傳操作中抽象出來的幾個算子，對參數(shù)編碼的字符串進行遺傳操作，每一字符串對應(yīng)于一個可行解，這種遺傳操作是對多個可行解組成的群體進行的，故在進化過程中可以并行地對解空間的不同區(qū)域進行搜索，可使搜索趨于全局最優(yōu)解而不會陷于局部極小解。正是由于這種內(nèi)在的優(yōu)良特性，GA可廣泛應(yīng)用于各種優(yōu)化問題。遺傳算法的操作算法有：（1）復(fù)制或選擇算子。（2）交叉算子。（3）變異算子?？梢奊A的主要優(yōu)點是：采用群體方式對目標函數(shù)空間進行多線索的并行搜索，可同時對多個可行解進行檢查，交叉算子、變異算子可以使可行解之間交換信息從而產(chǎn)生新的可行解，不會陷入局部極小點；GA只需要可行解目標函數(shù)的值，而不需要其他信息,對目標函數(shù)的連續(xù)性、可微性沒有要求，因此使用方便；解的選擇和產(chǎn)生采用概率方式，因此具有較強的適應(yīng)能力和魯棒性。他通過對隨機產(chǎn)生的多條路徑進行選擇、交叉、變異、優(yōu)化組合，利用遺傳算法的優(yōu)勝劣汰、適者生存的自然選擇原理，選擇出適應(yīng)值達到一定標準的一條優(yōu)化路徑。利用遺傳算法解決機器人動態(tài)環(huán)境中路徑規(guī)劃問題，可以避免困難的理論推導(dǎo)，直接獲得問題的最優(yōu)解。但遺傳算法運算速度不快，進化眾多的規(guī)劃要占用較大的存儲空間和運算時間?；趯崟r傳感信息的模糊邏輯算法參考人的駕駛經(jīng)驗，通過查表得到規(guī)劃信息,實現(xiàn)局部路徑規(guī)劃，計算量不大，易做到邊規(guī)劃邊跟蹤,能滿足實時性要求。該方法克服了勢場法易產(chǎn)生的局部極小問題，適用于時變未知環(huán)境下的路徑規(guī)劃，實時性較好。2.2.3最優(yōu)運動規(guī)劃在保證運動規(guī)劃算法具有足夠的安全性（避免碰撞）的前提下，尋找一條長度最短的路徑，或者時間最短的運動軌跡，是運動規(guī)劃算法追求的目標。在最優(yōu)規(guī)劃的理論研究方面取得的重要研究成果包括：Fillipoy的存在性理論，Pontryagin最大值原理(PMP)Boltianskii的充分優(yōu)化條件。其中PMP給出了最優(yōu)路徑的必要條件，因此是衡量最優(yōu)路徑的重要指標。分布式的思想同樣也被用來研究近似優(yōu)化的解法。Shiller等人提出了一種局部時間最優(yōu)的軌跡規(guī)劃方法。這種方法分為兩個步驟：首先規(guī)劃出一條路徑，然后將沿路徑的最優(yōu)運動時間作為價值函數(shù)，進行局部最優(yōu)化?？紤]到精確求解的巨大困難，研究人員在許多實際問題中提出了近似的算法，這些算法的基本思想是通過搜索預(yù)先定義在工作空間、姿態(tài)空間或者狀態(tài)空間的柵格，來尋找一條近似最優(yōu)的路徑。2.3足球機器人系統(tǒng)環(huán)境模型2.3.1球場模型在足球機器人系統(tǒng)中，其運行環(huán)境是部分己知、部分未知，含有靜態(tài)和動態(tài)障礙物的環(huán)境，且是個時刻變化的競爭性動態(tài)環(huán)境。圖2.4球場模型如上圖2.4所示，其中足球機器人球場邊界是已知的靜態(tài)障礙物，另外球場大小禁區(qū)有時也屬于己知的靜態(tài)障礙物，比賽規(guī)則中對大小禁區(qū)內(nèi)雙方機器人的數(shù)量均有嚴格的限制，所以決策系統(tǒng)應(yīng)該機器人小車模型根據(jù)場上形勢，規(guī)定禁區(qū)附近每個機器人是否可以進入禁區(qū)。機器人和小球都屬于不確定性障礙物，它們的形狀確定，但位置不確定，而且可能是靜態(tài)的或者是動態(tài)的，對這些障礙物的避障是研究的重點和難點。2.3.2機器人小車模型(1)機器人小車動力模型目前，足球機器人普遍采用的是兩輪差動式移動機器人，其兩個輪子共軸并且獨立驅(qū)動。設(shè)機器人目前的位姿速度為，和分別為左右輪的速度。機器人的位姿(位置、方向)與速度(線速度、角速度)之間存在如下關(guān)系：

由機器人小車的運動學(xué)模型可以看出，其狀態(tài)空間有三個分量：，和。，而控制分量卻只有兩個：線速度和角速度，也可以是左右輪的速度和。因此，這是一個非完整性約束問題，必須增加一個約束方程：(2.4)根據(jù)機器人小車純滾動、無側(cè)滑的假定，在運動過程中上面的等式始終滿足，其物理意義是，小車在輪軸方向上的速度始終為零。這個等式意味著，小車運動的瞬時速度的方向始終與小車的朝向相同，小車方向的改變只能通過兩個輪子的差速來實現(xiàn)。足球機器人的這種典型的非完整性約束的運動模型，我們在運動規(guī)劃時必須加以考慮，這樣規(guī)劃出來的路徑才能被足球機器人加以跟蹤和執(zhí)行。(2)機器人小車的運動學(xué)模型由上面的機器人小車動學(xué)力模型可知，機器人小車可作直線或曲線運動，根據(jù)機器人當前位姿和左右輪的速度可計算其曲率半徑，角速度，線速度，以及下個周期的位姿，其運動學(xué)模型由式（2.5）、（2.6）確定。(2.5)(2.6)其中，為機器人小車的邊長，、分別為較大的輪速和較小的輪速，、、。分別機器人當前的坐標和方向角。2.3.3球的運動學(xué)方程對球而言，它只能作直線運動，在沒有外力的作用下，它的運動是勻減速直線運動。如下式表示：（2.7）其中，、、表示t時刻球的運動狀態(tài)，，，表示t-1時刻球的運動狀態(tài)，a表示摩擦力產(chǎn)生的加速度，表示時間間隔，表示t-1時刻球的運動方向。第三章足球機器人路徑規(guī)劃方法路徑規(guī)劃是實現(xiàn)機器人智能的一個關(guān)鍵技術(shù)。它的任務(wù)是在具有障礙物的環(huán)境中，按照一定的評價標準，尋找一條從起始狀態(tài)（包括位置及姿態(tài)）到達目標狀態(tài)（包括位置及姿態(tài)）的無碰路徑。在足球機器人中，路徑規(guī)劃的目的主要是為了在充滿對抗的賽場上規(guī)劃出一條滿足某項評價指標的無碰路徑。路徑規(guī)劃主要應(yīng)用于機器人底層策略中，作為足球機器人基本動作實現(xiàn)的基礎(chǔ)，他的優(yōu)劣將直接影響動作的實時性和準確性。因此，每個足球機器人研究人員都把他作為一個研究重點，探索出了很多有效的求解方法。其中一些應(yīng)用范圍很廣，另外一些應(yīng)用范圍則極為有限。它們之間也不是互相排斥的，各有優(yōu)缺點，因而常常結(jié)合起來共同地實現(xiàn)路徑規(guī)劃。下面對足球機器人的一些傳統(tǒng)路徑規(guī)劃方法作個介紹。3.1柵格法3.1.1柵格法簡介柵格法（Grid）是在靜態(tài)路徑規(guī)劃中避障過程搜索最優(yōu)路徑的常見方法。該方法將機器人的工作空間分解為多個簡單的區(qū)域，一般稱為柵格。每個柵格的面積比一個機器人所占的面積略大。若某一個柵格范圍內(nèi)不包含任何障礙物，則稱此柵格為自由柵格；如某一個柵格內(nèi)含有障礙物，則稱為障礙柵格。由這些柵格構(gòu)成了一個連通圖，在這個連通圖上搜索一條從起始柵格到目標柵格的路徑，該路徑均由自由柵格構(gòu)成，用柵格的序號來表示。最后把柵格序號轉(zhuǎn)換成機器人空間實際坐標，令機器人按此路徑運動，達到無碰撞的路徑。目前有許多學(xué)者用柵格法對環(huán)境空間建模來解決問題并取得了較好的效果J.Borensteinf曾采用Grids表示環(huán)境，用勢場法決策出VFF算法和VFH算法，并由此將柵格法的良好性能向人們展現(xiàn)出來。任世軍和洪炳熔等人在機器人的位姿空間中采用基于柵格擴展的策略解決了機器人路徑規(guī)劃問題。薄喜柱等人用柵格法對機器人空間建模，參照人類在人群中行走的經(jīng)驗對柵格地圖進行進一步規(guī)劃，成功的實現(xiàn)了足球機器人路徑規(guī)劃問題。柵格法的運用方便，易于規(guī)劃出正確的路徑，因而對它的研究比較多。在柵格法表示的機器人路徑規(guī)劃問題研究中，定義出路徑記憶量、路徑方位的重要性等概念，通過可行路徑中兩兩結(jié)點之間關(guān)聯(lián)程度的改變，按照比例選擇概率確定下一結(jié)點，由此得到一條新的可行路徑。路徑和關(guān)聯(lián)程度之間形成一種正反饋機制，二者相互激勵，從而簡化了路徑搜索方法，提高了路徑搜索的效率。用柵格法建模進行機器人路徑規(guī)劃是研究比較多的一種方法。該方法將機器人的工作空間解耦為多個簡單的區(qū)域，一般稱為柵格，由這些柵格構(gòu)成了一個連通圖，在這個連通圖上搜索一條從起始柵格到目標柵格的路徑。哈爾濱工業(yè)大學(xué)用柵格法對機器人空間建模，參照人類在人群中行走的經(jīng)驗對柵格地圖進行進一步規(guī)劃，成功的實現(xiàn)了足球機器人路徑規(guī)劃問題。3.1.2柵格法進行路徑規(guī)劃使用柵格法進行路徑規(guī)劃的步驟有3個步驟：(1)建立模型區(qū)域用柵格法建模進行機器人路徑規(guī)劃是研究比較多的一種方法。該方法將機器人的工作空間解耦為多個簡單的區(qū)域，一般稱為柵格，由這些柵格構(gòu)成了一個連通圖，在這個連通圖上搜索一條從起始柵格到目標柵格的路徑。哈爾濱工業(yè)大學(xué)用柵格法對機器人空間建模，參照人類在人群中行走的經(jīng)驗對柵格地圖進行進一步規(guī)劃，成功的實現(xiàn)了足球機器人路徑規(guī)劃問題。根據(jù)機器人和目標點的位置劃定規(guī)劃區(qū)域，然后將該區(qū)域用網(wǎng)格表示，每個網(wǎng)格就是一個柵格。柵格的大小是一個關(guān)鍵因素：柵格選得小，環(huán)境分辨率較大，但抗干擾能力弱，環(huán)境信息存儲量大，決策速度慢；柵格選得大，抗干擾能力強，環(huán)境信息存儲量小，決策速度快，但分辨率下降，在密集障礙物環(huán)境下，發(fā)現(xiàn)路徑的能力減弱。一般柵格大小的選取和機器人的大小相關(guān)。最后對劃分好的柵格編序號，柵格序號將代表柵格所在的位置；并給每個柵格賦以一定的初值，柵格的值將代表有障礙物的可能性。(2)生成障礙物地圖區(qū)域建好以后，開始檢測障礙物的位置，并根據(jù)障礙物位置找到對應(yīng)柵格地圖中的序號值，并對對應(yīng)的柵格值進行修改。定義不包含障礙物的柵格為自由柵格，包含障礙物的柵格為障礙物柵格。(3)在區(qū)域里搜索無障礙物的柵格足球機器人所走的路徑就是在區(qū)域里尋找一條無碰撞的路徑，也就是區(qū)域里聯(lián)系自由柵格組成的一條路徑，搜索的方法很多如基于勢場法的柵格路徑搜索方法，用遺傳法進行的路徑規(guī)劃方法，以及基于動態(tài)二叉的A*算法等。3.2人工勢場法3.2.1人工勢場法簡介人工勢場法是國內(nèi)外研究者研究與應(yīng)用較多的方法。人工勢場實際是對機器人運行環(huán)境的一種抽象描述。勢場中包括斥力場和引力場，不希望機器人小車進入的區(qū)域和障礙物是斥力場，子目標及其建議機器人進入的區(qū)域為引力場。引力場和斥力場的周圍有一定的抽象勢能，它的負梯度方向表達了機器人小車系統(tǒng)所受抽象力的方向，正是這種抽象力，促使機器人小車以平滑的曲線朝向目標前進。人工勢場法在避障和軌跡規(guī)劃的同時也考慮了機器人小車的運動性能指標。該方法計算方法簡單，計算量小，且在避障和軌跡規(guī)劃的同時也考慮了機器人的運動性能，因此該方法倍受人們歡迎。傳統(tǒng)的人工勢場該方法是由khatib于1997年首次提出的一種虛擬力法，其主要思想是：構(gòu)造目標位姿引力場和障礙物斥力場共同作用的人工勢場，搜索勢力函數(shù)的下降方向來尋找無碰撞的路徑。首先，在機器人的運動空間中創(chuàng)建一個勢場。該勢場由兩部分組成：一個是引力場，方向指向目標點球；另一個是斥力場，方向指向遠離障礙物方向。整個勢場U是其引力部分和斥力部分的疊加。機器人就是沿著合成的勢場力方向運動，繞開障礙物，向目標點運動。如圖3.1所示圖3.1空間勢場模型在足球機器人系統(tǒng)中，將整個比賽場地虛擬成一個有力存在的場地，把力分為引力和斥力，目標點對移動機器人產(chǎn)生引力，障礙物對機器人產(chǎn)生斥力，其結(jié)果是使機器人沿“勢峰”間的“勢谷”前進。引力和斥力的合力作為機器人的加速力來控制機器人的運動方向和計算機器人的位置。根據(jù)比賽的進行，場上隊員會發(fā)生變化，因而整個力場中各部分的受力情況也會發(fā)生變化，因此決策系統(tǒng)就可以根據(jù)場上的這種變化去實時的控制足球機器人的運動情況。確定引力勢場和斥力場函數(shù)如下：引力場：(3.1)這里定義為引力場系數(shù)，和分別代表目標點和機器人的位置，m=1或2。對于m=1，引力場呈現(xiàn)圓錐狀，近似重力場，除在目標點外，其他點的吸引力為定值，為恒定的。對m=2，吸引力場呈現(xiàn)拋物線狀。則斥力場：(3.2)當機器人接近目標點時，引力勢場近似為零。此時，吸引力為零。斥力場函數(shù)為(3.3)為一正的比例因子，表示障礙物和目標點的最短距離，為影響障礙物的設(shè)定的一個正比例數(shù)，的選擇影小車的避障情況，合理的選擇有利與機器人走出合適的路徑規(guī)劃，一般選取<min(d1,d2)其中d1是各障礙物間相互距離中最小距離的一半，d2是目標點到各障礙物距離的最小者。相應(yīng)的斥力為(3.4)則，作用在機器人上的合力為引力和斥力的合理F=+(3.5)機器人的最后作用力為F，通過F來控制機器人小車的運動路線，避障情況，還有射門情況等，通過調(diào)節(jié)，的值進而調(diào)節(jié)機器人的運動。3.3中垂線法中垂線法是較早在控制中大量使用的路徑規(guī)劃算法，如圖3.5所示，分別作目標點與期望方向上一點的連BT，目標點與機器人小車的連線，再作目標點和機器人之間線段的中垂線交于BT于A1，使小車向該點運動，在下一周期，作一條新的中垂線，交BT于新的一點A2，使小車向A2運動，依此類推，最終小車將趨向目標點，同時保證其姿態(tài)為期望的方向。圖中點劃線表示機器人經(jīng)過的路徑。圖3.5中垂線模型這種方法的特點是算法簡單，而且算法可以保證機器人到達目標點時滿足位置和方向的要求。但是這種方法使用的范圍是有限的。當小車距位于球和對方球門之間的區(qū)域時，不能直接用中垂線法，而需要決策部分的相應(yīng)算法來實現(xiàn)控制小車首先繞到球的另一面。3.4遺傳算法法3.4.1遺傳算法的簡介遺傳算法(GeneticAlgorithm)是一種人工智能方法，它基于達爾文的生物進化論的適者生存原理，是1975年左右由美國Michigan大學(xué)的JohnH.Holland教授研究出的，遺傳算法模擬了生物的遺傳、進化原理，并引用了隨機統(tǒng)計理論而形成，在求解過程中，算法從一個初始變量群體開始，逐代尋找問題的最優(yōu)解，直至滿足收斂判據(jù)或預(yù)先設(shè)定的迭代次數(shù)為止，屬于迭代式算法。遺傳算法（GA）是一種基于自然選擇和自然遺傳的優(yōu)化算法，它采用從自然界選擇、遺傳操作中抽象出來的幾個算子，對參數(shù)編碼的字符串進行遺傳操作，每一字符串對應(yīng)于一個可行解，這種遺傳操作是對多個可行解組成的群體進行的，故在進化過程中可以并行地對解空間的不同區(qū)域進行搜索，可使搜索趨于全局最優(yōu)解而不會陷于局部極小解。正是由于這種內(nèi)在的優(yōu)良特性，GA可廣泛應(yīng)用于各種優(yōu)化問題。生物進化過程本質(zhì)上就是生物群在器生存環(huán)境約束下通過個體的競爭（competition）、選擇（selection）、雜交（crossover）、變異（mutation）等方式所進行的“優(yōu)勝劣汰”的一種自然有花過程。遺傳的基本思想正式體現(xiàn)了這一過程，隨記生產(chǎn)初始種群，將其視為附帶群體開始進行搜索，群體中的每個個體，即問題的一個解。算法通過個體的“適應(yīng)值”來作為父代中個體適應(yīng)環(huán)境的能力度量，進過選擇雜交和變異產(chǎn)生新的子代染色體重新選擇，如此反復(fù)金環(huán)迭代，使個體的適應(yīng)能力不斷提高并收斂與最好的個體，該個體就是問題的最優(yōu)解。遺傳算法對解決復(fù)雜系統(tǒng)優(yōu)化問題，特別是對組合優(yōu)化問題的求解有著良好的能力。近年來越來越多的中外學(xué)者致力于遺傳算法的研究。遺傳算法已將在旅行商問題的求解、生產(chǎn)調(diào)度、圖形劃分、函數(shù)優(yōu)化圖像處理、機器學(xué)習(xí)、自動控制、人工生命等總舵領(lǐng)域中得到了成功的應(yīng)用，并取得良好的成果。3.4.2遺傳算法的特點傳統(tǒng)的搜索方法重要分為三類：=1\*GB3①基于微分的方法：包括直接法和間接法。這類方法在求解問題是，要求倒數(shù)純在而且容易得到。=2\*GB3②枚舉方法：包括動態(tài)規(guī)劃法、隱枚舉法和完全枚舉法。該方法往往效率不高。=3\*GB3③啟發(fā)式隨機搜索方法：包括模擬退火和傳統(tǒng)方法相比，遺傳算法具有以下的優(yōu)勢。遺傳算法處理的對象是參數(shù)集的代碼，而不是參數(shù)本身，所以遺傳算法是一種所方法，與具體問題領(lǐng)域無關(guān)。此編碼操作使得遺傳算法可直接對結(jié)構(gòu)對象進行操作，所謂節(jié)后對象泛指集合，序列、矩陣、樹、圖、鏈、表等各種一維或二維甚至多維結(jié)構(gòu)形式的對象。這一特點使得遺傳算法具有廣泛的應(yīng)用領(lǐng)域。遺傳算法是非單點搜索算法，具有全局搜索能力。它的優(yōu)化過程是從點集開始對搜索空間中的多個解進行適應(yīng)值評估和染色體進化，這種機制使得遺傳算法易于并行話且搜索不易陷入局部極小點。特別是當算法中有保證全體多樣性的措施時，可以有效保持搜索空間的多樣性并使其具有較強的魯棒性。遺傳算法的搜索過程使用適應(yīng)度函數(shù)（目標函數(shù)）判定解的優(yōu)劣。適應(yīng)值函數(shù)不受可導(dǎo)，可微等傳統(tǒng)方法思路的限制，而且其定義域可以任意設(shè)定，因此算法過程簡單，易于實時。上述這些優(yōu)勢可以看出，遺傳算法有許多獨特的優(yōu)點。(1)全局性遺傳算法在搜索過程中不易陷入局部極值點，即使在非連續(xù)、多峰以及噪聲的情況下，也能以很大的概率收斂到最優(yōu)解或滿意解，具有驚人的容噪能力等。(2)并行性和高行型遺傳算法具有大范圍全局搜索的特點，與問題無關(guān)，潛入問題的前期工作量少，本身具有并行性，很適用于并行計算機，因而具有很高的執(zhí)行效率。(3)魯棒性魯棒性強意味著遺傳算法的搜索以全體為基本單元，解的節(jié)后隨時間增加而趨于穩(wěn)定，不受初始選擇的影響，不因?qū)嵗牟煌懽儯煌瑫r也疑問者，對一個相同問題，遺傳算法在不同的多此運行中得到的節(jié)后是相似的，在解的質(zhì)量上沒有很大的差異。遺傳算法的魯棒性已被許許多多的數(shù)值試驗所證實。(4)普適性和易擴性遺傳算法是一種弱方法，它采用自然進化機制來表達一類復(fù)雜現(xiàn)象，對函數(shù)的形態(tài)無要求，可解決多種優(yōu)化搜索問題。針對不同的實例，只需適當調(diào)整算子參數(shù)等，做很小的修改即可適應(yīng)新的問題，程序能夠通用，然而線性的大多數(shù)優(yōu)化方法都做不到折點。(5)簡明性遺傳算法的基本思想簡單明了，實現(xiàn)起來通俗易懂。3.4.3遺傳算法的基本原理1.遺傳算法的基本術(shù)語染色體：遺傳物質(zhì)的主要載體，指多個遺傳因子的集合。個體：指染色體呆有特征的實體稱個體。種群：染色體帶有特征個體的集合稱為群體，該集合內(nèi)的個體數(shù)稱為群體的大小。編碼：從表現(xiàn)型到遺傳子型的映射稱為編碼。適應(yīng)度：各個個體對各自適應(yīng)環(huán)境的程度成為適應(yīng)度。交叉：把兩個染色體換組的操作稱為交叉，又稱為重組。變異：讓遺傳因子以一定的概率變化的操作稱為變異。解碼：讓遺傳子型到表現(xiàn)型的映射稱為解碼。2.遺傳算法的基本原理與流程在遺傳算法中，首先通過隨機方式產(chǎn)生若干個所求解的問題的數(shù)字編碼(即染色體)來形成初始群體（即種群），以此為進化起點的第一代群體，并計算每個編碼的個體適應(yīng)值來對每個個體進行數(shù)值評價，這里的適應(yīng)度值體現(xiàn)并反應(yīng)了木匾函數(shù)的巡游信息。接下來與自然界一樣，從群體中隨機挑選若干個體作為繁殖過程的樣本集合，選擇機制應(yīng)保證適應(yīng)度值較高的個體能保留較多的樣本，而適應(yīng)度值較低的個體則保留較少的樣本或被淘汰。在繁殖過程中，利用交叉和變異兩種算子，以一定的交叉概率和變異概率對挑選后的樣本進行交換，從而給出新的個體。最后通過新老個體替換產(chǎn)生下一代群體。算法不斷重復(fù)進行上述評價、選擇、繁殖和替換過程，直到結(jié)束條件得到滿足為止。通常進化過程的最后一代群體中適應(yīng)度最高的個體，就是利用遺傳算法求解最優(yōu)化為題的最終結(jié)果。圖3.6遺傳算法的流程3.用遺傳算法進行路徑規(guī)劃①染色體表示用十進制柵格序號表示路徑節(jié)點，用柵格序列表示一條染色體。由于我們無法確定究竟要經(jīng)過多少個柵格，所以我們這里的染色體用不定長染色體表示。②初始群體生成初始種群為隨機生成的從出發(fā)點到目標點的任意一條可行路徑集合。具體產(chǎn)生的方法與柵格法搜索最優(yōu)路徑方法類似。③適應(yīng)值計算式中，Num為該個體所通過的柵格總數(shù);D為該個體中相鄰序號間直線距離之和。④遺傳操作選擇操作：用一定的算法從當前種群中選擇同樣數(shù)量的新一代群體。首先計算每個個體的適應(yīng)值函數(shù)，然后用賭輪選擇方法或者其它方法選出新的種群，通常在選擇時要把上一代的最優(yōu)個體強制保留下來。交叉操作：通常有單點交叉、多點交叉、均勻交叉等幾種方法。隨機選擇兩個個體，按照一定的交叉概率選擇交叉點進行交叉，用交叉后的子代個體代替原種群中的父代個體，產(chǎn)生新的種群。前面提到這里的染色體是長度不相等個體，所以交叉點應(yīng)該分別在要交叉的兩個個體中進行選擇。變異操作：根據(jù)路徑規(guī)劃的特點，這里的變異操作有多種設(shè)計方式，可以從個體中以一定概率選擇一個起點和終點之外序號作為變異點，刪除該點，或者用另一個隨機產(chǎn)生的序號代替它，或者在個體中隨機選擇一個序號在變異處插入。在機器人的路徑規(guī)劃中，還需要增加一些特殊的算子，以保證所得的路徑能夠避開障礙物，并達到最短的要求，常見的有插入和刪除算子。插入算子：前面由于交叉和變異操作可能產(chǎn)生不連續(xù)路徑的情況，引入插入操作的目的就是為了把間斷路徑用自由柵格彌補，使之成為連續(xù)路徑。具體方法是將出現(xiàn)斷點處的兩個路徑點分別設(shè)為起點和終點，然后搜索著兩點間的可行路徑，直到所有路徑位連續(xù)路徑為止。刪除算子：插入自由柵格的操作可能會使路徑中出現(xiàn)重復(fù)節(jié)點，刪除操作的作用就是將個體中兩相同序號之間的冗余序號，連同兩相同序號中的一個一并舍去，以簡化路徑。4.種群的初始化設(shè)定種群的初始化過程有很多種。在研究遺傳算法時，常常隨機產(chǎn)生初始群體，這樣做的好處是產(chǎn)生方式不依賴于問題，也就是對于任何問題，我們都可以采用這種方式來生成初始群體，因此從隨機初始群體出發(fā)能更清楚地考察算法的行為和性能。當然這也存在一定的問題，例如對于一個有約束的非線性規(guī)劃問題，隨機初始群體可能存在著不滿足約束的不可行解，雖然對于一個好的算法來講這并不會影響到最后的優(yōu)化結(jié)果，算法最終得到的最優(yōu)個體中關(guān)鍵的特性是算法的搜索和重組機制產(chǎn)生的，而不是由初始化過程產(chǎn)生的。但是，這還是可能對優(yōu)化的速度產(chǎn)生一定的影響。如果初始群體都是可行解，我們就有可能加快收斂速度。在實際應(yīng)用中，可以采用更有效的初始化方法來加快搜索，比如用貪婪算法等啟發(fā)式算法的輸出結(jié)果、利用人的直觀解答和加權(quán)隨機初始化過程等。5.遺傳操作算子1）選擇運算選擇是從群體中挑選優(yōu)良個體并淘汰劣質(zhì)個體的操作過程。它建立在適應(yīng)度評估的基礎(chǔ)上，個體適應(yīng)度越大，被選擇中的可能性就越大，它的子代保留到配對庫（matingpool）中的個體就越多。常用的選擇方法有：輪盤賭方法（roulettewheelmodel）輪盤度方法是目前遺傳算法中最基本也是最常用的選擇方法。設(shè)群體的大小為，個體的適應(yīng)度，則個體的選擇概率為則累計概率為然后，根據(jù)選擇概率{，=1,2,…,N}把一個圓盤分成N份，其中第扇形的中心角為2π*。在進行選擇時，可以假想轉(zhuǎn)動一下圓盤，若某參照點落入到第個扇形內(nèi)，則選擇個體。如下圖所示圖3.7概率分配輪盤所占的面積越大，被選中的概率也越大。表3.1個體1234567891011適應(yīng)度值2.01.21.00.20.1選擇概率90.070.060.030.020.0累計概率0.180.340.490.620.730.820.890.950.981.001.00排序選擇法排序選擇法以標準化幾何分布規(guī)律隨機對種群中染色體進行選擇，以最佳染色體的選擇概率作為基本參數(shù)，按染色體的排列序號確定其選擇概率。排序法的最大優(yōu)點是：排序法忽略實際染色體的適應(yīng)度值，用染色體的順序來換算出相應(yīng)的生存概率，換算原則為大適應(yīng)度值對高選擇概率，小適應(yīng)度值對地選擇概率。這樣既保證大適應(yīng)度值染色體獲得高選擇概率，同時又阻止某些超級染色體過快地控制遺傳過程。在該遺傳過程中，首先需要根據(jù)最佳染色體選擇概率計算標準分布值，如下(3.6)然后根據(jù)上式計算染色體選擇概率，k=1，2，3,…,P(3.7)式中為第個染色體的適應(yīng)值在種群中有達到小排列的序號。為最佳染色體選擇概率，為樣本數(shù)。最后計算染色體的累計選擇概率值,,k=1,2,3,…,P(3.8)其后的選擇方法同輪盤的賭類似。最佳個體保存法最佳個體保存法把群體中適應(yīng)度最高的個體不進行配對交叉而直接復(fù)制到下一代。該方法的好處在于保證了進化過程中某一代的最優(yōu)解不被交叉和變異操作所破壞。但是該方法是一些局部優(yōu)化個體的遺傳基因會急速增加進而達到局部有化解，器全局搜索能了差，不利于多峰值的搜索問題，所以該方法一般與其他選擇方法相結(jié)合使用。2）交叉運算（crossover）交叉操作：通常有單點交叉、多點交叉、均勻交叉等幾種方法。隨機選擇兩個個體，按照一定的交叉概率選擇交叉點進行交叉，用交叉后的子代個體替原種群中的父代個體，產(chǎn)生新的種群。前面提到這里的染色體是不等長個體，所以交叉點應(yīng)該分別在要交叉的兩個個體中進行選擇。①離散雜交離散雜交又分為部分離散雜交和整體離散雜交。部分離散雜交即是在父代向量中選擇一部分分量（如一個分量或從某分量以后的所有分量）然后交換這些分量以形成后代。例如：若選擇交換第k個分量以后的所有分量。則兩個后代為而整體雜交則是以0.5的概率交換所有分量，這有點像二進制編碼時的均勻性雜交，這些我們也可以通過生成模板的形式來實現(xiàn)，若某一位是1則交換相應(yīng)的分量，否則保留。顯然，通過離散雜交產(chǎn)生的后代，其分量仍然在其定義區(qū)間之內(nèi)。②算術(shù)雜交算術(shù)雜交也分為部分算術(shù)雜交和整體算術(shù)雜交。部分算術(shù)雜交也是先在父解向量中選擇一部分分量，如第個分量以后的所有分量，然后生成個（0,1）間的隨機數(shù),…則兩個后代定義為3）變異運算遺傳算法中使用變異算子使得遺傳算法具有局部的隨機搜索能力，能找到更精確的值，并配合交叉操作以維持種群的多樣性，防止出現(xiàn)過早收斂。一般來說變異算子也有兩類，一類為基本的二進制變異操作，另一類為浮點數(shù)交叉。①二進制變異運算變異就是以很小的概率隨機的改變?nèi)后w中染色體某些基因的值。變異操作的基本過程是：在二進制編碼方式中，百衲衣算子隨機的將某個基因值取反，即“0”編程“1”或“1”變成“0”。例如：浮點數(shù)變異運算對于浮點數(shù)來說常用的變異手段有均勻變異、邊界變異和非均勻變異等。其主要目的就是構(gòu)造變異一個擴大染色體基因值的取值范圍。均勻變異：設(shè)種群中有染色體，均勻變異則先在染色體中選擇一個分量，然后在一個定義區(qū)間[,]中均勻地選擇一個數(shù)代替，由此得到新的染色體為=（，，…，）。6.遺傳算法的終止條件作為一種算法不能無限地執(zhí)行下去，要在合理的時間內(nèi)終止。遺傳算法通常用到的終止標準有：①收斂標準。算法執(zhí)行到一定程度，群體中的個體字符串結(jié)構(gòu)會很相似，再執(zhí)行下去難以得到更好的個體了，這時認為算法收斂了。當然，判斷收斂的標準可以是不同的。②時間標準。預(yù)先給定算法的執(zhí)行時間，如給定要產(chǎn)生的個體的總數(shù)、循環(huán)的代數(shù)或者計算的時間長度。③精度標準。當找到的個體的評價函數(shù)值的精度達到一定要求后，算法就可終止。7.遺傳算法的參數(shù)設(shè)置從前面遺傳算法的討論中我們可以看出，每個部分都有許多參數(shù)，如變異概率、雜交概率、群體大小等，不同的參數(shù)取值使遺傳算法體現(xiàn)不同的行為。有一些問題的參數(shù)取值是相互關(guān)聯(lián)的，這些參數(shù)很大程度影響著解的質(zhì)量。在簡單遺傳算法中，在演化過程中，這些參數(shù)是固定不變的，而對于不同類型的問題，往往要采用不同的參數(shù)才能得到滿意的解。因此我們不得不花費很多時間來試驗到底哪個參數(shù)最適合我們要解決的問題。但是由于遺傳算法的各個部分是相互作用的，這些參數(shù)組合起來的情況非常多，實際上想通過手工調(diào)節(jié)來找到最佳的參數(shù)組合是很費力的一件事。如果能在演化過程中，程序自己不斷的調(diào)節(jié)這些參數(shù)，就能使算法適用于更多類型的問題。參數(shù)的調(diào)節(jié)方式大致可以劃分為三類：確定性調(diào)節(jié)，適應(yīng)性調(diào)節(jié)，自適應(yīng)性調(diào)節(jié)。確定性調(diào)節(jié)方式是指參數(shù)的調(diào)節(jié)方式是靠事先確定好的策略調(diào)節(jié)的，這種調(diào)節(jié)沒有用到解的反饋信息，只用到了時間信息。例如在變異策略中，我們可以在前面若干代中使用大的步長變異，而當收斂到一定代數(shù)后使用步長較小變異。這里我們只用到了代數(shù)這一個參數(shù)，并沒有其他關(guān)于群體的反饋信息。適應(yīng)性調(diào)節(jié)方式是根據(jù)群體中解的反饋信息來調(diào)節(jié)參數(shù)的，這種調(diào)節(jié)方式是最為常用的，也是非常有效的方法。例如我們前面提到的變異方法大多屬于這一類型。自適應(yīng)調(diào)節(jié)是指將參數(shù)作為個體的一個染色體和其他需要優(yōu)化的參數(shù)一起用遺傳算法進行優(yōu)化。參數(shù)調(diào)節(jié)本身就是一個復(fù)雜的優(yōu)化過程，而遺傳算法本身也是一種優(yōu)化算法，既然遺傳算法可以用來優(yōu)化非線性規(guī)劃問題，也應(yīng)該可以用來優(yōu)化自身的參數(shù)。這種方法己經(jīng)成功的用于變異算子，雜交算子和群體大小的優(yōu)化。但是這種方法并不適用于罰函數(shù)的參數(shù)調(diào)節(jié)。與雜交和變異算子的參數(shù)不同，罰函數(shù)的參數(shù)直接影響到個體的適應(yīng)值，而雜交和變異算子的參數(shù)并不參與適應(yīng)值的計算。適應(yīng)值是我們進行個體好壞判斷的標準，當我們把罰函數(shù)的參數(shù)也作為個體的一部分時，我們得到的適應(yīng)值好的個體可能并不好，而只是它所在那一代的罰函數(shù)的參數(shù)使它得到了很好的適應(yīng)值。3.5對各種方法的綜合評價人工勢場法比較容易掌握，結(jié)構(gòu)簡單，使用方便，便于底層的實時控制，規(guī)劃出的路徑比較平滑安全，使機器人運動更加自然具有柔韌性。但是人工勢場法是一種局部規(guī)劃算法，不一定能規(guī)劃出全局最優(yōu)路徑。而且算法本生有著一定的局限性：①會出現(xiàn)機器人在沒有到達目的地時停滯或者找不到路徑的現(xiàn)象；②當障礙物與目標點的位置很近時會出現(xiàn)機器人在障礙物前振蕩甚至被障礙物推開的現(xiàn)象。不過它最突出的優(yōu)點就是簡潔方便，便于實時控制，因此在實際應(yīng)用中使用的還是很廣泛的。柵格法是最容易掌握的一種方法，其簡單的建模過程與靈活多變的搜索算法可以被各個領(lǐng)域、各個階層的人接受和使用，而且只要問題的最優(yōu)路徑存在，設(shè)計合理的搜索算法一定能求出最優(yōu)的路徑。但是當要規(guī)劃的環(huán)境比較復(fù)雜時，搜索效率會下降。另外規(guī)劃的路徑是一種折線路徑，路線不光滑，機器人在轉(zhuǎn)角處的速度會受到影響，對于高速運行的機器人，這個問題就顯得更加突出了。中垂線法的特點是算法簡單，而且算法可以保證機器人到達目標點時滿足位置和方向的要求。但是這種方法使用的范圍是有限的。當小車距位于球和對方球門之間的區(qū)域時，不能直接用中垂線法，而需要決策部分的相應(yīng)算法來實現(xiàn)控制小車首先繞到球的另一面。遺傳算法、神經(jīng)網(wǎng)絡(luò)都屬于人工智能方法。遺傳算法是一種全局算法，但是算法比較復(fù)雜，設(shè)計者需要花大量的精力來設(shè)計。另外該算法采用的是迭代方法，如果迭代次數(shù)太多，會影響到實時性。綜上所述，可以看出沒有一種方法是完美的，每一種方法都有自己的優(yōu)點和不可避免的缺點。我們應(yīng)該設(shè)法利用這些優(yōu)點，用其他的方法來彌補其缺點?，F(xiàn)在研究者們常用的方法就是將兩個或者兩個以上的方法相互結(jié)合，來解決這類問題。例如：柵格法和人工勢場法的結(jié)合，柵格法和遺傳算法的結(jié)合，人工神經(jīng)網(wǎng)絡(luò)和進化算法的結(jié)合等等。第四章matlab實現(xiàn)人工勢場、遺傳算法的仿真4.1環(huán)境建模實現(xiàn)路徑規(guī)劃的前提是對環(huán)境進行描述，即對環(huán)境進行建模。賽場為黑色（不反光的）木質(zhì)長方形場地（圖4.1），其尺寸是150cm×130cm，帶有5cm高，2.5cm厚的圍墻。圍墻的側(cè)面為白色，圍墻頂部為黑色。在場地的四角固定四個7cm×7cm的等腰三角形以避免球進入角落。木板表面的材質(zhì)與乒乓球臺相同。圖4.1實際2D環(huán)境中圈半徑是20cm，作為門區(qū)的一部分的圓弧沿球門線長20cm，垂直于球門線5cm。主要直線、圓弧（中線、門區(qū)邊界線和中圈）均為白色，3mm寬。球門寬40cm，沒有橫梁和網(wǎng)。門線是恰好位于球門前長40cm的直線。門區(qū)包括位于球門前尺寸為70cm×15cm的長方形區(qū)域以及附屬的弧形區(qū)域，弧形區(qū)域平行于球門線長度為20cm，垂直于球門線高度為5cm。將球場的圖像以q