基于勢(shì)場(chǎng)導(dǎo)向權(quán)的改進(jìn)機(jī)器人路徑規(guī)劃免疫算法

王孫安，吳燦陽

（西安交通大學(xué)機(jī)械工程學(xué)院，西安710049）

1 前言

路徑規(guī)劃技術(shù)是機(jī)器人自主導(dǎo)航的關(guān)鍵支撐技術(shù)之一，是指在具有障礙物的環(huán)境內(nèi)按照一定的評(píng)價(jià)標(biāo)準(zhǔn)，如最小工作代價(jià)、最短路徑等，從起始位置到達(dá)目標(biāo)位置搜索一條無碰路徑[1]。近年來，隨著人工智能的發(fā)展，模糊邏輯[2]、遺傳算法[3]、蟻群算法[4]等方法在路徑規(guī)劃中的應(yīng)用取得了很大的進(jìn)展，顯示出較好的魯棒性和全局優(yōu)化能力。但模糊邏輯存在經(jīng)驗(yàn)不完備性；遺傳算法編碼復(fù)雜、效率低；蟻群算法的路徑發(fā)現(xiàn)能力受限于柵格大小的劃分[5]。從路徑規(guī)劃發(fā)展來看，仿生智能算法是主要應(yīng)用趨勢(shì)。

由生物免疫系統(tǒng)啟發(fā)而來的人工免疫系統(tǒng)，因其自組織、自學(xué)習(xí)和免疫記憶等優(yōu)點(diǎn)為解決工程問題尤其是機(jī)器人技術(shù)提供了新契機(jī)[6]。20世紀(jì)80年代，F(xiàn)armer等人基于免疫網(wǎng)絡(luò)學(xué)說給出了免疫系統(tǒng)的動(dòng)態(tài)模型[7]?；谠搫?dòng)態(tài)模型，1996年日本學(xué)者Ishiguro等[8]率先提出了一種行為仲裁系統(tǒng)，并在垃圾自動(dòng)回收上得到評(píng)估。Meshref等[9]實(shí)現(xiàn)了分布式自主機(jī)器人系統(tǒng)中的狗羊放牧問題。Farmer模型體現(xiàn)了較好的魯棒性和柔韌性，但是缺乏全局優(yōu)化能力。基于生物免疫網(wǎng)絡(luò)理論，文獻(xiàn)[10]設(shè)計(jì)了一種新的機(jī)器人路徑規(guī)劃算法。該算法通過學(xué)習(xí)獲取規(guī)則和清晰規(guī)則，具有很強(qiáng)的空間搜索能力和規(guī)則發(fā)現(xiàn)與再學(xué)習(xí)能力，但在搜索精度和路徑收斂性能方面還有待進(jìn)一步提高。為了更好地解決復(fù)雜環(huán)境中的移動(dòng)機(jī)器人路徑規(guī)劃問題，本文提出了一種改進(jìn)的基于勢(shì)場(chǎng)導(dǎo)向權(quán)的人工免疫網(wǎng)絡(luò)路徑規(guī)劃算法。

2 人工免疫網(wǎng)絡(luò)規(guī)劃模型及其定義

2.1 生物免疫系統(tǒng)

生物免疫系統(tǒng)是高等脊椎動(dòng)物體內(nèi)能夠識(shí)別和排除抗原性異物、保護(hù)機(jī)體內(nèi)免受損害及維持體內(nèi)環(huán)境穩(wěn)定的極為復(fù)雜的生物學(xué)系統(tǒng)。生物免疫學(xué)發(fā)展至今已經(jīng)取得了不少研究成果，但人類對(duì)自然免疫系統(tǒng)的認(rèn)識(shí)還不是十分充分。目前被普遍接受的理論主要有克隆選擇和獨(dú)特型網(wǎng)絡(luò)。后者是1973年由丹麥學(xué)者Jerne在克隆選擇的基礎(chǔ)上提出[11]，其原理如圖1所示。由圖1可看出，免疫系統(tǒng)是由淋巴系統(tǒng)網(wǎng)絡(luò)所組成，淋巴細(xì)胞之間通過通訊來完成免疫系統(tǒng)任務(wù)?？贵wAb1的獨(dú)特位Id1通過Ab2的側(cè)位P2刺激B細(xì)胞2，而從抗體2的角度看，Ab1的Id1相當(dāng)于抗原，因此與抗體Ab1相關(guān)的B細(xì)胞將受到Ab2抑制。而Ab3的Id3相對(duì)于Ab1而言又是抗原，Ab1又將受到Ab3刺激。整個(gè)網(wǎng)絡(luò)成員通過相互刺激與抑制構(gòu)成一個(gè)閉環(huán)鏈，具有識(shí)別自身和非自身的分辨能力。

圖1 獨(dú)特型網(wǎng)絡(luò)模型Fig.1 Jerne’s idiotypic networks

2.2 人工免疫網(wǎng)絡(luò)路徑規(guī)劃模型

為了實(shí)現(xiàn)移動(dòng)機(jī)器人的免疫路徑規(guī)劃，本文將移動(dòng)機(jī)器人所處環(huán)境作為抗原，抗原的表位是包含障礙物和目標(biāo)信息的環(huán)境信息。將機(jī)器人的移動(dòng)行為作為抗體，抗體的獨(dú)特位同樣是環(huán)境信息，對(duì)位是機(jī)器人運(yùn)動(dòng)命令?？乖涂贵w匹配稱為刺激，不匹配稱為抑制，主要通過抗原抗體的親和度來衡量。

借鑒Jerne的獨(dú)特型免疫網(wǎng)絡(luò)模型，本文構(gòu)建如圖2所示的人工免疫網(wǎng)絡(luò)規(guī)劃模型（各抗體下方用不同形狀表示其獨(dú)特位和對(duì)位）。不失一般性，本文將路徑規(guī)劃問題研究限制于室內(nèi)平面環(huán)境中。對(duì)應(yīng)的免疫智能體是如圖3所示的一個(gè)虛擬全方位平面移動(dòng)機(jī)器人。機(jī)器人四周配備8個(gè)虛擬傳感器，檢測(cè)方向?yàn)?～8，檢測(cè)距離分近、中、遠(yuǎn)。機(jī)器人可以按8個(gè)命令C＝{a，b，c，d，e，f，g，h}運(yùn)動(dòng)，分別代表{前進(jìn)、左前進(jìn)、右前進(jìn)、左平移、右平移、左后退、右后退、后退}，當(dāng)機(jī)器人到達(dá)目的地時(shí)采用停止命令。機(jī)器人從起點(diǎn)S出發(fā)，根據(jù)抗原抗體的匹配進(jìn)行空間搜索直至終點(diǎn)G[12]。因此從起點(diǎn)到終點(diǎn)將形成一個(gè)人工免疫網(wǎng)絡(luò)，抗體的連接取決于機(jī)器人所在環(huán)境以及運(yùn)動(dòng)命令清晰度。路徑規(guī)劃的實(shí)質(zhì)就是要找到由抗體構(gòu)成的一個(gè)內(nèi)圖，該內(nèi)圖所描述的機(jī)器人運(yùn)動(dòng)軌跡是最優(yōu)的。

2.3 基本定義

為了便于人工免疫網(wǎng)絡(luò)規(guī)劃算法的描述，首先給出如下基本定義[5]。

圖2 人工免疫網(wǎng)絡(luò)規(guī)劃模型Fig.2 Planning model of artificial immune

圖3 免疫智能體Fig.3 Immune agent

定義1：抗原（Ag）代表機(jī)器人所處室內(nèi)平面環(huán)境。

定義2：抗體（Ab）代表機(jī)器人針對(duì)環(huán)境信息產(chǎn)生的對(duì)應(yīng)行為。

式（2）中，IAbO為障礙物信息，IAbO=AbOi，?i∈IAbG為目標(biāo)信息，，集合元素定義同抗原；Com為運(yùn)動(dòng)命令，Com=C。

定義3：用抗原抗體的親和度ζ來描述抗原抗體的匹配程度。

由圖3看出，機(jī)器人前方障礙信息比后方的貢獻(xiàn)大，而正前方的障礙物信息貢獻(xiàn)最大，正后方的貢獻(xiàn)最小，機(jī)器人左側(cè)和右側(cè)的貢獻(xiàn)對(duì)稱相等。為了體現(xiàn)環(huán)境編碼中不同位置在抗原抗體親和度中的不同貢獻(xiàn)，本文親和度定義如下

式（3）中，A_Gi為i方向抗原和抗體的目標(biāo)信息的邏輯運(yùn)算值，即A_Gi=（AgGi⊕AbGi）；A_Oi為i方向抗原和抗體的障礙物信息的邏輯運(yùn)算值，即A_Oi=（AgOi1⊕AbOi1）+（AgOi2⊕AbOi2）；mi為障礙物信息貢獻(xiàn)權(quán)值。根據(jù)實(shí)驗(yàn)，本文分別取{2、0.5、0.5、0.15、0.15、0.1、0.1、0.01}。

3 人工勢(shì)場(chǎng)法及其導(dǎo)向權(quán)

在基于人工免疫網(wǎng)絡(luò)的路徑規(guī)劃算法中，抗體在抗體網(wǎng)絡(luò)中的轉(zhuǎn)移效率直接影響到算法的搜索性能。文獻(xiàn)[10]按照抗體生命力進(jìn)行轉(zhuǎn)移概率的設(shè)計(jì)，但搜索能力和網(wǎng)絡(luò)收斂性能較差。為了提高抗體的轉(zhuǎn)移效率，文獻(xiàn)[5]融合蟻群算法，將命令清晰度和抗體轉(zhuǎn)移后的距離變化作為變量設(shè)計(jì)了轉(zhuǎn)移概率。文獻(xiàn)[12]將勢(shì)場(chǎng)法的規(guī)劃結(jié)果作為先驗(yàn)知識(shí)，對(duì)文獻(xiàn)[5]中的命令清晰度進(jìn)行優(yōu)化，進(jìn)一步提高了抗體的轉(zhuǎn)移效率。為了更有效地利用勢(shì)場(chǎng)法并提高抗體的轉(zhuǎn)移效率，本文將人工勢(shì)場(chǎng)法的規(guī)劃結(jié)果作為導(dǎo)向權(quán)，構(gòu)建了新的抗體轉(zhuǎn)移算子，從而優(yōu)化人工免疫網(wǎng)絡(luò)的路徑規(guī)劃算法。

人工勢(shì)場(chǎng)法是由Khatib于1986年提出來的，其基本思想是：在目標(biāo)位置構(gòu)造引力勢(shì)場(chǎng)Uatt和在障礙物周圍構(gòu)造斥力勢(shì)場(chǎng)Urep，機(jī)器人在Uatt的引力Fatt和Urep的斥力Frep共同作用下向目標(biāo)運(yùn)動(dòng)。

設(shè)X、Xobs、Xgoal分別為機(jī)器人、障礙物和目標(biāo)的位置向量。引力勢(shì)場(chǎng)通常定義為（4）

式（4）中，‖X-Xgoal‖為歐氏距離；ξ為引力場(chǎng)正比例系數(shù)；m為引力勢(shì)場(chǎng)系數(shù)（m取值不同，引力勢(shì)場(chǎng)形狀也不同，通常m取2）。

引力通常取引力勢(shì)場(chǎng)的負(fù)梯度當(dāng)m=2時(shí)，F(xiàn)att=ξ‖Xgoal-X‖斥力勢(shì)場(chǎng)通常定義為式（6）中，η為斥力場(chǎng)正比例系數(shù)；ρ0為障礙物影響距離 ；n為 正 常 數(shù) ；ρ(X，Xobs)=‖X-Xobs‖ ；ρ(X,Xgoal)=‖X-Xgoal‖。

斥力同樣定義為斥力勢(shì)場(chǎng)的負(fù)梯度

根據(jù)人工勢(shì)場(chǎng)法的原理，機(jī)器人的避障角度為

設(shè)某抗體運(yùn)動(dòng)命令方向與x軸的夾角為θx，則定義該抗體運(yùn)動(dòng)命令的人工勢(shì)場(chǎng)導(dǎo)向權(quán)為

式（9）中，κ為調(diào)整系數(shù)。

由式（9）可看出，當(dāng)抗體命令執(zhí)行方向與機(jī)器人的避障方向越接近，導(dǎo)向權(quán)越大。

4 基于勢(shì)場(chǎng)導(dǎo)向權(quán)的免疫網(wǎng)絡(luò)路徑規(guī)劃算法

4.1 主要算子

1）抗體轉(zhuǎn)移算子。為了提高抗體的選擇效率，本文將抗體命令清晰度、抗體轉(zhuǎn)移的距離變化和勢(shì)場(chǎng)導(dǎo)向權(quán)作為變量，構(gòu)建如下的抗體轉(zhuǎn)移概率

式（10）中，τi（t）為抗體第i號(hào)運(yùn)動(dòng)命令的清晰度；α為抗體命令清晰度啟發(fā)因子；σi（t）為抗體第i號(hào)運(yùn)動(dòng)命令的導(dǎo)向權(quán)；β為勢(shì)場(chǎng)導(dǎo)向權(quán)啟發(fā)因子；qi（t）為抗體第i號(hào)命令的目標(biāo)啟發(fā)函數(shù)；γ為目標(biāo)啟發(fā)因子。

qi（t）的表達(dá)式如下

式（11）中，Δd為機(jī)器人執(zhí)行8個(gè)命令后與目標(biāo)點(diǎn)的距離變化結(jié)果集合；l為調(diào)整系數(shù)，且l>0。

匹配抗體命令的選擇主要通過輪盤賭算法，這既保證了命令選擇的合理性，又保證了特殊小概率事件發(fā)生的可能性，實(shí)現(xiàn)了對(duì)抗體命令集遍歷選擇的可能。

2）抗體命令清晰度學(xué)習(xí)算子?？贵w在轉(zhuǎn)移過程中，往往會(huì)產(chǎn)生碰撞或因陷入局部極小而造成的徘徊。為了解決抗體轉(zhuǎn)移過程中存在的上述問題，本文采用式（12）的抗體命令清晰度學(xué)習(xí)策略。

式（12）中，n為當(dāng)前所處位置在抗體鏈中的層數(shù)；Nn為抗體鏈總層數(shù)；χ為學(xué)習(xí)可變系數(shù)，且χ<1；ε為學(xué)習(xí)定系數(shù)，且ε>0。

抗體命令清晰度學(xué)習(xí)的目的是減小造成碰撞和徘徊的抗體運(yùn)動(dòng)命令的參與機(jī)會(huì)，增加其他抗體運(yùn)動(dòng)命令的參與機(jī)會(huì)。

3）抗體命令清晰度更新算子。當(dāng)完成抗體網(wǎng)絡(luò)的一次搜索后，需對(duì)所選擇的相應(yīng)運(yùn)動(dòng)命令予以激勵(lì)，使其清晰度得到提高。當(dāng)下次任務(wù)遇到同樣抗原時(shí)，該命令被選擇的概率將會(huì)增大，從而形成一個(gè)正反饋機(jī)制。另外，為了保證抗體庫的動(dòng)態(tài)特性，所有抗體運(yùn)動(dòng)命令的清晰度又將按照一定的遺忘率消逝。這樣，隨著規(guī)劃的不斷進(jìn)行，不用的或不合理的抗體運(yùn)動(dòng)命令將逐漸死去，可行且較優(yōu)的抗體命令將被保存下來，從而進(jìn)一步提高了免疫網(wǎng)絡(luò)規(guī)劃算法的搜索速度。在本文中，抗體命令清晰度更新算子定義如下

式（13）中，ρ為抗體命令清晰度遺忘率；μ為常數(shù)；L為規(guī)劃的路徑長(zhǎng)度。

由式（13）可看出，免疫規(guī)劃路徑越短，說明抗體網(wǎng)絡(luò)中的抗體執(zhí)行命令越正確，相應(yīng)抗體命令獲得的激勵(lì)程度越大，其清晰度也就變得更高。

4.2 算法流程

步驟1：初始化參數(shù)。包括ξ，η，ρ0，κ，α，β，γ，χ，ε，μ，最大循環(huán)次數(shù)Tmax等相關(guān)參數(shù)。

步驟2：初始化規(guī)劃任務(wù)。

步驟3：抗原識(shí)別。提取環(huán)境信息，根據(jù)式（1）進(jìn)行抗原編碼。

步驟4：抗體匹配。根據(jù)式（3）從規(guī)則庫中尋找大于臨界親和度且為最大的匹配抗體。如果有執(zhí)行步驟5，否則按照式（2）生成新抗體。

步驟5：按式（10）計(jì)算匹配抗體或新抗體命令集的選擇概率，并用輪盤賭算法進(jìn)行選擇實(shí)現(xiàn)抗體轉(zhuǎn)移。

步驟6：判斷機(jī)器人是否發(fā)生徘徊或碰撞。若未發(fā)生則執(zhí)行下一步，否則按照式（12）進(jìn)行抗體命令清晰度學(xué)習(xí)并轉(zhuǎn)步驟3。

步驟7：判斷是否到達(dá)終點(diǎn)。若沒有則轉(zhuǎn)步驟3，否則保留最優(yōu)路徑解，并按照式（13）進(jìn)行抗體命令清晰度的更新。

步驟8：判斷是否完成所有循環(huán)的搜索。若沒有則轉(zhuǎn)步驟2，否則輸出最優(yōu)路徑。

5 仿真實(shí)驗(yàn)與討論

為了驗(yàn)證本文提出的改進(jìn)的免疫網(wǎng)絡(luò)路徑規(guī)劃算法（IINA）的有效性，本文基于MATLAB 7.0語言，針對(duì)圖4兩種室內(nèi)平面環(huán)境進(jìn)行路徑規(guī)劃實(shí)驗(yàn)（其中起點(diǎn)為S，終點(diǎn)為G，各種黑色形狀為障礙物），并與基本免疫網(wǎng)絡(luò)算法（SINA）和蟻群算法（ACA）進(jìn)行了比較。算法收斂條件是：最優(yōu)抗體（螞蟻）路徑長(zhǎng)度連續(xù)15代未發(fā)生改善?？紤]到算法的隨機(jī)性，每種環(huán)境每種算法共進(jìn)行了30次獨(dú)立隨機(jī)實(shí)驗(yàn)。在獲得局部曲折的最優(yōu)抗體（螞蟻）路徑后，本文對(duì)其進(jìn)行了平滑處理以適合機(jī)器人行走。

圖4 仿真環(huán)境Fig.4 Simulation environments

表1為3種算法的規(guī)劃性能比較。從4種路徑長(zhǎng)度來看，SINA路徑最長(zhǎng)，顯示出其全局規(guī)劃能力較弱，IINA引入了勢(shì)場(chǎng)法，并將其規(guī)劃結(jié)果作為先驗(yàn)知識(shí)構(gòu)建了引導(dǎo)權(quán)，從而設(shè)計(jì)了新的抗體轉(zhuǎn)移概率，較好地提高了抗體的轉(zhuǎn)移效率，使得IINA的規(guī)劃能力明顯優(yōu)于SINA。ACA具有全局優(yōu)化能力，其信息素的正反饋機(jī)制增強(qiáng)了其優(yōu)化能力，使得其規(guī)劃路徑整體上優(yōu)于SINA，但劣于IINA。從平均收斂代數(shù)看，SINA雖收斂最快，但僅一種局部收斂，而基于勢(shì)場(chǎng)導(dǎo)向的抗體轉(zhuǎn)移加快了算法的收斂速度，使其收斂性能優(yōu)于ACA。

表1 3種算法的性能比較Table 1 Performance comparison among three algorithms

圖5為3種算法在兩種環(huán)境下的平均收斂曲線。由圖5可看出，SINA的平均規(guī)劃性能最弱；IINA有了明顯的提高，既具備了與ACA相似的收斂速率，且其規(guī)劃性能是3種優(yōu)化算法中最優(yōu)的。

圖5 3種算法的平均收斂曲線Fig.5 Average convergence curves of three algorithms

圖6給出了3種算法在環(huán)境二里的最優(yōu)規(guī)劃結(jié)果及對(duì)應(yīng)的光滑路徑。由圖6可看出，3種算法都能找到各自最優(yōu)路徑，顯示出較好的魯棒性和柔韌性，IINA所規(guī)劃的路徑長(zhǎng)度最短。

圖6 環(huán)境二中3種算法的最優(yōu)規(guī)劃結(jié)果Fig.6 Optimal planning results of three algorithms in environment II

6 結(jié)語

基于生物免疫學(xué)的人工免疫系統(tǒng)，由于其自組織、自學(xué)習(xí)、自識(shí)別和自記憶能力，為路徑規(guī)劃研究開辟了一個(gè)新的領(lǐng)域。為了解決復(fù)雜環(huán)境中移動(dòng)機(jī)器人的自主導(dǎo)航問題，本文基于丹麥學(xué)者Jerne的獨(dú)特型網(wǎng)絡(luò)假設(shè)，構(gòu)建了免疫網(wǎng)絡(luò)規(guī)劃模型。為了進(jìn)一步提高免疫網(wǎng)絡(luò)規(guī)劃模型中抗體的轉(zhuǎn)移效率，研究中引入了計(jì)算量小、實(shí)時(shí)性好的人工勢(shì)場(chǎng)法，將其規(guī)劃結(jié)果作為先驗(yàn)知識(shí)，設(shè)計(jì)了基于勢(shì)場(chǎng)導(dǎo)向權(quán)的改進(jìn)人工免疫網(wǎng)絡(luò)路徑規(guī)劃算法。實(shí)驗(yàn)結(jié)果表明，在最優(yōu)規(guī)劃能力和網(wǎng)絡(luò)收斂性能方面，新算法IINA比SINA有了明顯提高，在解決移動(dòng)機(jī)器人的路徑規(guī)劃問題上具有較好的應(yīng)用前景。

[1]蔣新松.機(jī)器人學(xué)導(dǎo)論[M].遼寧：遼寧科學(xué)技術(shù)出版社，1994.

[2]Saboori I，Menhaj M B，Karimi B.Optimal robot path planning based on fuzzy model of obstacles[C]//Proceedings of 2006 IEEE International Conference on Industrial Electronics.USA：NJ，Piscataway.IEEE，2006：383-387.

[3]Liu J，Yang D Y.Path planning based on double-layer genetic algorithm[C]//Proceedings of the Third International Conference on NaturalComputation.USA：NJ，Piscataway.IEEE，2007：357-361.

[4]Liu G Q，Li T J，Li Y P.The ant algorithm for solving robot path planning problem[C]//Proceedings of the Third International Conference on Information Technology and Applications.USA：NJ，Piscataway.IEEE，2005：25-27.

[5]Yuan M X，Wang S A，Li K P.A model of ant colony and immune network and its application in path planning[C]//Proceedings of 3rd IEEE Conference on Industrial Electronics and Application.USA：NJ，Piscataway.IEEE，2008：102-107.

[6]Dasgupta D.Artificial Immune Systems and Their Applications[M].Berlin：Springer-Verlag，Inc，1999.

[7]Farmer J D，Packard N H，Perelson A S.The immune system，adaptationandmachinelearning[J].PhysicsD，1986，2（2）：187-204.

[8]Ishiguro A，Shirai Y，Kondo T，et al.Immunoid：an architecture for behavior arbitration based on the immune networks[C]//Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems.USA：NJ，Piscataway.IEEE，1996：1730-1736.

[9]Meshref H，VanLandingham H.Artificial immune systems：application to autonomous agents[C]//IEEE International Conference on Systems，Man，and Cybernetics.USA：NJ，Piscataway.IEEE，2000：61-66.

[10]莊 健，王孫安.基于人工免疫網(wǎng)絡(luò)機(jī)器人路徑規(guī)劃算法的進(jìn)一步研究[J].系統(tǒng)仿真學(xué)報(bào)，2004，16（5）：1017-1019.

[11]Jerne N K.Idiotypic networks and other preconceived ideas[J].Immunological Rev，1984，79：5-24.

[12]Yuan M X，Wang S A，Zhuang J，et al.Immune network algorithm based on improved APF for on-line dynamic planning[C]//Proceedings of IEEE International Conference on Robotics，Automation and Mechatronics.2008：193-198.