基于勢場導向權的改進機器人路徑規劃免疫算法

王孫安，吳燦陽

（西安交通大學機械工程學院，西安710049）

1 前言

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

由生物免疫系統啟發而來的人工免疫系統，因其自組織、自學習和免疫記憶等優點為解決工程問題尤其是機器人技術提供了新契機[6]。20世紀80年代，Farmer等人基于免疫網絡學說給出了免疫系統的動態模型[7]。基于該動態模型，1996年日本學者Ishiguro等[8]率先提出了一種行為仲裁系統，并在垃圾自動回收上得到評估。Meshref等[9]實現了分布式自主機器人系統中的狗羊放牧問題。Farmer模型體現了較好的魯棒性和柔韌性，但是缺乏全局優化能力。基于生物免疫網絡理論，文獻[10]設計了一種新的機器人路徑規劃算法。該算法通過學習獲取規則和清晰規則，具有很強的空間搜索能力和規則發現與再學習能力，但在搜索精度和路徑收斂性能方面還有待進一步提高。為了更好地解決復雜環境中的移動機器人路徑規劃問題，本文提出了一種改進的基于勢場導向權的人工免疫網絡路徑規劃算法。

2 人工免疫網絡規劃模型及其定義

2.1 生物免疫系統

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

圖1 獨特型網絡模型Fig.1 Jerne’s idiotypic networks

2.2 人工免疫網絡路徑規劃模型

為了實現移動機器人的免疫路徑規劃，本文將移動機器人所處環境作為抗原，抗原的表位是包含障礙物和目標信息的環境信息。將機器人的移動行為作為抗體，抗體的獨特位同樣是環境信息，對位是機器人運動命令。抗原和抗體匹配稱為刺激，不匹配稱為抑制，主要通過抗原抗體的親和度來衡量。

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

2.3 基本定義

為了便于人工免疫網絡規劃算法的描述，首先給出如下基本定義[5]。

圖2 人工免疫網絡規劃模型Fig.2 Planning model of artificial immune

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

定義1：抗原（Ag）代表機器人所處室內平面環境。

定義2：抗體（Ab）代表機器人針對環境信息產生的對應行為。

式（2）中，IAbO為障礙物信息，IAbO=AbOi，?i∈IAbG為目標信息，，集合元素定義同抗原；Com為運動命令，Com=C。

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

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

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

3 人工勢場法及其導向權

在基于人工免疫網絡的路徑規劃算法中，抗體在抗體網絡中的轉移效率直接影響到算法的搜索性能。文獻[10]按照抗體生命力進行轉移概率的設計，但搜索能力和網絡收斂性能較差。為了提高抗體的轉移效率，文獻[5]融合蟻群算法，將命令清晰度和抗體轉移后的距離變化作為變量設計了轉移概率。文獻[12]將勢場法的規劃結果作為先驗知識，對文獻[5]中的命令清晰度進行優化，進一步提高了抗體的轉移效率。為了更有效地利用勢場法并提高抗體的轉移效率，本文將人工勢場法的規劃結果作為導向權，構建了新的抗體轉移算子，從而優化人工免疫網絡的路徑規劃算法。

人工勢場法是由Khatib于1986年提出來的，其基本思想是：在目標位置構造引力勢場Uatt和在障礙物周圍構造斥力勢場Urep，機器人在Uatt的引力Fatt和Urep的斥力Frep共同作用下向目標運動。

設X、Xobs、Xgoal分別為機器人、障礙物和目標的位置向量。引力勢場通常定義為（4）

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

引力通常取引力勢場的負梯度當m=2時，Fatt=ξ‖Xgoal-X‖斥力勢場通常定義為式（6）中，η為斥力場正比例系數；ρ0為障礙物影響距離 ；n為 正 常 數 ；ρ(X，Xobs)=‖X-Xobs‖ ；ρ(X,Xgoal)=‖X-Xgoal‖。

斥力同樣定義為斥力勢場的負梯度

根據人工勢場法的原理，機器人的避障角度為

設某抗體運動命令方向與x軸的夾角為θx，則定義該抗體運動命令的人工勢場導向權為

式（9）中，κ為調整系數。

由式（9）可看出，當抗體命令執行方向與機器人的避障方向越接近，導向權越大。

4 基于勢場導向權的免疫網絡路徑規劃算法

4.1 主要算子

1）抗體轉移算子。為了提高抗體的選擇效率，本文將抗體命令清晰度、抗體轉移的距離變化和勢場導向權作為變量，構建如下的抗體轉移概率

式（10）中，τi（t）為抗體第i號運動命令的清晰度；α為抗體命令清晰度啟發因子；σi（t）為抗體第i號運動命令的導向權；β為勢場導向權啟發因子；qi（t）為抗體第i號命令的目標啟發函數；γ為目標啟發因子。

qi（t）的表達式如下

式（11）中，Δd為機器人執行8個命令后與目標點的距離變化結果集合；l為調整系數，且l>0。

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

2）抗體命令清晰度學習算子。抗體在轉移過程中，往往會產生碰撞或因陷入局部極小而造成的徘徊。為了解決抗體轉移過程中存在的上述問題，本文采用式（12）的抗體命令清晰度學習策略。

式（12）中，n為當前所處位置在抗體鏈中的層數；Nn為抗體鏈總層數；χ為學習可變系數，且χ<1；ε為學習定系數，且ε>0。

抗體命令清晰度學習的目的是減小造成碰撞和徘徊的抗體運動命令的參與機會，增加其他抗體運動命令的參與機會。

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

式（13）中，ρ為抗體命令清晰度遺忘率；μ為常數；L為規劃的路徑長度。

由式（13）可看出，免疫規劃路徑越短，說明抗體網絡中的抗體執行命令越正確，相應抗體命令獲得的激勵程度越大，其清晰度也就變得更高。

4.2 算法流程

步驟1：初始化參數。包括ξ，η，ρ0，κ，α，β，γ，χ，ε，μ，最大循環次數Tmax等相關參數。

步驟2：初始化規劃任務。

步驟3：抗原識別。提取環境信息，根據式（1）進行抗原編碼。

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

步驟5：按式（10）計算匹配抗體或新抗體命令集的選擇概率，并用輪盤賭算法進行選擇實現抗體轉移。

步驟6：判斷機器人是否發生徘徊或碰撞。若未發生則執行下一步，否則按照式（12）進行抗體命令清晰度學習并轉步驟3。

步驟7：判斷是否到達終點。若沒有則轉步驟3，否則保留最優路徑解，并按照式（13）進行抗體命令清晰度的更新。

步驟8：判斷是否完成所有循環的搜索。若沒有則轉步驟2，否則輸出最優路徑。

5 仿真實驗與討論

為了驗證本文提出的改進的免疫網絡路徑規劃算法（IINA）的有效性，本文基于MATLAB 7.0語言，針對圖4兩種室內平面環境進行路徑規劃實驗（其中起點為S，終點為G，各種黑色形狀為障礙物），并與基本免疫網絡算法（SINA）和蟻群算法（ACA）進行了比較。算法收斂條件是：最優抗體（螞蟻）路徑長度連續15代未發生改善。考慮到算法的隨機性，每種環境每種算法共進行了30次獨立隨機實驗。在獲得局部曲折的最優抗體（螞蟻）路徑后，本文對其進行了平滑處理以適合機器人行走。

圖4 仿真環境Fig.4 Simulation environments

表1為3種算法的規劃性能比較。從4種路徑長度來看，SINA路徑最長，顯示出其全局規劃能力較弱，IINA引入了勢場法，并將其規劃結果作為先驗知識構建了引導權，從而設計了新的抗體轉移概率，較好地提高了抗體的轉移效率，使得IINA的規劃能力明顯優于SINA。ACA具有全局優化能力，其信息素的正反饋機制增強了其優化能力，使得其規劃路徑整體上優于SINA，但劣于IINA。從平均收斂代數看，SINA雖收斂最快，但僅一種局部收斂，而基于勢場導向的抗體轉移加快了算法的收斂速度，使其收斂性能優于ACA。

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

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

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

圖6給出了3種算法在環境二里的最優規劃結果及對應的光滑路徑。由圖6可看出，3種算法都能找到各自最優路徑，顯示出較好的魯棒性和柔韌性，IINA所規劃的路徑長度最短。

圖6 環境二中3種算法的最優規劃結果Fig.6 Optimal planning results of three algorithms in environment II

6 結語

基于生物免疫學的人工免疫系統，由于其自組織、自學習、自識別和自記憶能力，為路徑規劃研究開辟了一個新的領域。為了解決復雜環境中移動機器人的自主導航問題，本文基于丹麥學者Jerne的獨特型網絡假設，構建了免疫網絡規劃模型。為了進一步提高免疫網絡規劃模型中抗體的轉移效率，研究中引入了計算量小、實時性好的人工勢場法，將其規劃結果作為先驗知識，設計了基于勢場導向權的改進人工免疫網絡路徑規劃算法。實驗結果表明，在最優規劃能力和網絡收斂性能方面，新算法IINA比SINA有了明顯提高，在解決移動機器人的路徑規劃問題上具有較好的應用前景。

[1]蔣新松.機器人學導論[M].遼寧：遼寧科學技術出版社，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]莊 健，王孫安.基于人工免疫網絡機器人路徑規劃算法的進一步研究[J].系統仿真學報，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.