基于免疫遺傳的機器人路徑規(guī)劃【開題報告】

1、畢業(yè)設計開題報告電氣工程與自動化基于免疫遺傳的機器人路徑規(guī)劃一、選題的背景與意義機器人是一個集環(huán)境感知、動態(tài)決策與規(guī)劃、行為控制與執(zhí)行等多功能于一體的的綜合復雜系統(tǒng)。它集中了計算機工程、機械工程、人工智能、控制論以及仿生學等多學科的科研成果，代表著機電一體化的最高成就，同樣也是20世紀自動控制最具有說服力的成就，是當代最高意義上的自動化。自從1959年，機器人之父約瑟夫？恩格爾伯格推出第一款機器人以來，出現(xiàn)了各種各樣的機器人，機器人性能也不斷的在完善，它們在農(nóng)業(yè)、工業(yè)、航天以及空間探測等許多領域發(fā)揮著非常重 要的作用。先進機器人技術的發(fā)展代表著一個國家的綜合科技實力和水平，目前許多發(fā)達國家，甚

2、 至一些發(fā)展中國家都已將機器人技術列為二十一世紀高新技術發(fā)展計劃。移動機器人是一種具有自規(guī)劃、自組織和自適應能力并能夠在復雜環(huán)境下正常完成所要求工作的機器人。導航技術是反映移動式機器人自主能力的關鍵問題之一，也是其實現(xiàn)真正智能化和完全 自主移動的關鍵技術。實質(zhì)上我們可將導航問題描述為這樣三個問題：“我現(xiàn)在在哪里、“我要去哪里”以及“應該用什么方法去我想去的地方”。而這三個問題可由兩級規(guī)劃完成，即局部規(guī)劃和全局規(guī)劃。其中第一個和第三個問題，即機器人目標制導和路徑跟蹤問題，可由局部規(guī)劃解決。第二個 問題，即將全局大任務分解成局部子任務，通過不斷完成這些子任務最終達到全局目標的問題，可 由全局規(guī)劃完

3、成。全局規(guī)劃一般是建立在已知環(huán)境信息的基礎上，適應范圍相當有限；局部規(guī)劃能 適應于不確定環(huán)境的情況，但其對規(guī)劃系統(tǒng)的品質(zhì)要求較高并且具有有時反應不及時的缺點。通過上述描述可知，機器人路徑規(guī)劃是機器人導航技術中不可或缺的重要組成部分，它要求機器人根據(jù)給予的指令及周圍環(huán)境信息在滿足某個或某些性能指標（如距離、時間、能量、工作代價 等）條件下，自主選定一條從起始點到達任務目標點的無碰障最優(yōu)或次路徑。它是移動機器人完成 任務的安全保障。傳統(tǒng)的路徑規(guī)劃方法在解決機器人路徑規(guī)劃問題時缺乏自適應性和魯棒性，計算量大且復雜， 很難得到最優(yōu)路徑。遺傳算法由于其并行隨機搜索的特點，在解決路徑規(guī)劃問題時有獨特的優(yōu)勢

4、， 取得了一定的成果。但其仍存在缺乏指導性，易產(chǎn)生無效路徑，收斂速度慢，易早熟等問題，無法 有效保證路徑規(guī)劃的計算效率。為了進一步提高遺傳算法在路徑規(guī)劃中的搜索精度和收斂速度，應用基于免疫遺傳算法的路徑規(guī)劃方法去解決已有成果的缺陷，同時亦嘗試對一般免疫遺傳算法進行適當?shù)母倪M，以期能夠在路 徑規(guī)劃中得到好的效果二、研究的基本內(nèi)容與擬解決的主要問題：（一）研究的基本內(nèi)容1、查找文獻數(shù)據(jù)，了解機器人路徑規(guī)劃傳統(tǒng)方法，并了解遺傳免疫算法；2、用MATLAB完成遺傳免疫算法對典型多峰測試函數(shù)的搜索；3、用遺傳免疫算法完成機器人在柵格環(huán)境下的搜索；4、對搜索策略進行分析評價。5、要求能在文獻閱讀的查找基礎

5、上完成基本的遺傳免疫算法的編程，建立柵格環(huán)境，用遺傳 免疫算法進行搜索，達到預期的規(guī)定要求。（二）要解決的關建問題1、用柵格法建立環(huán)境模型。2、在遺傳的基礎上建立 MATLAB函數(shù)，并對多峰測試函數(shù)進行驗證。3、設置障礙物，并確定適應度函數(shù)模型。三、研究的方法與技術路線：到目前為止，機器人的發(fā)展仍處于初始階段，但是機器人路徑規(guī)劃的方法已經(jīng)層出不窮了。根 據(jù)規(guī)劃體對環(huán)境信息的認知程度，機器人路徑規(guī)劃方法可分為基于已知環(huán)境模型的全局路徑規(guī)劃和 基于傳感器信息的局部路徑規(guī)劃。對于環(huán)境已知條件下的離線全局規(guī)劃方法，已取得大量結果。下 面將主要研究全局路徑規(guī)劃。移動機器人運動環(huán)境模型的建立環(huán)境建模是機器

6、人路徑規(guī)劃的重要環(huán)節(jié)，目的是為了建立一個便于進行路徑規(guī)劃使用的環(huán)境模 型。合理的環(huán)境模型要求是便于計算機存儲、處理、更新和使用。當然在實際應用中，這些要求有 可能會有沖突。移動機器人的工作環(huán)境一般可簡化成二維模型，用地圖來表示環(huán)境的信息情況。關 于環(huán)境地圖的創(chuàng)建，有三個基本問題需要解決：如何表示環(huán)境地圖；如何獲取環(huán)境信息；如何實時 更新地圖。目前地圖創(chuàng)建的方法很多，大致可以分為柵格法、特征法和拓撲法這三類。特征法建立的模型雖然易于用計算描述和表示，但其需要特征提取的辦法處理過程，對傳感器 噪聲非常敏感，只適于高度的結構化的環(huán)境。拓撲法在前面我們就說過，當障礙物增加時，實時更 新及其困難。而柵格

7、法建立的模型以為計算機存儲、操作、顯示與維護，并且易于擴充、修改，直 觀性強，特別是易與遙感影像的聯(lián)合處理。鑒于此，本人將使用柵格法建立環(huán)境地圖。在使用柵格法創(chuàng)建地圖時，需要做以下幾個假設：（1）機器人的運動是在二維空間中;(2)用尺寸相同的柵格對工作環(huán)境進行劃分。若柵格包含有障礙物，則稱為障礙柵格，并用數(shù)字“1”標示；否則，稱之為自由柵格，并用數(shù)字“0”標示；(3)由于環(huán)境是靜態(tài)的，所以機器人在運動過程中障礙物的大小和位置都是不變的。在大多數(shù)文獻中，對柵格進行標識時要么使用直角坐標法，要么使用序號法。而此處，將會使用兩者結合一起來標識。因為相比坐標法，序號法占有的內(nèi)存很少，便于在遺傳操作中使

8、用。另一 方面，直角坐標法在描述柵格之間的相對位置，計算路徑長度及檢驗路徑可行性方面有著巨大的優(yōu) 勢。下面給出直接坐標法和序號法轉換關系：X = N%niY = N /n2上式中，X和Y分別表示指定柵格的橫坐標和縱坐標，N表示該柵格的序號，ni和n2分別指橫坐標和縱坐標的柵格數(shù)。建模后的10*10機器人工作環(huán)境如下圖所示。0123456789 XS(O)123 1415678g011121311415Id17IS1920212223124252627，2829303 口3233 J34，3536373839404口4243144，454d474g4950515253545556575S5960

9、61626364656667施】6970711173，74 1757677 17879SOS1S283S4S5S687SS8990919293，9495期97E(W圖序號法和直鬲坐標法建立例機翳入空間模型全局路徑規(guī)劃全局路徑規(guī)劃的作業(yè)環(huán)境信息是完全已知的，故又稱為靜態(tài)路徑規(guī)劃，其主要包括環(huán)境建模和路徑搜索策略兩個子問題。典型的全局路徑規(guī)劃方法有柵格法、拓撲法、可視圖法、概率路徑圖法、廣度優(yōu)先搜索方法等。柵格法柵格法是當前研究最廣泛的路徑規(guī)劃之一，該方法Hovoden于1968年提出。柵格法的主要思想3是將機器人的工作環(huán)境劃分成一系列具有二值信息的網(wǎng)格單元，障礙物和自由空間分別被不同的數(shù) 值所標

10、示（如0表示自由柵格，1表示障礙物柵格）。這些柵格構成了一個連通圖，在這個連通圖上 搜索一條從初始位置到目標柵格的路徑。在柵格法中，柵格的大小是由機器人行進的區(qū)域的可視度所決定的，其直接影響著環(huán)境信息存 儲量的大小和規(guī)劃時間的長短。柵格選的小，環(huán)境的分辨率就高，在密集障礙物或狹窄通道中發(fā)現(xiàn) 路徑的能力強，但環(huán)境信息的儲存量大，規(guī)劃時間長，降低了系統(tǒng)的實時性；柵格選的大了，環(huán)境 信息儲存量小，決策速度快，抗干擾能力強，但環(huán)境的分辨率低，在相應環(huán)境中發(fā)現(xiàn)路徑的能力變 差。因此合理選擇柵格的大小是柵格法的重要問題。在某個局部柵格中，所有的參考點（也即機器人穿行環(huán)境時收集的傳感器數(shù)據(jù)）應該是互相可 見

11、的。這就意味著在空曠的區(qū)域同一時間能夠有更多的參考點是可視的，由此一個有著粗糙解析的 大柵格就可以將此區(qū)域描述出來。相反的在混亂區(qū)域，當機器人圍繞障礙物轉向或穿過門時，它容 易很快的丟失掉其他參考點的視線。描述這些區(qū)域的柵格就應當較小而且要有一個較好的解析。這 也就使得機器人在障礙物間或狹窄走廊中的機動行進成為可能。另外，柵格越小，就更容易做到路 徑的實時再規(guī)劃。雖然這種方法不能保證所有可能的路徑都能夠被發(fā)現(xiàn)，但是它提供了一種對環(huán)境 本能和實踐的描述，使得機器人更加人性化，“正如機器人能夠自主看見一樣”。區(qū)域中的柵格通過那些重疊在不同柵格上的參考點相互連接在一起。這樣整個機器人的路徑規(guī)劃問題也

12、就分解成了如何規(guī)劃從一個參考點運行到下一個參考點最優(yōu)無碰路徑問題。免疫遺傳算法與一般免疫算法一樣，免疫遺傳算法將待求解的問題對應為抗原，問題的解對應為抗體，在許 多方面表現(xiàn)出超越遺傳算法和免疫算法的優(yōu)點。其具有下述功能：克服通常遺傳算法收斂方向無法 控制的缺陷，把目標函數(shù)和制約條件作為抗原，這就能保證所生成的抗體直接與問題相關聯(lián)，收斂 方向能夠得到控制。生成的抗體能夠有效的排除抗原也就相當于求得了問題的最優(yōu)解。對于抗原親 和力高的抗體進行記憶，能促進快速求解，即當遇到同類抗原時可以快速生成與之對應的抗體。一般免疫遺傳算法組成免疫遺傳算法的流程圖：抗原輸入初始抗體產(chǎn)生計算適應度計算抗體濃度 計算

13、選擇概率抗體產(chǎn)生(、交叉,變異，裝 樣性保持)遺傳操作結束圖1.免疫遺傳算法流程圖(1)抗原輸入，即將目標函數(shù)和各種約束作為抗原。(2)初始抗體的產(chǎn)生，即生成初始解。一般都是根據(jù)問題的特征隨機生成一組初始化解。(3)親和度計算。親和度指兩者的關聯(lián)性。生物體內(nèi)，親和度分為抗體一抗原間親和度以及抗 體一抗體間親和度這兩類。前者即相當于遺傳算法中的適應度，后者體現(xiàn)了不同抗體之間 的相似度，是構造群抗體濃度必須的量。(4)抗體的抑制/促進。與抗原親和度高的抗體在算法中顯然受到促進，會以較高的概率進入下 一代抗體群。這樣做往往會使種群過于單一，易陷入局部最優(yōu)。因此要引入必要的抑制策 略以保持種群中抗體的

14、多樣性，這可以通過構造抗體的選擇概率時加入抗體濃度因素來實 現(xiàn)，也即抗體間相似度高的抗體，應受到抑制。(5)遺傳操作。當前種群中通過抗體的抑制/促進，抗體交叉、變異生成新一代抗體，進入下一代。算法通過綜合考慮抗體適應度和其在種群中的濃度，構造選擇概率對其進行選擇，對 選擇出來的抗體群進行遺傳操作(交叉、變異)，產(chǎn)生新一代抗體。既確?？贵w群整體朝著適應度高的方向進化，又維持了種群中抗體的多樣性。本人在基本框架的基礎上，對算法的具體步驟進行改進，增加精英選擇策略等以其能夠獲得高效的效果。個體編碼個體表示移動機器人在其工作空間中的一條運動路徑。機器人由其起始位置 S g路徑運動到終點位置E,即為1個

15、個體。該個體用直角坐標形式可表示為：(0 , 0), (0, 1), (0, 2), (1, 3), (2, (3 , 5) , ?, (9 , 9)。若每一位坐標用4位二進制數(shù)表示，則同一個體可表示為：0 000, 0 000,0 000, 0 001 , ?, 1 001 , 1 001。若用柵格序號表示，則同一個體可表示為：0, 10, 20, 31,42, 53,，99。由此可見，個體采用柵格序號編碼較直角坐標或二進制編碼長度短、簡明、直觀。種群初始化初始群體是遺傳算法迭代運算的起點，它由一定數(shù)目的個體組成，在機器人運動的起點到終點之間，用一系列隨機選擇、自由、不一定連續(xù)的柵格序號連接

16、起始點和終點。在種群初始化過程中，確保個體基因位上填充的都為自由柵格，并且初始種群中的每個個體的長度大于3,再經(jīng)過插入、刪除操作生成一系列不問斷無障礙路徑。采用這種操作方法有利于種群初始化。個體適應度函數(shù)個體的適應度函數(shù)與免疫算法的計算時間和效率密切相關。這里所討論的問題是求從起始點到終點的1條最優(yōu)路徑，且該路徑不能與障礙物相交，以確保機器人按這條路徑運動時不與障礙物發(fā)生碰撞。選取如下個體適應度函數(shù)：1精英選擇策略精英選擇策略是由 de.K.A.Jong提出的，其主要是為了解決遺傳算法不能收斂到全局最優(yōu)解這個缺陷。其主要思想就是，將當前群體中迄今出現(xiàn)的最佳個體作為精英個體不進行任何操作而直接復

17、制到下一代中。定義描述即為，假設免疫遺傳算法進化到第t代時，群體中的最優(yōu)個體為a(t),且新一代群體為A(t+1),若a(t)不屬于A(t+1),則將a(t)作為精英個體復制到 A(t+1)中，作為其的個體。 此種免疫遺傳算法，其具體步驟如下：進行個體免疫遺傳編碼，隨機產(chǎn)生初始種群；按照設計的適應度函數(shù)，確定種群中每個個體的適應度值，并且將適應度最大抗體作為精英抗體保存在一個專有變量中；若種群為第一代抗體群，則轉到第五步，否則，繼續(xù)；再次確定抗體群中每個個體的適應度值。若當前種群中沒有個體的適應度值比精英抗體適應度值大，則將該精英抗體復制到抗體群中，并將抗體群中適應度最小的抗體淘汰掉；或者若當

18、前群體中有個體適應度值大于精英抗體的適應度值，則將此作為新的精英抗體保存到專有變量中。否則，繼續(xù)；計算抗體濃度，對抗體執(zhí)行選擇和復制操作；對抗體群實行交叉和變異操作；判斷設置條件是否得到滿足。若滿足，算法終止；否則，回到第四步繼續(xù)。四、研究的總體安排與進度：2010.11.30-12.30:查找文獻資料，了解路徑規(guī)劃，遺傳免疫算法，完成開題報告的撰寫，2011.1.1-1.30:熟悉MATLAB的編程語言，完成算法的編寫。2011.2.1-3.30:進行系統(tǒng)軟件的調(diào)試。2011.4.1-4.30:對結果進行分析評價，撰寫畢業(yè)論文，并進行答辯。五、主要參考文獻：1袁曾讓，高明.在動態(tài)環(huán)境中移動機

19、器人導用和避碰的一種新方法.機器人,2000,22(2):81-882曹雁軍.機器人路徑規(guī)劃研究.河北工業(yè)大學碩士論文，20083莫宏偉，左興權.人工免疫系統(tǒng).科學出版社，2009:3-284李愛萍，李元宗.機器人路徑規(guī)劃方法的研究.機械工程與自動化,2009(5):194-1965王醒策，張汝波，顧國昌.基于勢場柵格法的機器人全局路徑規(guī)戈IJ.哈爾濱工程大學學 報,2003,24(2):170-1746于洪斌，李孝安.基于柵格法的機器人快速路徑規(guī)劃.微電子學與計算機.2005,22(6):98-1007陳曦，譚冠政，江斌.基于免疫遺傳算法的移動機器人實時最優(yōu)路徑規(guī)劃.中南大學學報(自然版)，2008,39(3):577-5838孫樹棟.遺傳算法在機器人路徑規(guī)劃中的應用研究.西北工業(yè)大學學報，1998,16(1):79-83.9李擎，馮金玲，柳延林等.自適應遺傳算法在移動機器人路徑規(guī)劃中的應用.北京科技大學學報，2008,30(3):316-323J.Timmis, A.Hone, T.Stibor,etc. Theoretical advances