基于免疫遺傳的機(jī)器人路徑規(guī)劃【開(kāi)題報(bào)告】

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

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

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

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

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

6、人路徑規(guī)劃的重要環(huán)節(jié)，目的是為了建立一個(gè)便于進(jìn)行路徑規(guī)劃使用的環(huán)境模 型。合理的環(huán)境模型要求是便于計(jì)算機(jī)存儲(chǔ)、處理、更新和使用。當(dāng)然在實(shí)際應(yīng)用中，這些要求有 可能會(huì)有沖突。移動(dòng)機(jī)器人的工作環(huán)境一般可簡(jiǎn)化成二維模型，用地圖來(lái)表示環(huán)境的信息情況。關(guān) 于環(huán)境地圖的創(chuàng)建，有三個(gè)基本問(wèn)題需要解決：如何表示環(huán)境地圖；如何獲取環(huán)境信息；如何實(shí)時(shí) 更新地圖。目前地圖創(chuàng)建的方法很多，大致可以分為柵格法、特征法和拓?fù)浞ㄟ@三類(lèi)。特征法建立的模型雖然易于用計(jì)算描述和表示，但其需要特征提取的辦法處理過(guò)程，對(duì)傳感器 噪聲非常敏感，只適于高度的結(jié)構(gòu)化的環(huán)境。拓?fù)浞ㄔ谇懊嫖覀兙驼f(shuō)過(guò)，當(dāng)障礙物增加時(shí)，實(shí)時(shí)更 新及其困難。而柵格

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

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

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

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

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

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

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

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

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

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

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

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

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