遺傳算法在機器人路徑規(guī)劃中的應用分析研究

1、畢業(yè)論文題目：遺傳算法在機器人路徑規(guī)劃中的應用分析研究摘要移動機器人路徑規(guī)劃作為自主式移動機器人技術的一個重要組成部分，是研究移動機器人技術較為活躍的課題之一，吸引了國內(nèi)外大批的研究學者。隨著各種新方法和新技術的不斷出現(xiàn)，對路徑規(guī)劃的研究有了更廣闊的天地。我國在智能移動機器人研究方面雖然已經(jīng)取得了一定的成果，如地面自主導航車、水下自主機器人和飛行機器人等。但由于起步較晚，在研究和應用方面都落后于一些西方國家，而且還沒有達到完全實用。因此，進行這項研究，具有一定的理論和工程應用意義。首先從移動機器人的歷史和現(xiàn)狀出發(fā)，對比了國內(nèi)外的不同發(fā)展狀況，對移動機器人領域的研究方向進行了綜述。著重介紹了移動

2、機器人路徑規(guī)劃中常用的方法，對柵格法、遺傳算法等進行了逐一的分析闡述。應用于機器人路徑規(guī)劃的有很多傳統(tǒng)的優(yōu)化方法，本文主要介紹的最基本的一種算法-遺傳算法在機器人路徑規(guī)劃中的應用。遺傳算法（簡稱ga）是一種借鑒生物界自然選擇和自然遺傳機制的隨機化的搜索算法，它將“適者生存”這一基本的達爾文進化理論引入串結構，并且在串之間進行有組織但又隨機的信息交換，伴隨著算法的進行，優(yōu)良的品質被逐漸保留并加以組合，從而不斷產(chǎn)生出更佳的個體，也就是不斷地接近于最優(yōu)解。本文采取了柵格法對機器人工作空間進行劃分，用序號標識柵格，并以此序號作為機器人路徑規(guī)劃參數(shù)編碼。同時引入間斷無障礙路徑概念以簡化初始種群產(chǎn)生，而且

3、采用了遺傳算法操作對初始路徑進行尋優(yōu)，這里遺傳算法操作主要指的是選擇操作、交叉操作、變異操作；尋優(yōu)主要是選取適當?shù)膫€體評價函數(shù)及適應函數(shù)對路徑進行尋優(yōu)。最后采用matlab對機器人路徑進行仿真，靜態(tài)顯示進化過程中生成的路徑并顯示機器人在障礙物存在情況下避障的運動過程。對不同參數(shù)設置下的路徑進行比較，不同種群大小的適應度值進行統(tǒng)計分析，并將不同環(huán)境下的最佳路徑與最差路徑作比較。傳統(tǒng)優(yōu)化方法在機器人路徑規(guī)劃這類復雜非線性優(yōu)化問題中缺乏足夠的魯棒性。遺傳算法是國際上80年代中期以來獲得廣泛應用的一種新型參數(shù)優(yōu)化方法，它基于自然選擇原理和群體進化機制，有許多區(qū)別于傳統(tǒng)優(yōu)化方法的特點，對機器人路徑尋優(yōu)效

4、果更明顯。關鍵詞 ：遺傳算法，機器人，路徑規(guī)劃，優(yōu)化abstract to be a important component of the independent -like migration robot technology, the motion robot way plan is one of more active topics of motion robot technology and has attracted large quantities of the domestic and foreign research scholar. with new method and n

5、ew technologys unceasing appearance, there is a broader world to research the way plan. although our country had already made certain progress in intelligent migration robot research aspect, such as ground autonomous navigation vehicle, submarine independent robot and flight robot and so on .but it

6、starts late, it falls behind some western country in the application aspect and has not achieved completely usability. therefore, it has certain theory and project application significance to conduct this research. firstly， from the history and the present situation of moved robot ，comparing the dom

7、estic and foreign different development condition , it starts the summary. from the research direction of migration robot. it introduces commonly used method in motion robot way plan emphatically, and has carried on the analysis elaboration one by one to the grid law, the genetic algorithm and so on

8、 applied to the plans in the robot way has many traditional optimized methods, this article mainly introduce the most basic one algorithm - genetic algorithm in the application of the robot way plan .the genetic algorithm (ga) is one kind which profits from the biosphere natural selection and the na

9、ture heredity mechanism randomisation searching algorithm, it introduces his basic darwin evolution theory of the survival of the fittest” to string structure, and carries on organized but the stochastic exchange of information between the strings. following algorithm advance, the fine quality is re

10、tained gradually and combined, thus produces a better individual unceasingly and also closes to the optimal solution unceasingly . the article adopts the method of grid work to divide robot space , with the serial numbers to identify grid, and as the parameters of code of robot path planning .and th

11、is paper introduces barrier-free path concept to simplify the initial population and using the genetic algorithm operation for the initial route optimization of genetic . the operations mainly refer to selection operation , crossover operation and variation operation. this paper mainly adopts indivi

12、dual evaluation function and the fitness function for optimal selection . finally using matlab to simulate robot path. traditional optimization methods which is used in this kind of complex nonlinear optimization problems lack of robustness. it displays the path of evolution statically and displays

13、the avoidance movement of the robot in the environment of obstacles .finally, different optimized paths under different parameters are compared; fitness values of various population sizes are statistically analyzed and best optimized paths and worst optimized paths in different environments are comp

14、ared as well. genetic algorithm is a new parameters optimization method which has won extensive application in the whole world since the middle of 1980s.it is based on natural selection principle and group evolution mechanism. there are many characteristics which are different from traditional optim

15、ization methods and has better effect in robot path optimization.key wordsgenetic algorithms, robot, path planning, optimize目錄摘要1英文摘要2第一章 緒論.61.1課題的研究背景.61.2國內(nèi)外路徑規(guī)劃發(fā)展狀況.81.3路徑規(guī)劃解決的基本問題.101.4論文主要研究內(nèi)容（原理）概述.111.4.1遺傳算法的基本運算過程如下.141.4.2路徑規(guī)劃的實現(xiàn).151.4.3 機器人路徑最優(yōu)化的實現(xiàn).151.5本章小結.15第二章 機器人路徑規(guī)劃和遺傳算法162.1 路徑規(guī)劃研

16、究概述.162.1.1 路徑規(guī)劃分類.162.1.2 路徑規(guī)劃問題特點.162.1.3路徑規(guī)劃方法.172.1.4 優(yōu)化問題1922遺傳算法192.2.1遺傳算法定義.192.2.2 遺傳算法特點.192.2.3 編碼.202.2.4適應度函數(shù).202.2.5初始群體的選取.21第三章基于遺傳算法的機器人路徑的優(yōu)化223.1.參數(shù)設定.223.2環(huán)境建模.223.3生成初始種群.233.4 適應度函數(shù)設置.243.5 選擇操作.253.5.1 什么是輪盤賭選擇.263.6 交叉操作.283.7 終止條件.29第四章 仿真及結果分析.314.1 仿真程序.314.2 仿真結果及分析.35致謝38

17、參考文獻.39圖列和表列圖1 交叉操作示意圖.13 圖2 變異操作示意圖. .14圖3 機器人路徑空間模型 . 22圖4 初始種群產(chǎn)生流程圖23圖5選擇操作得流程圖 26圖6轉盤法示意圖 27表1 10個染色體種群按比例的選擇過程 27圖7交叉操作示意圖. 28圖8整個優(yōu)化過程流程圖.30第一章 緒論1.1課題的研究背景現(xiàn)代機器人的研究始于20世紀中期，其技術背景是計算機和自動化的發(fā)展，以及原子能的開發(fā)利用。 自1946年第一臺數(shù)字電子計算機問世以來，計算機取得了驚人的進步，向高速度、大容量、低價格的方向發(fā)展。 大批量生產(chǎn)的迫切需求推動了自動化技術的進展，其結果之一便是1952年數(shù)控機床的誕生

18、。與數(shù)控機床相關的控制、機械零件的研究又為機器人的開發(fā)奠定了基礎。 另一方面，原子能實驗室的惡劣環(huán)境要求某些操作機械代替人處理放射性物質。在這一需求背景下，美國原子能委員會的阿爾貢研究所于1947年開發(fā)了遙控機械手，1948年又開發(fā)了機械式的主從機械手。 1954年美國戴沃爾最早提出了工業(yè)機器人的概念，并申請了專利。該專利的要點是借助伺服技術控制機器人的關節(jié)，利用人手對機器人進行動作示教，機器人能實現(xiàn)動作的記錄和再現(xiàn)。這就是所謂的示教再現(xiàn)機器人?，F(xiàn)有的機器人差不多都采用這種控制方式。 作為機器人產(chǎn)品最早的實用機型是1962年美國amf公司推出的“verstran”和unimation公司推出的

19、“unimate”。這些工業(yè)機器人的控制方式與數(shù)控機床大致相似，但外形特征迥異，主要由類似人的手和臂組成。 1965年，mit的roborts演示了第一個具有視覺傳感器的、能識別與定位簡單積木的機器人系統(tǒng)。 1967年日本成立了人工手研究會（現(xiàn)改名為仿生機構研究會），同年召開了日本首屆機器人學術會。 1970年在美國召開了第一屆國際工業(yè)機器人學術會議。1970年以后，機器人的研究得到迅速廣泛的普及。 1973年，辛辛那提米拉克隆公司的理查德豪恩制造了第一臺由小型計算機控制的工業(yè)機器人，它是液壓驅動的，能提升的有效負載達45公斤。 到了1980年，工業(yè)機器人才真正在日本普及，故稱該年為“機器人元

20、年”。 隨后，工業(yè)機器人在日本得到了巨大發(fā)展，日本也因此而贏得了“機器人王國的美稱”。 隨著計算機技術和人工智能技術的飛速發(fā)展，使機器人在功能和技術層次上有了很大的提高，移動機器人和機器人的視覺和觸覺等技術就是典型的代表。由于這些技術的發(fā)展，推動了機器人概念的延伸。80年代，將具有感覺、思考、決策和動作能力的系統(tǒng)稱為智能機器人，這是一個概括的、含義廣泛的概念。這一概念不但指導了機器人技術的研究和應用，而且又賦予了機器人技術向深廣發(fā)展的巨大空間，水下機器人、空間機器人、空中機器人、地面機器人、微小型機器人等各種用途的機器人相繼問世，許多夢想成為了現(xiàn)實。將機器人的技術（如傳感技術、智能技術、控制技

21、術等）擴散和滲透到各個領域形成了各式各樣的新機器機器人化機器。當前與信息技術的交互和融合又產(chǎn)生了“軟件機器人”、“網(wǎng)絡機器人”的名稱，這也說明了機器人所具有的創(chuàng)新活力。機器人是20世紀人類最偉大的發(fā)明之一，自60年代初問世以來，經(jīng)歷40多年的發(fā)展已取得很大的進步。機器人技術的出現(xiàn)和發(fā)展，不僅使傳統(tǒng)的工業(yè)生產(chǎn)面貌發(fā)生了根本性變化，而且對人類社會產(chǎn)生深遠的影響。目前工業(yè)機器人已走向成熟，而具有特定任務的機器人也開始進入實用化研究階段。這些機器人在工業(yè)生產(chǎn)、航天、軍事、交通、安全、醫(yī)療、老人和殘疾人服務等多個領域具有十分重要的應用價值。在機器人研究的早期，機器人的結構、運動學、控制和信息處理是研究的

22、重點。隨著機器人技術的發(fā)展，單個機器人的能力、魯棒性、可靠性、效率等都有很大的提升。一方面，人們希望機器人能完成一些復雜的、需要高效率的、并行完成的任務，但這些復雜的任務由單個機器人已很難完成，需要多個機器人組成的團隊相互協(xié)調與合作共同完成，這導致了機器人的應用方式從部件式單元應用向系統(tǒng)式應用的方向發(fā)展。另一方面，人們也希望通過多機器人間的協(xié)調與合作，來提高機器人系統(tǒng)在作業(yè)過程中的效率，進而當機器人工作環(huán)境發(fā)生變化或系統(tǒng)局部發(fā)生故障時，多機器人之間仍可通過本身具有的協(xié)調與合作關系完成預定的任務。如何組織由多個機器人構成的群體系統(tǒng)，以及在這樣的群體系統(tǒng)中如何實現(xiàn)機器人的協(xié)調與合作已成為當前機器人

23、學研究領域的一個新課題。80年代以來，多機器人系統(tǒng)憑借著比單個機器人更高的精度、剛度、承載能力和靈活性而進入我們的生活中，從而引起了越來越廣泛的重視。隨著機器人向系統(tǒng)應用的方向發(fā)展，人們提出了多機器人群體的組織和控制問題，也就是多機器人協(xié)調合作問題，并形成了協(xié)作機器人學。多機器人協(xié)調合作是多機器人系統(tǒng)中一個重要部分，可以使多機器人系統(tǒng)將整體優(yōu)勢發(fā)揮得淋漓盡致。多移動機器人協(xié)調系統(tǒng)的研究是機器人技術發(fā)展的必然，也將隨著機器人應用領域的迅速發(fā)展而越來越廣泛。機器人技術的發(fā)展科學技術共同發(fā)展的一個綜合性的結果，它的發(fā)展歸功于第二次世界大戰(zhàn)之后各國為加強了本國的經(jīng)濟的發(fā)展，就加強了經(jīng)濟的投入。比如說日

24、本，戰(zhàn)后開始進行的汽車制造工業(yè)，那個時候由于人力的缺乏，它迫切需要一種機器人來進行大批量的制造，提高生產(chǎn)效率降低人的勞動強度，這是社會發(fā)展本身的一個需求。另一方面它也是生產(chǎn)力發(fā)展的必然結果，也是人類自身發(fā)展的必然結果。隨著人類的發(fā)展和社會發(fā)展，人們在探討自然、改造自然、認識自然的過程中越來越需要一種解放人類的“奴隸”，這種“奴隸”能夠代替人們?nèi)氖聫碗s和繁重的體力勞動，實現(xiàn)人們對不可達世界的認識和改造。這也是人們在科技發(fā)展過程中的一個客觀需要。那什么是機器人呢？機器人是具有一些類似人的功能的機械電子裝置，或者叫自動化裝置，它仍然是個機器，它有三個特點，一個是有類人的功能，比如說作業(yè)功能，感知功

25、能，行走功能，還能完成各種動作，它還有一個特點是根據(jù)人的編程能自動的工作，這里一個顯著的特點，就是它可以編程，改變它的工作、動作、工作的對象，和工作的一些要求，它是人造的機器或機械電子裝置。但從完整的更為深遠的機器人定義來看，應該更強調機器人智能，所以人們又提出來機器人的定義是能夠感知環(huán)境，能夠有學習、情感和對外界一種邏輯判斷思維的這種機器。那么這給機器人提出來更高層次的要求.。機器人的發(fā)展有三個階段，那么也就是說，我們習慣于把機器人分成三類，一種是第一代機器人，那么也叫示教再現(xiàn)型機器人，它是通過一個計算機，來控制一個多自由度的一個機械，通過示教存儲程序和信息，工作時把信息讀取出來，然后發(fā)出指

26、令，這樣的話機器人可以重復的根據(jù)人當時示教的結果，再現(xiàn)出這種動作，比方說汽車的點焊機器人，它只要把這個點焊的過程示教完以后，它總是重復這樣一種工作，它對于外界的環(huán)境沒有感知，這個力操作力的大小，這個工件存在不存在，焊的好與壞，它并不知道，那么實際上這種從第一代機器人，也就存在它這種缺陷，因此，在20世紀70年代后期，人們開始研究第二代機器人，叫帶感覺的機器人，這種帶感覺的機器人是類似人在某種功能的感覺，比如說力覺、觸覺、滑覺、視覺、聽覺和人進行相類比，有了各種各樣的感覺，比方說在機器人抓一個物體的時候，它實際上力的大小能感覺出來，它能夠通過視覺，能夠去感受和識別它的形狀、大小、顏色。抓一個雞蛋

27、，它能通過一個觸覺，知道它的力的大小和滑動的情況。 那么第三代機器人，也是我們機器人學中一個理想的所追求的最高級的階段，叫智能機器人，那么只要告訴它做什么，不用告訴它怎么去做，它就能完成運動，感知思維和人機通訊的這種功能和機能，那么這個目前的發(fā)展還是相對的只是在局部有這種智能的概念和含義，但真正完整意義的這種智能機器人實際上并沒有存在，而只是隨著我們不斷的科學技術的發(fā)展，智能的概念越來越豐富，它內(nèi)涵越來越寬。同時機器人能夠通過傳感器感知環(huán)境，并通過執(zhí)行器對環(huán)境起作用。機器人是現(xiàn)代科學技術發(fā)展的佼佼者，將在21世紀發(fā)揮出越來越重要的作用，使人類的生產(chǎn)活動和家庭生活發(fā)生巨大的變化。自從被譽為機器人

28、之父的著名科學家約瑟夫恩格爾伯格在1959年推出了世界上第一臺機器人以來，出現(xiàn)了形形色色的機器人，其中一些機器人由于功能獨特而引人注目。隨著機器人在工業(yè)領域的應用越來越廣泛，與外界環(huán)境交互的能力要求也在提高，機器人需要解決以下幾個問題，分別為確定在哪，應該去哪，以及怎么到達那里。最后一個問題，機器人怎么到達哪里的需求就是所謂的路徑規(guī)劃問題，它是機器人研究領域中的一個重要分支，主要是指如何獲得外部環(huán)境信息，在其工作空間中找到一條從起始狀態(tài)到目標狀態(tài)的能避開障礙物的路徑。移動機器人的路徑規(guī)劃是一種比較復雜的帶約束條件的優(yōu)化問題，而遺傳算法能夠模仿自然選擇與適者生存的生物進化過程，是求解優(yōu)化問題的一

29、種有效方法。采用遺傳算法對移動機器人進行路徑規(guī)劃時，具體算法的路徑編碼機制，將直接影響算法的實現(xiàn)和代碼的運行效率針對移動機器人不同的工作環(huán)境和具體特點，現(xiàn)已提出了多種基于定長編碼或動態(tài)編碼的機制本文提出了一種基于柵格的十進制路徑編碼機制，使得障礙物的辨識以及遺傳算法的實現(xiàn)更為簡單，增強了算法的通用性。自主導航是機器人相關技術的研究核心之一，而路徑規(guī)劃是移動機器人自主導航的基本環(huán)節(jié)之一，對于真正實現(xiàn)機器人自主導航非常關鍵，因此本文將重點研究多機器人的路徑規(guī)劃問題。機器人路徑規(guī)劃主要解決個問題：（）使機器人能從初始點運動到目標點；（）用一定的算法使機器人能繞開障礙物，并且經(jīng)過某些必須經(jīng)過的點；（）

30、在完成以上任務的前提下，盡量優(yōu)化機器人運行軌跡。1.2國內(nèi)外路徑規(guī)劃發(fā)展狀況機器人路徑規(guī)劃的研究始于20世紀70年代，就目前來看，機器人的發(fā)展仍然處于初級的階段，需要去完成的工作仍然很多，特別是在許多具體的環(huán)境中仍要具體問題具體分析。在機器人中有一類機器人叫做進化機器人，它用進化算法來實現(xiàn)機器人控制、機構等方面的優(yōu)化，在路徑規(guī)劃運用中，主要是能夠進化出合適的運動軌跡。自從提出遺傳規(guī)劃以來，遺傳規(guī)劃已經(jīng)在許多方面得到了應用，如纏繞的螺旋線的分辨，圖像壓縮，符號回歸等問題。遺傳規(guī)劃在機器人路徑規(guī)劃中的應用也是國外許多學者研究的目標，并且己經(jīng)出現(xiàn)了許多令人興奮的成果。其中比較早，影響也比較大的是人工

31、螞蟻的問題，這些應用遺傳規(guī)劃來規(guī)劃路徑的螞蟻能夠自主地尋找食物并吃掉食物，而且能夠避開障礙。除了人工螞蟻問題外還有割草機問題，在割草機問題中，割草機必須要在執(zhí)行一次程序后割草機才能夠到達正方形草坪的每一個部分。其環(huán)境及任務與人工螞蟻問題的環(huán)境基本相似。 移動機器人的路徑規(guī)劃問題已經(jīng)研究了很長時間，也產(chǎn)生了很多方法，如全局-空間法、人工勢場法以及人工神經(jīng)網(wǎng)絡法每一種方法都具有各自的優(yōu)點；但總的看來，以上方法都或多或少地存在著一些問題，如算法計算量大、容易陷入局部最優(yōu)解以及自適應能力差作為優(yōu)化算法中的一種，遺傳算法在許多優(yōu)化問題中得到了廣泛應用并取得了很好效果近年來，遺傳算法同樣被應用于移動機器入

32、的路徑規(guī)劃問題中目前有專家利用經(jīng)典遺傳算法對移動機器人進行路徑規(guī)劃，它采用固定長發(fā)的二進制編碼方式，遺傳算子也只有交叉和變異兩種雖然然該方法具有一定的自適應性，但其在使用過程中必須滿足一個約束條件，那就是沿著所規(guī)劃出的路徑前進，其路徑中各點橫坐標（或縱坐標）必須是單調上升的后來又有專家提出了一種自適應移動機器人路徑規(guī)劃算法，它采用變長度的實數(shù)編碼方式，將路徑中每個點的橫、縱坐標和該點的連通性信息作為基因進行編碼，其適應度函數(shù)則考慮了多個性能指標，如路徑的長度、路徑的光滑性以及路徑的安全性針對路徑規(guī)劃問題的特點，該算法專門設計了八種遺傳箅子，而且這八種算子還能根據(jù)進化過程中環(huán)境特點以及約束指標的

33、變化自適應地調節(jié)自身的使用概率從內(nèi)容上看，該算法似乎比較完美。但這是以大量的數(shù)值計算為代價的后來又有專家采用變長度的二進制編碼方式，它將機器人下一步的運行方向和運行距離作為基因進行編碼，同以上研究方法相比并沒有大的改進再后來又有學者提出了一種直接將路徑中各點編號進行整數(shù)編碼的變長度編碼方式。并設計了六種遺傳算子，該算法具有搜索速度較快，搜索質量較高等優(yōu)點研究發(fā)現(xiàn)，該算法還存在著以下三個主要問題需要改進：(1)初始種群的產(chǎn)生方式有待于進一步研究；(2)基于啟發(fā)式知識的遺傳算子需要進一步設計；(3）遺傳算子的使用概率應能夠在線調節(jié) 國內(nèi)外對自主移動機器人的導航和避障問題己經(jīng)做了大量的研究工作，比如

34、哈爾濱工業(yè)大學機器人研究所在1996年11月研制成功一個“導游小姐”，該機器人能夠實現(xiàn)避障和自主路徑規(guī)劃，識別障礙物的類型，具有一定的語音功能，具有極強的遙控功能。這個機器人能夠根據(jù)傳感器信息自主規(guī)劃路徑，由行走部分、行使控制器、顯示器、語音識別系統(tǒng)和大量的傳感器組成。行走部分采用差速驅動的方式。既可以在線仿真，也可以顯示機器人行走的路徑和某個時刻導游機器人所在的位置。大面積寬闊地面的清掃工作一直是一項繁重的體力勞動，人工清掃費時、費力且工作效率低，將機器人用于清掃服務，具有廣闊的應用前景。為實現(xiàn)適合我國國情的寬闊地面自動清掃，清華大學與香港中文大學合作，聯(lián)合研制開發(fā)出一種全方位移動清掃機器人

35、。國內(nèi)在遺傳規(guī)劃方面研究主要是西安建筑科技大學，云慶夏教授編寫的進化算法比較詳細介紹了遺傳規(guī)劃相關內(nèi)容。另外，上海交通大學自動化所利用+語言也對該算法在機器人沿墻移動問題進行了仿真實驗，通過對移動機器入的行為策略進行符號型編碼，然后對這些策略的組合（gp算法個體）進行自然選擇，優(yōu)勝劣汰，最后進化出滿足任務需要的優(yōu)良個體，這些個體實際上就是機器人沿墻移動的一系列指令有序組合最后的仿真結果說明了應用gp算法來演化移動機器人沿墻走行為的有效性。 近年來，自主式水下機器人由于其在海底資源探測上的優(yōu)勢而受到各國的關注，但因為水下環(huán)境十分復雜導致一般的規(guī)劃方法都難以奏效，而水下環(huán)境的擁擠程度相對較低，機器

36、人工作在同一區(qū)域的可能性較大這一特征恰好有利于基于事例的規(guī)劃方法的應用，因此該方法被廣泛的用于解決水下機器入的路徑規(guī)劃問題.目前對機器人路徑規(guī)劃這一問題的研究仍十分活躍，許多學者仍在繼續(xù)做大量的研究工作。1.3路徑規(guī)劃解決的基本問題 路徑規(guī)劃是機器人技術研究領域中的核心問題之一，也是機器人學中研究人工智能問題的一個重要的方面。路徑規(guī)劃的主要任務是在機器人所在的環(huán)境中尋求一條從已知起點到已知終點的最低代價的無碰撞路徑. 路徑規(guī)劃技術是機器人研究領域的一個重要分支。所謂機器人的最優(yōu)路徑規(guī)劃問題，就是依據(jù)某個或某些優(yōu)化準則（如工作代價最小、行走路線最短、行走時間最短等），在其工作空間中找到一條從起始

37、狀態(tài)到目標狀態(tài)的能避開障礙物的最優(yōu)路徑。根據(jù)控制方法的不同，機器人路徑規(guī)劃方法大致可以分為兩類：傳統(tǒng)方法和智能方法。移動機器人的路徑規(guī)劃是移動機器人研究領域中非常重要的問題，總的控制目標是使移動機器人運動到目標點，總的約束是在整個過程中，機器人不碰到任何一個障礙物。該問題根據(jù)對環(huán)境信息的掌握程度可以分為兩類：一類是環(huán)境信息已知的全局規(guī)劃，另一類是環(huán)境信息未知的局部規(guī)劃。全局規(guī)劃方法依照已獲取的環(huán)境信息，給機器人規(guī)劃出一條路徑。規(guī)劃路徑的精確程度取決于獲取環(huán)境信息的準確程度。全局方法通?？梢詫ふ易顑?yōu)解，但是需要預先知道環(huán)境的準確信息，并且計算量很大。局部規(guī)劃方法側重于考慮機器人當前的局部環(huán)境信息

38、，讓機器人具有良好的避碰能力。很多機器人導航方法通常是局部的方法，因為它的信息獲取僅僅依靠傳感器系統(tǒng)獲取的信息，并且隨著環(huán)境的變化實時的發(fā)生變化。和全局規(guī)劃方法相比較，局部規(guī)劃方法更具有實時性和實用性。缺陷是僅僅依靠局部信息，有時會產(chǎn)生局部極點，無法保證機器人能順利到達目的地。根據(jù)機器人對環(huán)境信息知道的程度不同可分為兩種類型。環(huán)境信息完全知道的全局路徑規(guī)劃和環(huán)境信息完全未知或部分未知的局部路徑規(guī)劃。對于環(huán)境信息完全知道的情況到目前為止已經(jīng)有許多解決方法，例如勢場法。人工勢場法的基本思想是將機器人在環(huán)境中的運動視為一種虛擬的人工受力場中的運動。障礙物對機器人產(chǎn)生斥力.目標點對機器人產(chǎn)生引力，斥力

39、和引力的合力控制機器人的運動。該方法結構簡單，易于實現(xiàn).，得到廣泛應用.但有幾個主要缺陷：存在陷阱區(qū)，在相近的障礙物面前不能發(fā)現(xiàn)路徑；在障礙物面前振蕩。在實際應用中，機器人的工作環(huán)境多數(shù)是處于兩種極端情況之間的，即環(huán)境信息部分未知。例如在自動化車間，一方面環(huán)境的整體布局已知(如車間結構，固定設備），另一方面環(huán)境中存在著不可預知的障礙物(如其它機器人、臨時堆放的物品)。本文主要研究移動機器人在 靜態(tài)環(huán)境中的路徑規(guī)劃問題。本文只進行路徑規(guī)劃問題的研究，而不考慮軌跡跟蹤問題，簡單講就是研究如何在含有障礙的環(huán)境空間中為機器人規(guī)劃出一條從起始節(jié)點到目標節(jié)點的最短無障礙路徑。構型空間法是目前研究移動機器人

40、路徑規(guī)劃的一個基本工具，其基本思想是用構型空 間中的一個點來表征移動機器人的位置與方向目前最常用的方法是可視圖法。即在一個無向圖中，將移動機器人的起始點與終止點以及移動機器人運動環(huán)境中各障礙物的頂點表征為點 的形式，從而移動機器人的有效路徑就是這樣的一些點之間與障礙物不相交的相互連接的線段。一個好的路徑規(guī)劃方法需要滿足如下指標：（1）合理性返回的任何路徑都是合理的，或者說任何路徑對控制機器人運動都是可執(zhí)行的。（2）完備性如果客觀上存在一條從起點到達終點的無碰路徑，該算法一定能找到； 如果環(huán)境中沒有路徑可通行，會報告規(guī)劃失敗。（3）最優(yōu)性算法規(guī)劃的結果路徑在某個測度（如時間、距離、能量消耗等）上

41、是最優(yōu)的。（4）實時性規(guī)劃算法的復雜度（時間需求、存儲需求等）能滿足機器人運動的需要（5）環(huán)境變化適應性算法具有適應環(huán)境動態(tài)改變的能力，隨著環(huán)境改變，不必全部重新計算。（6）滿足約束支持移動機器人運動時的完整性和非完整性運動約束。機器人路徑規(guī)劃研究一般涉及到環(huán)境表達、規(guī)劃方法、路徑執(zhí)行個方面，從而產(chǎn)生以下四個相關問題：（1）機器人如何從環(huán)境中有效的獲取周圍的障礙信息和其它相關信息。（2）機器人如何根據(jù)內(nèi)部及外部傳感器來回答當前處于地圖中什么位置。（3）機器人如何根據(jù)其處于當前地圖的位置和當前地圖中信息確定行動策略。（4）如何產(chǎn)生合適的驅動信號使機器人運動在預定的軌跡上。為了解決這些問題，機器人

42、需要具備以下四個相關的技術：（1）傳感技術。機器人通過傳感器設備檢測收集外部環(huán)境的信息，建立環(huán)境的全局地圖和得到用于局部避障障礙物信息。（2）自定位技術。如果沒有機器人的當前位置信息，也就沒有局部坐標系在地圖坐標系中的位置，從而無法進行運動的規(guī)劃。（3）運動控制?？刂茩C器人按照設定的路徑行走，涉及到機器人的結構、運動學和動力學性質。（4）規(guī)劃和決策。規(guī)劃部分是智能機器人的智能部分，規(guī)劃的大部分創(chuàng)新技術可以分為任務規(guī)劃和運動規(guī)劃，運動規(guī)劃又分為路徑規(guī)劃利軌跡規(guī)劃， 本文重點討論如何解決規(guī)劃與決策問題，該操作的前提是要對機器人當前所處的全局或局部環(huán)境建造模型。1.4論文主要研究內(nèi)容（原理）概述對于

43、路徑規(guī)劃的研究已經(jīng)有很多方法，其中不乏基于遺傳算法的研究方法，但往往是針對靜態(tài)或動態(tài)的某一種狀態(tài)，全局或局部的某一種，兩者結合的研究比較少見，同時目標函數(shù)一般也只是取路徑最短一項標準。多目標考慮的方案不多。本文主要解決的問題是在靜態(tài)環(huán)境狀態(tài)下，運用遺傳算法，實現(xiàn)路徑的規(guī)劃問題，找出可行路徑，并實現(xiàn)優(yōu)化。研究的重點是解決路徑的歸劃問題，先考慮找到可行路徑，后考慮路徑效果。 路徑規(guī)劃是指移動機器人按照某一性能指標（如距離、時間、能量等）搜索一條從起始狀態(tài)到目標狀態(tài)的最優(yōu)路徑。在機器人學領域，路徑規(guī)劃是最基本同時也是最重要的研究課題之一作為機器智能的一部分，它的任務就是使機器人在其工作環(huán)境中能夠自主

44、的從起始點運動到目標點同時滿足一定的約束條件這些約束條件包括但不限于：(1)不與障礙物碰撞；(2)運動路徑最短；(3)盡量遠離障礙物；(4)機器人耗費能量最??；(5)運動軌跡包含某些設定的必經(jīng)路點?；诓煌幕舅枷?，有多種算法出現(xiàn)。包括有人工勢場法（apf）、臭蟲法（bug）、隨機位圖法（prm、快速隨機樹（rrt）、神經(jīng)網(wǎng)絡法cnn）等。這些算法都在不同的方面有著各自的優(yōu)勢，然而在總體上，這些路徑規(guī)劃算法都還存在各自的不足。如計算復雜度局部最優(yōu)解，地圖適應性，動態(tài)環(huán)境下有效性，全局及多目標優(yōu)化能力。隨著遺傳算法（ga）的提出,機器人路徑規(guī)劃算法也得到相應的發(fā)展。通過ga在路徑規(guī)劃中的應用，

45、使得機器人更加的智能，其運行路徑也更加逼近理想的優(yōu)化要求。尤其是其優(yōu)秀的全局優(yōu)化能力和較高的搜索效率使得成為處理復雜環(huán)境下全局優(yōu)化要求的最佳算法之一。遺傳算法是模擬自然界生物進化過程與機制求解極值問題的一類自組織、自適應人工智能技術。他是建立在自然遺傳學機理基礎上的迭代自適應概率性搜索算法，具有堅實的生物學基礎。遺傳算法的工作原理為：遺傳算法的基本思想來源于達爾文的進化論和門德爾的遺傳學說，它是以生物進化的高度抽象模型為基礎的自適應搜索策略，基于自然選擇和自然遺傳這種生物進化機制，把待優(yōu)化問題的解的搜索空間映射為遺傳空間，把每一可能的解編碼為一個稱為染色體的二進制串（編碼的方法很多，如：二進制

46、編碼；浮點數(shù)編碼；參數(shù)動態(tài)編碼；有序串編碼），染色體的每一位稱為基因，每個染色體（對應一個個體）代表一個解，遺傳算法首先隨機地產(chǎn)生若干代表優(yōu)化問題侯選解的一個群體，按照預先根據(jù)目標函數(shù)確定的適應度函數(shù)計算群體中各個個體對問題環(huán)境的適應度，從而對群體中的每個成員進行評估，然后根據(jù)每個個體的適應度對各個個體所對應的染色體進行選擇，抑制適應度低的染色體，繼承適應度高的染色體，然后利用遺傳操作符（交叉，變異等）對群體中的個體進行遺傳操作，產(chǎn)生進化了的新一代群體。如此反復操作。一代一代不斷地向更優(yōu)解的方向進化，最后得到滿足某種收斂條件的最適應問題環(huán)境的群體從而獲得問題的最優(yōu)解.遺傳算法的主要實現(xiàn)步驟如下

47、：（1）問題的表示對于一個實際的待優(yōu)化的問題，要根據(jù)具體問題確定待尋優(yōu)的參數(shù)以及評價解的優(yōu)劣程度的適應度函數(shù)，從而使問題適于遺傳算法進行操作。（2）選擇待尋優(yōu)參數(shù)的編碼方式和編碼編碼是連續(xù)問題與算法的橋梁。選擇合適的強有力的編碼表達方式是遺傳算法的關鍵根據(jù)所選擇的編碼方式，將待優(yōu)化的問題的所有參變量編碼成對應的子串再將各個子串首尾聯(lián)接成一定長度的串（設串長為），即染色體，每個串代表解空間中的一個解。不同的編碼方式對待優(yōu)化問題的求解精度和算法的收斂速度有一定的影響。二進制編碼對于數(shù)值優(yōu)化問題存在著精度不高的缺點，參數(shù)動態(tài)編碼是一種提高遺傳算法精度的新的編碼方式，但是對于非線性強的多模型優(yōu)化問題，

48、dpe性能不佳，浮點數(shù)編碼具有精度高、便于大空間搜索的優(yōu)點。目前最常用的編碼方式主要是二進制編碼。（3）產(chǎn)生初始群體選擇一個整數(shù)n作為群體的規(guī)模參數(shù)。隨機生成解空間的n個初始個體作為初始群體，代表待優(yōu)化問題的一些可能解。遺傳算法就是從這一初始群體出發(fā)，通過遺傳操作模擬進化過程，最后獲得問題的最優(yōu)解。當然對于有些問題，具有某些先驗知識的情況，可以首先將這些先驗知識轉變?yōu)楸仨殱M足的一組要求，然后在滿足這些要求的解中再隨機地選取樣本，這樣選擇初始群體可以使遺傳算法更快地收斂到最優(yōu)解。(4）計算適應度函數(shù)值計算適應度函數(shù)值可以看作是遺傳算法與優(yōu)化問題之間的一個接口。遺傳算法評價一個解的好壞，不是取決于

49、它的解的結構，而是取決于相應于該解的適應度函數(shù)值。適應度函數(shù)反映了個體對問題環(huán)境適應能力的強弱是個體競爭的測度，它可以很好地控制個體生存的機會。（5）選擇、復制一般采用與適應度函數(shù)值成比例的概率方法，個體適應度函數(shù)值越高，其被選擇并復制的機會也就越多，選擇復制體現(xiàn)了“適者生存”的自然法則。選擇的目的是從群體中選出繁殖后代的雙親，復制則保留了父代的良好的基因。（6）交叉交叉是非常重要的遺傳算子。交叉操作可以分為如下兩個步驟，第一步是將新復制產(chǎn)生的個體隨機地兩兩匹配，第二步是進行交叉操作。具體過程如下：設串的長度為則串的個數(shù)字位之間的空隙標記為，-。隨機地從，l一中選取一個整數(shù)位置k將兩個父母串中

50、從位置k到串末尾的子串互相交換，從而形成兩個新個體。這兩個新個體分別組合了其父輩個體的特性，產(chǎn)生了新的基因組合。圖3是交叉操作示意圖 圖1（7）變異首先在群體中隨機地選擇一個個體，對于選中的個體以一定的概率隨機地改變串上的某一位的值，以二進制編碼為例，單靠變異操作一般不能使問題求解取得進展，因為變異發(fā)生的概率很小，但是變異能起到恢復丟失的遺傳信息生成新的遺傳信息的作用，從而保持群體中個體的多樣性，能有效地防止遺傳算法的過早收斂。圖2是變異操作示意圖 圖2（8）遺傳算法的終止遺傳算法的反復執(zhí)行（4）一（7）步，直至滿足某個收斂準則，搜索到問題的最優(yōu)解。收斂準則一般有：遺傳算法找到能接受的優(yōu)秀個體

51、（最優(yōu)解）；遺傳算法已經(jīng)進化了事先預定的最大代數(shù)；在事先預定的代數(shù)內(nèi)最優(yōu)秀個體的適應度函數(shù)值無改進；最優(yōu)秀個體占群體的比例已經(jīng)達到事先規(guī)定的比例。近年來，隨著智能方法的廣泛應用，機器人路徑規(guī)劃方法也有了長足的進展，許多研究者把目光放在了基于智能方法的路徑規(guī)劃研究上，遺傳算法是目前路徑規(guī)劃研究中應用較多的一種方法。遺傳算法不要求適應度函數(shù)是可導或連續(xù)的，而只要求適應度函數(shù)為正；作為并行算法，它的隱并行性適用于全局搜索：另外多數(shù)優(yōu)化算法是單點搜索算法，容易陷入局部最優(yōu)，而遺傳算法是一種多點搜索算法，因而更有可能搜索到全局最優(yōu)解。由于遺傳算法的整體搜索策略和優(yōu)化計算不依賴與梯度信息，解決了一些其他優(yōu)

52、化算法無法解決的問題。 本文主要研究的是應用遺傳算法的基本思想去研究機器人的路徑，去研究如何使機器人的路徑達到最優(yōu)。這里就相當于運用遺傳算法求最優(yōu)解（最小值或最大值）。比如對于一個求函數(shù)最大值的優(yōu)化問題(求函數(shù)最小值也類同)，一般可以描述為下列數(shù)學規(guī)劃模型: 式中2-1為決策變量，為目標函數(shù)式，式2-2、2-3為約束條件，u是基本空間，r是u的子集。滿足約束條件的解x稱為可行解，集合r表示所有滿足約束條件的解所組成的集合，稱為可行解集合。1.4.1遺傳算法的基本運算過程如下: a)初始化:設置進化代數(shù)計數(shù)器t=0，設置最大進化代數(shù)t，隨機生成m個個體作為初始群體p(0)。 b)個體評價:計算群

53、體p(t)中各個個體的適應度。 c)選擇運算:將選擇算子作用于群體。選擇的目的是把優(yōu)化的個體直接遺傳到下一代或通過配對交叉產(chǎn)生新的個體再遺傳到下一代。選擇操作是建立在群體中個體的適應度評估基礎上的。 d)交叉運算；將交叉算子作用于群體。所謂交叉是指把兩個父代個體的部分結構加以替換重組而生成新個體的操作。遺傳算法中起核心作用的就是交叉算子。 e)變異運算:將變異算子作用于群體。即是對群體中的個體串的某些基因座上的基因值作變動。 群體p(t)經(jīng)過選擇、交叉、變異運算之后得到下一代群體p(t 1)。 f)終止條件判斷:若tt,則以進化過程中所得到的具有最大適應度個體作為最優(yōu)解輸出，終止計算。1.4.

54、2路徑規(guī)劃的實現(xiàn)路徑規(guī)劃的實現(xiàn)分為兩種遺傳算法機制，第一種只考慮靜態(tài)障礙物的情況，找出最佳的可行路徑，還包括出現(xiàn)靜態(tài)障礙物的動態(tài)情況；機器人根據(jù)獲得的最佳路徑到達目的地同時處理期間出現(xiàn)的動態(tài)障礙物的情況，由第二種遺傳算法機制解決本文主要分析靜態(tài)環(huán)境下，運用以上的遺傳算法實現(xiàn)，通過操作算子的改進，交叉率、變異率的選擇以及適應度函數(shù)中加權系數(shù)的分析調整求得最佳的路徑。1.4.3 機器人路徑最優(yōu)化的實現(xiàn)主要結合選擇算子、交叉算子和變異算子，及目標函數(shù)設置實現(xiàn)。路徑規(guī)劃算法運用matlab建立仿真平臺，模擬實現(xiàn)過程，并對實驗結果進行統(tǒng)計分析。1.5本章小結本章主要介紹了機器人路徑規(guī)劃研究的一些概況。討論了機器人路徑規(guī)劃研究的背景，給出了研究的目的，對當前機器人路徑規(guī)