基于免疫遺傳算法的AGV路徑規(guī)劃方法研究

井治財(cái)　史恩秀

【摘要】論文基于遺傳學(xué)和免疫學(xué)的特點(diǎn)，提出了一種基于免疫遺傳算法AGV路徑規(guī)劃方法。算法采用實(shí)數(shù)編碼，且采用不定長(zhǎng)度，定義的適應(yīng)度函數(shù)具有明確的物理意義。所設(shè)計(jì)的路徑規(guī)劃方法具有遺傳算法具有的搜索空間大等優(yōu)點(diǎn)，也具有免疫算法對(duì)抗原的識(shí)別、學(xué)習(xí)、記憶和自動(dòng)調(diào)節(jié)能力，克服了遺傳算法易陷入局部最優(yōu)的缺陷，進(jìn)化速度也得到了提高。仿真結(jié)果證明該算法能較快地為AGV產(chǎn)生一條適應(yīng)所處環(huán)境的無(wú)碰撞的最優(yōu)路徑。

【關(guān)鍵詞】自動(dòng)導(dǎo)航小車(chē)；路徑規(guī)劃；免疫遺傳算法；疫苗

1、引言

目前，為使移動(dòng)機(jī)器人規(guī)劃出良好的去去路徑，所用的方法很多，如柵格法[1]、勢(shì)場(chǎng)法[2]、可視圖法[3]等。但各種方法有其使用局限。人工智能的發(fā)展為AGV的路徑規(guī)劃提供了新思路，產(chǎn)生了諸如神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)法、遺傳算法等方法。這些算法在一定程度上解決了AGV的路徑規(guī)劃問(wèn)題，但也有其缺陷。如神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)法對(duì)于復(fù)雜環(huán)境難以數(shù)學(xué)建模，范化能力差；模糊法靈活性差。遺傳算法在迭代過(guò)程中，個(gè)體在進(jìn)化過(guò)程中不可避免地會(huì)產(chǎn)生退化。受生物免疫系統(tǒng)的啟發(fā)，論文將免疫引入到遺傳算法中，在保留遺傳算法優(yōu)點(diǎn)的情況下，利用待求問(wèn)題的一些特征信息，采用免疫方法所具有的識(shí)別、記憶等功能來(lái)抑制遺傳算法在進(jìn)化中所出現(xiàn)的退化現(xiàn)象。本文所設(shè)計(jì)的基于免疫遺傳算法的AGV路徑規(guī)劃方法利用AGV在移動(dòng)過(guò)程中的特殊信息對(duì)所選路徑進(jìn)行優(yōu)化，可較快地使AGV根據(jù)環(huán)境信息搜索一種滿(mǎn)意的路徑，提高了AGV路徑規(guī)劃的智能性。

2、環(huán)境信息建模

對(duì)AGV進(jìn)行路徑規(guī)劃前，應(yīng)解決對(duì)其環(huán)境信息的描述即環(huán)境建模問(wèn)題。為此，作以下假設(shè)[3]：

（1）AGV在二維平面中運(yùn)動(dòng)，不考慮其高度方向的信息；（2）規(guī)劃環(huán)境的邊界及其內(nèi)所有障礙物（妨礙AGV運(yùn)動(dòng)的所有物體）用凸多邊形表示。（3）考慮到AGV的大小等，對(duì)環(huán)境邊界進(jìn)行縮小和對(duì)障礙物進(jìn)行擴(kuò)大時(shí)，其縮放量為AGV外形最大尺寸的一半。即AGV為“點(diǎn)機(jī)器人”。

至此，AGV的工作空間可描述為：工作平面和障礙物群{Oi|i=1，2…N}。具體到其個(gè)障礙物Oi，可描述為Oi={頂點(diǎn)1坐標(biāo)（xi1， yi1），….. 頂點(diǎn)n坐標(biāo)（xni， yni）}。為方便數(shù)據(jù)處理，對(duì)多邊形頂點(diǎn)沿順時(shí)針?lè)较蚓幪?hào)。起點(diǎn)為S，終點(diǎn)為E。工作平面可表示為矩形{（Xmin，Ymin），（Xmax，Ymax）}。

設(shè)在A(yíng)GV的工作環(huán)境中有n個(gè)已知的障礙物Oi（i=1，2，...，n），對(duì)應(yīng)的頂點(diǎn)數(shù)為Si，頂點(diǎn)坐標(biāo)為（x（i，j），y（i，j））（j=1，2，…Si）。為描述AGV工作環(huán)境中的障礙物，采用Dm×m矩陣對(duì)環(huán)境信息進(jìn)行描述，其中，m為障礙物頂點(diǎn)總數(shù)。定義d（i，j）為：

3、免疫遺傳算法設(shè)計(jì)

3.1路徑編碼方式

采用免疫遺傳算法求解最優(yōu)問(wèn)題的關(guān)鍵是對(duì)所求問(wèn)題的解進(jìn)行編碼。編碼的長(zhǎng)度與搜索空間的大小及求解精度有直接關(guān)系，也影響算法的效率。對(duì)AGV進(jìn)行路徑規(guī)劃時(shí)，傳統(tǒng)的二進(jìn)制或?qū)崝?shù)編碼方式都不適用。本文設(shè)計(jì)了一種自適應(yīng)變長(zhǎng)度實(shí)數(shù)數(shù)組編碼方式，即第p代Xp的第k條染色體Xkp的第j位基因Xkp（j）表示為Xkp（j）=|io，xk，yk|T，其中io為障礙物序號(hào)，（xk，yk|）為第io號(hào)障礙物的某頂點(diǎn)坐標(biāo)。由于路徑的起點(diǎn)為AGV的起始點(diǎn)，終點(diǎn)為其目標(biāo)點(diǎn)，在路徑規(guī)劃時(shí)可省去以縮短染色體的長(zhǎng)度。定義，AGV的可能運(yùn)動(dòng)路徑由數(shù)條直線(xiàn)段組成，相鄰兩直線(xiàn)段的交點(diǎn)稱(chēng)為AGV的路徑拐點(diǎn)。為使AGV不穿越障礙物運(yùn)動(dòng)，基于對(duì)工作規(guī)劃空間建模時(shí)所作的假設(shè)，AGV可沿多邊形障礙物的邊界線(xiàn)移動(dòng)，也可以障礙物的頂點(diǎn)為拐點(diǎn)在自由空間中移動(dòng)。染色體即AGV的某行路徑Xkp為Xkp={Xkp（1）， Xkp（2），…， Xkp（nkp）}，其中nkp為第p代中第k條染色體的長(zhǎng)度，每代中各條染色體長(zhǎng)度不同。

3.2適應(yīng)度函數(shù)

在對(duì)AGV進(jìn)行路徑規(guī)劃時(shí)，其優(yōu)化目標(biāo)為在所有可能的運(yùn)動(dòng)路徑Xp={Xkp|k=1， 2，…，N}中找出一條最優(yōu)或次優(yōu)路徑。設(shè)某個(gè)體Xkp的路徑長(zhǎng)度Dk為：

其中dj為Xk中各直線(xiàn)段軌跡長(zhǎng)。因?yàn)锳GV由一直線(xiàn)軌跡向另一直線(xiàn)軌跡過(guò)渡時(shí)運(yùn)動(dòng)速度的變化會(huì)影響其運(yùn)行時(shí)間，因此，在對(duì)所選路徑進(jìn)行評(píng)價(jià)時(shí)，除考慮其總長(zhǎng)度外，可要求路徑中的拐點(diǎn)數(shù)盡可能的少或AGV的姿態(tài)角變化量盡要能的小。本論文的路徑規(guī)劃目標(biāo)是路徑短且拐點(diǎn)較少。定義適應(yīng)度函數(shù)為：

式中，和為調(diào)整系數(shù)。這里取=0.8，=0.2。N為種群大小，Dj為種群中第j個(gè)體的路徑長(zhǎng)度，nj為第j個(gè)體路徑拐點(diǎn)數(shù)。

3.3算法的實(shí)現(xiàn)

在進(jìn)行路徑規(guī)劃時(shí)，首先判斷AGV從起點(diǎn)向終點(diǎn)沿直線(xiàn)軌跡運(yùn)動(dòng)時(shí)是否穿越障礙物。若無(wú)障礙物，兩點(diǎn)間的連線(xiàn)為AGV的最佳運(yùn)動(dòng)路徑，無(wú)須進(jìn)行路徑規(guī)劃。否則進(jìn)行路徑規(guī)劃。

免疫遺傳算法中，疫苗是根據(jù)待求問(wèn)題的先驗(yàn)知識(shí)構(gòu)造的最佳個(gè)體基因的估計(jì)，抗體是根據(jù)疫苗將某個(gè)體基因進(jìn)行修正后所得到的新個(gè)體。論文所設(shè)計(jì)的基于免疫遺傳算法的路徑規(guī)劃過(guò)程如下：

（1）根據(jù)問(wèn)題從記憶抗體庫(kù)中提取問(wèn)題的抗體P得到初始種群 ，不足N個(gè)時(shí)在A(yíng)GV起始點(diǎn)和目標(biāo)點(diǎn)之間隨機(jī)產(chǎn)生N-P條路徑。個(gè)體的產(chǎn)生方法是：以包圍AGV的起點(diǎn)、終點(diǎn)和所有在線(xiàn)障礙物的最小矩形為規(guī)劃區(qū)域，在規(guī)劃區(qū)域內(nèi)的障礙物頂點(diǎn)個(gè)數(shù)為M，在線(xiàn)障礙物為m，則染色體的最大長(zhǎng)度為M-m。以規(guī)劃區(qū)域內(nèi)的障礙物頂點(diǎn)為被選對(duì)象，沿一定的條件隨機(jī)選取基因位上的基因組成一條染色體，同用樣的方法產(chǎn)生其它染色體以組成群體。

（2）根據(jù)先驗(yàn)知識(shí)抽取疫苗H={h1， h2， …， hm}；

（3）計(jì)算第p代種群Ak所有個(gè)體的適應(yīng)度，并進(jìn)行終止進(jìn)化判斷。

（4）對(duì)當(dāng)前群體Xp進(jìn)行遺傳算子操作得到子代群體Bp。進(jìn)行交叉操作時(shí)，采用單點(diǎn)交叉。交叉操作時(shí)，兩個(gè)個(gè)體若有相同的基因（而非等位基因）進(jìn)行交叉操作。當(dāng)相同基因位不止一個(gè)，隨機(jī)選擇其一進(jìn)行交叉；當(dāng)無(wú)相同基因位則不進(jìn)行交叉。進(jìn)行變異操作時(shí)，從個(gè)體中隨機(jī)刪除一基因位或隨機(jī)選取一基因位插入一新基因位，或在個(gè)體中隨機(jī)選取一基因位用另一隨機(jī)產(chǎn)生的基因位交換。

（5）對(duì)子代Bp進(jìn)行免疫操作，得到新代Xp+1；接種疫苗和免疫選擇是免疫算法的主要操作，接種疫苗是為了提高個(gè)體的適應(yīng)度，免疫選擇是為了防止個(gè)體的退化。接種疫苗即從Bp中按比例K隨機(jī)抽取Nk=KN個(gè)個(gè)體Bip（i=1，2，…，Nk），并按先驗(yàn)知識(shí)修改Bip（這時(shí)就變?yōu)榭贵w），使其以較大的概率具有更高的適應(yīng)度。接種疫苗時(shí)，若Bip已經(jīng)是最佳個(gè)體，則其以概率1轉(zhuǎn)移為Bip。對(duì)路徑規(guī)劃，接種疫苗就是對(duì)所選個(gè)體進(jìn)行判斷：首先，相鄰兩點(diǎn)間能否使AGV無(wú)障礙的沿直線(xiàn)運(yùn)動(dòng)；其次，任意兩點(diǎn)間能否使AGV無(wú)障礙的沿直線(xiàn)運(yùn)動(dòng)？條件滿(mǎn)足，則刪除中間點(diǎn)。免疫選擇分兩步完成：免疫檢測(cè)和退火選擇。免疫檢測(cè)即對(duì)抗體進(jìn)行檢測(cè)，若出現(xiàn)適應(yīng)度下降，此時(shí)由父代個(gè)體代替其參加競(jìng)選，退火選擇即以概率P（Bip）在當(dāng)前子代中進(jìn)行選擇：

其中，為適應(yīng)度函數(shù)；Tk是單調(diào)遞減趨于0的退火溫度控制序列，Tk=ln（T0/k+1），T0=100，p是進(jìn)化代數(shù)[3]。

（6）選擇個(gè)體進(jìn)入新的群體。更新抗體庫(kù)，并轉(zhuǎn)到第（3）步。

4、仿真實(shí)驗(yàn)

仿真是在Matlab6.1上進(jìn)行的。AGV的工作環(huán)境大小為8×6m2，其內(nèi)有6個(gè)形狀各異、排列任意的障礙物（如圖2所示），現(xiàn)欲使AGV從S點(diǎn)無(wú)碰撞地運(yùn)動(dòng)到E點(diǎn)且使其運(yùn)動(dòng)路徑最短，建立如圖4所示的可視圖。其可視矩陣如左圖：

論文采用所設(shè)計(jì)的路徑規(guī)劃方法和現(xiàn)有的遺傳和免疫算法對(duì)AGV進(jìn)行路徑規(guī)劃以尋找最佳路徑。取遺傳操作中的交叉概率Pc=0.8，變異概率Pm=0.2，免疫操作中的接種疫苗概率Pv=0.6，初始種群大小為N=20，抗體庫(kù)M=5，遺傳代數(shù)不超過(guò)K=200。圖3為路徑規(guī)劃的最佳路徑。進(jìn)化過(guò)程中適應(yīng)度變化和路徑長(zhǎng)度變化如圖4所示。

由仿真結(jié)果知，采用免疫遺傳算法進(jìn)行路徑規(guī)劃時(shí)，退化現(xiàn)象基本不會(huì)發(fā)生，再能很快得到問(wèn)題的最優(yōu)解。其原因是，利用免疫遺傳算法對(duì)AGV進(jìn)行路徑規(guī)劃，一方面利用了遺傳算法的優(yōu)點(diǎn)，由于是對(duì)編碼進(jìn)行操作，對(duì)問(wèn)題的依賴(lài)性小，且操作是并行進(jìn)行，優(yōu)化速度快；同時(shí)針對(duì)遺傳算在進(jìn)行交叉和變異操作時(shí)是以以概率方式隨機(jī)地、缺泛指導(dǎo)性地進(jìn)行導(dǎo)致問(wèn)題進(jìn)化時(shí)產(chǎn)生退化的現(xiàn)象，采用適當(dāng)?shù)闹笇?dǎo)，彌補(bǔ)了遺傳算法的缺點(diǎn)。利用遺傳免疫算法進(jìn)行優(yōu)化，在保證算法收斂的前提下，有效地提高計(jì)算速度。利用此法對(duì)AGV的路徑進(jìn)行規(guī)劃，比其它的方法更有效。

5、結(jié)論

論文主要針對(duì)環(huán)境建模和路徑搜索兩大問(wèn)題進(jìn)行了研究。基于可視圖環(huán)境建模方法優(yōu)點(diǎn)，完成了對(duì)環(huán)境信息的建模。并結(jié)合遺傳和免疫算法的優(yōu)點(diǎn)設(shè)計(jì)了具有精英保留策略的基于免疫遺傳算法的AGV路徑規(guī)劃方法。通過(guò)比較采用遺傳算法、免疫算法和本論文所設(shè)計(jì)的免疫遺傳算法對(duì)AGV進(jìn)行路徑規(guī)劃結(jié)果和效率的比較，分析了所提出的基于免疫遺傳算法的AGV路徑規(guī)劃方法的優(yōu)點(diǎn)。仿真結(jié)果表明：

A.本論文采用改進(jìn)的可視圖法對(duì)環(huán)境信息進(jìn)行建模，在改變障礙物位置、形狀、大小和AGV的起點(diǎn)及終點(diǎn)的情況下，均可快速構(gòu)建AGV的環(huán)境信息模型。

B.采用本論文所設(shè)計(jì)的基于免疫遺傳算法的AGV路徑規(guī)劃方法對(duì)AGV進(jìn)行路徑規(guī)劃，在速度方面優(yōu)于傳統(tǒng)的免疫算法和遺傳算法，且系統(tǒng)退化現(xiàn)象基本得到消除。

參考文獻(xiàn)

[1]吳鋒，楊宜民.一種基于柵格模型的機(jī)器人路徑規(guī)劃算法[J].現(xiàn)代計(jì)算機(jī)（專(zhuān)業(yè)版），2012，4（3），7-9，13.

[2]沈鳳梅，吳隆.基于改進(jìn)人工勢(shì)場(chǎng)法的移動(dòng)機(jī)器人自主導(dǎo)航和避障研究[J].制造業(yè)自動(dòng)化，2013，35 （12），28-30，39.

[3]李善壽，方潛生，肖本賢.全局路徑規(guī)劃中基于改進(jìn)可視圖法的環(huán)境建模[J].華東交通大學(xué)學(xué)報(bào)，2008，25（6），73-77.

作者簡(jiǎn)介

井治財(cái)（1968），男，諾伯特智能裝備（漢中）有限公司，陜西省漢中市，郵編：723000。主要從事機(jī)床結(jié)構(gòu)設(shè)計(jì)與誤差檢測(cè)。

史恩秀（1966），女，西安理工大學(xué)機(jī)械與精密儀器工程學(xué)院，副教授，陜西省西安市，郵編：710048。