免疫算法在移動(dòng)機(jī)器人路徑規(guī)劃中的應(yīng)用*

趙 娜

(太原師范學(xué)院，山西太原030012)

移動(dòng)機(jī)器人是自動(dòng)化與機(jī)器人領(lǐng)域最有前景的研究方向之一。它是小車(chē)機(jī)械、機(jī)器人學(xué)、機(jī)電一體化、精密儀器、軌跡規(guī)劃、多智能協(xié)調(diào)等理論、技術(shù)的融合體，它對(duì)于研發(fā)多智能體系統(tǒng)具有重要的研究模型意義。

與移動(dòng)機(jī)器人相關(guān)的研究?jī)?nèi)容有:運(yùn)動(dòng)控制、多智能體合作、軟硬件平臺(tái)與路徑規(guī)劃。其中，對(duì)移動(dòng)機(jī)器人的性能影響比較大的是路徑規(guī)劃算法的性能，它為頂層決策與底層控制提供了銜接功能。移動(dòng)機(jī)器人路徑規(guī)劃問(wèn)題可以這樣來(lái)描述:確定目標(biāo)點(diǎn)和出發(fā)點(diǎn)，處于具有有障礙物(固定或移動(dòng))的環(huán)境中，為移動(dòng)機(jī)器人在滿(mǎn)足一定的最優(yōu)規(guī)則的情況下規(guī)劃一條無(wú)碰的路徑，使得移動(dòng)機(jī)器人遵照規(guī)劃的路徑運(yùn)動(dòng)并到達(dá)目標(biāo)點(diǎn)。最優(yōu)規(guī)則包括最短的路徑長(zhǎng)度、最小的消耗能量和最短運(yùn)行時(shí)間等。目前路徑規(guī)劃有許多方法，如勢(shì)場(chǎng)法［1］、動(dòng)態(tài)意圖預(yù)測(cè)法［2］，在文獻(xiàn)［3］中提出了基于遺傳算法的路徑規(guī)劃方法。

信息處理系統(tǒng)模仿生物免疫系統(tǒng)，為找到新的更優(yōu)的智能控制算法提供比較有力的啟發(fā)。生物免疫系統(tǒng)是一個(gè)基本防御系統(tǒng)，它的作用是抵抗細(xì)菌、病毒和其它致病因子入侵。免疫系統(tǒng)是一個(gè)復(fù)雜系統(tǒng)，其由器官、細(xì)胞和分子組成。與神經(jīng)系統(tǒng)相同，它是一個(gè)機(jī)體能特異地識(shí)別“自己/非己”的刺激、精確應(yīng)答、保留記憶的功能系統(tǒng)。同時(shí)，免疫系統(tǒng)利用一套復(fù)雜的機(jī)制使基因重組，使產(chǎn)生的抗體能夠有效地識(shí)別入侵的抗原，并消滅抗原。在這個(gè)過(guò)程中，通過(guò)體細(xì)胞理論和網(wǎng)絡(luò)理論可得出抗體具有模式識(shí)別、免疫記憶與學(xué)習(xí)、多樣性的產(chǎn)生、噪聲耐受、歸納概括、分步檢測(cè)、自我抑制調(diào)節(jié)的功能［4］。

自然免疫系統(tǒng)為人工智能方法提供了靈感。人工免疫算法是一種在生物界中得到啟示，以自然免疫系統(tǒng)為機(jī)理，將其中的有利用價(jià)值的原理應(yīng)用到人工智能中的一種算法。受這樣的啟發(fā)，已經(jīng)有很多種人工免疫算法提出，它們利用自然免疫系統(tǒng)的原理實(shí)現(xiàn)了類(lèi)似于免疫系統(tǒng)的識(shí)別抗原、分化細(xì)胞、記憶以及自調(diào)節(jié)的良好功能;免疫行為較好地使多樣性得到保持，從而有效地預(yù)防了“早熟”現(xiàn)象。

在目前人工免疫系統(tǒng)的基礎(chǔ)上，本文將其中一種人工免疫算法用于移動(dòng)機(jī)器人路徑規(guī)劃中。對(duì)移動(dòng)機(jī)器人基本控制方式進(jìn)行了簡(jiǎn)要說(shuō)明，然后求得算法中需要的函數(shù)，并詳細(xì)說(shuō)明了人工免疫算法在路徑規(guī)劃中的實(shí)施過(guò)程，仿真結(jié)果充分說(shuō)明了該算法的可行性和有效性。

1 移動(dòng)機(jī)器人運(yùn)動(dòng)路徑的選取與親和力函數(shù)構(gòu)建

1.1 路徑抗體編碼的產(chǎn)生

編碼對(duì)于機(jī)器人路徑規(guī)劃是非常重要的，由于本文使用人工免疫算法求解最優(yōu)路徑，所以對(duì)路徑進(jìn)行如圖1所示的抗體編碼。

圖1 路徑點(diǎn)選取示意圖

起點(diǎn)與終點(diǎn)構(gòu)成線(xiàn)段SG，長(zhǎng)度為DIST，并確定一個(gè)路徑有效搜索區(qū)域，一般為正方形;將SG進(jìn)行n等分，通過(guò)每個(gè)等分點(diǎn)做SG的垂線(xiàn)段，依次在每一條垂線(xiàn)段上任意取一點(diǎn)Aji，按順序依次連接這些點(diǎn)，則構(gòu)成一條路徑Lj;同理，可以得到m條路徑。表示如下:

其中，j=1，2，3，…，m;i=0，1，2，…，n;Aji為第 j條路徑的第i條垂線(xiàn)段上的點(diǎn);Aj0取為起點(diǎn)，Ajn取為終點(diǎn)。

由于等分的特點(diǎn)，把路徑點(diǎn)轉(zhuǎn)化為直角坐標(biāo)形式的一維編碼，則有:

其中，yji為點(diǎn)Aji在直角坐標(biāo)中的縱坐標(biāo)，并且規(guī)定起點(diǎn)與終點(diǎn)坐標(biāo)固定。

1.2 親合力函數(shù)的構(gòu)建［3］

親和力函數(shù)的選取將直接影響到免疫算法收斂速度的快慢和最終的結(jié)果。在移動(dòng)機(jī)器人的路徑規(guī)劃中，親和力函數(shù)應(yīng)該滿(mǎn)足兩個(gè)現(xiàn)實(shí)條件，即路徑最短并且能夠有效避開(kāi)障礙物。為此，文中將親和力函數(shù)分為兩部分。

路徑距離的親和力函數(shù)可以由以下公式確定

其中(xji，yji)是第j條路徑第i點(diǎn)的坐標(biāo)。

假設(shè)在路徑搜索區(qū)域內(nèi)有q個(gè)障礙物，每個(gè)障礙物的大小表示為圓心為xk，yk，半徑為r的圓，則路徑點(diǎn)到障礙物的安全距離為r。則對(duì)于路徑點(diǎn)Aji避開(kāi)障礙物的程度為:

其中，k=1，2，…，q。

這樣可以得出路徑避開(kāi)障礙物的親和力函數(shù):

綜合以上結(jié)論，得到總體親和力函數(shù)的計(jì)算公式:

其中，α，β為加權(quán)系數(shù)，調(diào)節(jié)加權(quán)系數(shù)可以改變親和力函數(shù)中距離與避障所占的比例。

親和力函數(shù)將實(shí)際約束條件有機(jī)地結(jié)合起來(lái)，計(jì)算比較簡(jiǎn)單。人工免疫算法的最終目標(biāo)是選擇親和力高的抗體作為最優(yōu)解的，在每一步操作中都以親和力高作為優(yōu)勝抗體的主要標(biāo)準(zhǔn)。

2 人工免疫算法在路徑規(guī)劃中的實(shí)現(xiàn)

文中將免疫系統(tǒng)中的優(yōu)化機(jī)理概括為:選擇、克隆擴(kuò)增、受體編輯、骨髓產(chǎn)生新細(xì)胞。其中克隆擴(kuò)增和受體編輯分別用來(lái)進(jìn)行局部和全局搜索，骨髓產(chǎn)生新B細(xì)胞以增加群體的多樣性。免疫進(jìn)化算法的具體操作和步驟分為:選擇、擴(kuò)展、突變和替換［5］。

算法在路徑規(guī)劃中的具體實(shí)現(xiàn)包括以下具體操作:

(1)選擇操作

隨機(jī)產(chǎn)生n個(gè)實(shí)數(shù)編碼的路徑抗體作為初始群體A，編碼采用 Lj={0，yi1，yi2，…，yji，…，yjn－1，0}的形式，并且按照公式fj=α/ftj1+β·ftj2計(jì)算其中每個(gè)路徑抗體的親和力。選出其中m個(gè)親和力最高的個(gè)體組成群體B(其中m＜n)。

(2)擴(kuò)展操作

模擬免疫系統(tǒng)的克隆擴(kuò)增過(guò)程，構(gòu)造一個(gè)小鄰域，群體B中每個(gè)路徑抗體在其小鄰域內(nèi)隨機(jī)產(chǎn)生若干新路徑抗體，m個(gè)路徑抗體產(chǎn)生n個(gè)新路徑抗體組成群體C。群體B中任意一個(gè)路徑抗體Li的小鄰域SN(vi)構(gòu)造為:

其中Ω為可行解空間，‖·‖為歐幾里德范數(shù)。SN(Li)是由與Li的歐氏距離不大于常數(shù)r的所有可行解構(gòu)成，在解空間中是以L(fǎng)i為中心，以r為半徑的球形區(qū)域。

B細(xì)胞的親和力越高，其克隆擴(kuò)增生成的子細(xì)胞就越多，因此用正比選擇法實(shí)現(xiàn)親和力越高的路徑抗體擴(kuò)展出越多的新路徑抗體。設(shè)群體B中的路徑抗體為L(zhǎng)1，L2，…，Lm，親和力值分別為f1，f2，…，fm，則每個(gè)路徑抗體擴(kuò)展新路徑抗體的概率為:

(3)突變操作

構(gòu)造一個(gè)較大鄰域，群體C中親和力最低的n－m個(gè)路徑抗體中的每個(gè)抗體突變?yōu)槠浯筻徲騼?nèi)的任一個(gè)抗體。突變后的路徑抗體與群體C中未突變的路徑抗體一起組成群體D。設(shè)路徑抗體Lj進(jìn)行突變操作，其大鄰域構(gòu)造為:

MN(Lj)在解空間中是以L(fǎng)j為中心，以R為半徑的球形區(qū)域。群體C中親和力最低的n－m個(gè)路徑抗體一定不會(huì)被選入下一代，對(duì)其進(jìn)行突變操作，相當(dāng)于在解空間的全局范圍內(nèi)進(jìn)行大鄰域搜索。

(4)替換操作

群體D中親和力最低的J個(gè)路徑抗體替換為隨機(jī)路徑抗體形成群體E。替換操作模擬骨髓產(chǎn)生新B細(xì)胞過(guò)程以增加群體多樣性。

為了避免當(dāng)前群體中最優(yōu)抗體被擴(kuò)展操作破壞掉以及保證算法收斂，算法采取最優(yōu)個(gè)體保留策略。實(shí)現(xiàn)步驟如下:

(1)隨機(jī)產(chǎn)生初始群體A0，令k=0;

(2)重復(fù)以下步驟，直到滿(mǎn)足收斂準(zhǔn)則。

a.計(jì)算當(dāng)前群體Ak中的每個(gè)路徑抗體的親和力;

b.對(duì)群體Ak進(jìn)行選擇操作得到群體Bk;

c.對(duì)群體Bk進(jìn)行擴(kuò)展操作得到群體Ck;

d.對(duì)群體Ck進(jìn)行突變操作得到群體Dk;

e.對(duì)群體Dk進(jìn)行替換操作得到群體Ek;

f.群體Ek中評(píng)價(jià)值最低的路徑抗體替換為Ak中親和力最高的抗體，形成下一代群體Ak+1，令k=k+1。

(3)輸出結(jié)果

在本文中，采用了限定迭代次數(shù)作為終止條件。

3 實(shí)驗(yàn)結(jié)果與結(jié)論

在移動(dòng)機(jī)器人仿真軟件RobotSoccer1.5a中進(jìn)行靜態(tài)環(huán)境仿真試驗(yàn)，設(shè)置算法的參數(shù)m=20、n=10、J=1，迭代次數(shù)為200代，圖2和圖3分別是算法中有無(wú)突變操作時(shí)的路徑規(guī)劃仿真結(jié)果。

從仿真結(jié)果可以看到，算法中的突變操作大范圍的產(chǎn)生了新路徑抗體，這樣有利于算法在全局范圍內(nèi)進(jìn)行尋優(yōu)。同時(shí)，全局競(jìng)爭(zhēng)可以粗略地搜索到抗體親和力高的區(qū)域，而擴(kuò)展操作隨后可以進(jìn)行細(xì)致地搜索并得到高精度的抗體解，這樣可以有效避免算法過(guò)早收斂于局部值的“早熟”現(xiàn)象。

圖2 不存在突變操作時(shí)的仿真圖

圖3 存在突變操作時(shí)的仿真圖

實(shí)驗(yàn)仿真結(jié)果表明，把人工免疫算法用于移動(dòng)機(jī)器人的路徑規(guī)劃中是有效和可行的，在實(shí)際應(yīng)用時(shí)，要進(jìn)一步深入考慮實(shí)時(shí)性和動(dòng)態(tài)性，合理選擇群體規(guī)模和迭代次數(shù)，注意改變親和力函數(shù)以滿(mǎn)足系統(tǒng)動(dòng)態(tài)性能要求，從而達(dá)到路徑規(guī)劃的要求。

［1］鐘碧良，張祺，楊宜民.基于改進(jìn)勢(shì)場(chǎng)法的移動(dòng)機(jī)器人避障路徑規(guī)劃［J］.控制理論與應(yīng)用，2003，20(4):623－626.

［2］唐平，李夏，楊宜民.移動(dòng)機(jī)器人進(jìn)行障礙物動(dòng)態(tài)意圖預(yù)測(cè)的研究［J］.控制理論與應(yīng)用，2002，19(4):604－606.

［3］吳麗娟，徐心和.基于遺傳算法的移動(dòng)機(jī)器人比賽中障礙回避策略的設(shè)計(jì)［J］.機(jī)器人，2001，23(2):142－145.

［4］莫宏偉.人工免疫系統(tǒng)原理與應(yīng)用［M］.哈爾濱:哈爾濱工業(yè)大學(xué)出版社，2002.

［5］左興權(quán)，李士勇，黃金杰.一種新的免疫進(jìn)化算法及其性能分析［J］.系統(tǒng)仿真學(xué)報(bào)，2003，15(11):1607－1609.