趙 娜
(太原師范學(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ō)明了該算法的可行性和有效性。
編碼對(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)固定。
親和力函數(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)。
文中將免疫系統(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ù)作為終止條件。
在移動(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.