神經(jīng)元活性引導(dǎo)機器人脫困的全覆蓋路徑規(guī)劃

江靜嵐

（柳州鐵道職業(yè)技術(shù)學(xué)院，廣西 柳州 545616）

1 引言

移動機器人導(dǎo)航包括地圖創(chuàng)建、路徑規(guī)劃與跟蹤控制等方面，路徑規(guī)劃分為點對點規(guī)劃和全覆蓋規(guī)劃兩類。全覆蓋機器人廣泛應(yīng)用于除草、掃地、噴涂等行業(yè)和領(lǐng)域，要求對工作區(qū)域遍歷的同時重復(fù)覆蓋率較低[1]。研究機器人全區(qū)域覆蓋方法，對提高機器人工作效率和降低機器人能耗意義明顯。

機器人工作區(qū)域全覆蓋方法可以分為三類，分別為傳統(tǒng)覆蓋方法、基于區(qū)域分解覆蓋方法、基于柵格地圖覆蓋方法。傳統(tǒng)覆蓋方法包括模板法和內(nèi)螺旋法，模板法根據(jù)環(huán)境特征預(yù)先設(shè)定運動模板，機器人進行環(huán)境匹配后根據(jù)此模板運動[2]，此方法能夠完成遍歷，但是要求環(huán)境不能發(fā)生任何變化，應(yīng)用范圍極小。內(nèi)螺旋法是一種沿邊法[3]，當(dāng)遇到已覆蓋區(qū)域或邊界時則內(nèi)旋一個單位繼續(xù)工作，此方法對環(huán)境精度要求極高，且難以實現(xiàn)完全覆蓋。基于區(qū)域分解的覆蓋方法是根據(jù)障礙物形狀將工作區(qū)域進行劃分，子工作區(qū)域內(nèi)沒有障礙物，而后對設(shè)定子區(qū)域遍歷法、子區(qū)域遍歷順序等，包括牛耕分解法[4]、矩形分解法[5]等。基于柵格地圖覆蓋方法包括生成樹法、生物激勵神經(jīng)網(wǎng)絡(luò)法等，生成樹法[6]將每四個柵格合成一個單元，通過全部單元連接實現(xiàn)遍歷，此方法需要極大的存儲空間且路徑轉(zhuǎn)彎較多；生物激勵神經(jīng)網(wǎng)絡(luò)算法[7]中神經(jīng)元使用分流方程與相鄰神經(jīng)元交流，根據(jù)神經(jīng)元活性值選擇下一柵格，此方法計算簡單，無需學(xué)習(xí)過程，其最大缺陷是存在“死區(qū)”問題。

這里為了解決生物激勵神經(jīng)網(wǎng)絡(luò)算法存在的死區(qū)問題，使機器人高效地完成工作區(qū)域全覆蓋，提出了脫困點搜索和脫困點路徑規(guī)劃方法。制定了元胞自動機演化規(guī)則，搜索到了最佳脫困點；使用神經(jīng)元活性值引導(dǎo)RRT算法，使隨機樹擴展具有方向性，完成了脫困路徑規(guī)劃。帶有脫困機制的生物激勵神經(jīng)網(wǎng)絡(luò)算法能夠有效完成工作區(qū)域全覆蓋，是一種有效的遍歷路徑規(guī)劃方法。

2 生物激勵神經(jīng)網(wǎng)絡(luò)全覆蓋方法

2.1 柵格環(huán)境模型

使用生物激勵神經(jīng)網(wǎng)絡(luò)算法進行全區(qū)域覆蓋規(guī)劃時，首先需要建立工作區(qū)域的柵格模型。使用方形柵格對工作區(qū)域進行分割，當(dāng)柵格內(nèi)不存在障礙物時稱為自由柵格，當(dāng)柵格內(nèi)存在障礙物時稱為障礙物柵格，另外自由柵格需要區(qū)分已覆蓋柵格和未覆蓋柵格。通過對柵格賦不同屬性值，使機器人能夠識別以上3類柵格，對障礙物柵格賦值為“-1”，對已覆蓋柵格賦值為“0”，對未覆蓋柵格賦值為“1”。機器人某次規(guī)劃過程，如圖1所示。其對應(yīng)點陣為：

圖1 機器人某次規(guī)劃過程Fig.1 A Planning Process of Robot

柵格法的編碼方法包括直角坐標(biāo)法和順序編碼法，相互轉(zhuǎn)換關(guān)系可參考文獻[8]，此內(nèi)容非本文重點，這里不再贅述。另外，方形柵格法包括“四叉樹法”和“八叉樹法”，本文使用的是“八叉樹法”。

2.2 生物激勵神經(jīng)網(wǎng)絡(luò)

使用柵格法將工作區(qū)域離散化，每個柵格對應(yīng)一個神經(jīng)元，柵格屬性值即為神經(jīng)元初始活性值。二維的生物激勵神經(jīng)網(wǎng)絡(luò)模型，如圖2所示。每個神經(jīng)元與周圍相鄰神經(jīng)元相互連接，實現(xiàn)神經(jīng)元活性相互影響與傳遞。

圖2 二維生物激勵神經(jīng)網(wǎng)絡(luò)模型Fig.2 2-Dimention Biologically Inspired Neural Network Model

神經(jīng)元活性值由分流方程描述外部激勵及相互間作用關(guān)系[9]，為：

式中：uk—第k個神經(jīng)元活性值；RB—活性值衰減速率，是一個正值常數(shù)；UB、LB—活性值上下限；m—神經(jīng)網(wǎng)絡(luò)中神經(jīng)元k的相鄰柵格數(shù)；wkl—神經(jīng)元k與神經(jīng)元l的權(quán)值，權(quán)值矩陣具有對稱性，即wkl=wlk；函數(shù)外部輸入信號，當(dāng)Ik＞0時Ik為激勵信號，當(dāng)Ik＜0時Ik為抑制信號。根據(jù)不同柵格類型，為Ik設(shè)置不同值，即：

式中：EB?UB—外部輸入值。

神經(jīng)元k與神經(jīng)元l之間的連接權(quán)值wkl定義為兩者歐式距離的遞減函數(shù)，這里設(shè)置為：

式中：μ—一個常數(shù)，取值范圍為0 ＜μ＜1。

分析式（1）可知，對于未覆蓋區(qū)域，正的活性值可以通過分流方程不斷擴散，在全局范圍內(nèi)對機器人產(chǎn)生吸力；而對于障礙物區(qū)域，負(fù)的活性值不參與分流方程，只受外部輸入的作用，因此對機器人沒有任何吸引作用，達(dá)到避障目的。

機器人轉(zhuǎn)彎不僅降低工作效率，同時增加了磨損降低機器人使用壽命。為了減少機器人轉(zhuǎn)彎次數(shù)，將轉(zhuǎn)彎角度加入到活性值中，作為一項選擇指標(biāo)，即：

式中：Pathk—神經(jīng)元k選擇的路徑；η—方向權(quán)值，（1）調(diào)節(jié)活性值與轉(zhuǎn)向角處于同一數(shù)量級，（2）調(diào)節(jié)轉(zhuǎn)向約束重要性；Δθl—選擇相鄰神經(jīng)元l的轉(zhuǎn)向角，由式（3）可知轉(zhuǎn)向角越大則被選概率越小，是為了保證機器人直線行駛，提高行走效率；(xl，yl)—下一時刻神經(jīng)元l的位置，(xc，yc)—機器人當(dāng)前時刻神經(jīng)元位置，(xp，yp)—上一時刻神經(jīng)元位置。

2.3 生物激勵神經(jīng)網(wǎng)絡(luò)全覆蓋原理及缺陷分析

根據(jù)前文生物激勵神經(jīng)網(wǎng)絡(luò)工作原理，制定全覆蓋路徑規(guī)劃過程為：首先根據(jù)柵格法建立工作環(huán)境模型，為每個神經(jīng)元賦初始活性值。從起始點開始規(guī)劃，每走過一個柵格將其屬性活性值強制設(shè)置為0，而后依據(jù)式（1）進行活性值更新。路徑規(guī)劃過程中，障礙物神經(jīng)元不進行活性值更新，只對自由神經(jīng)元活性值更新。機器人每前進一步，則按照式（1）對自由神經(jīng)元進行一次活性值更新，按照式（3）選擇相鄰柵格中最大值作為下一柵格，直至結(jié)束。對于某一工作環(huán)境，按照生物激勵神經(jīng)網(wǎng)絡(luò)全覆蓋規(guī)劃方法，得到的覆蓋結(jié)果，如圖3（a）所示，此時神經(jīng)元活性值，如圖3（b）所示。

圖3 生物激勵神經(jīng)網(wǎng)絡(luò)規(guī)劃結(jié)果Fig.3 Planning Resultant of Biologically Inspired Neural Network

圖3（a）中S點為路徑起始點，A點為終止點。從路徑規(guī)劃結(jié)果看，生物激勵神經(jīng)網(wǎng)絡(luò)算法陷入了“死區(qū)”問題，死區(qū)問題是指機器人周圍柵格不存在未覆蓋柵格，但是在整個區(qū)域中仍存在未覆蓋區(qū)域。圖3（b）中未覆蓋區(qū)域神經(jīng)元活性值較高，對機器人具有較強的吸引作用，但是機器人陷入“死區(qū)”無法完成遍歷。

3 脫困機制設(shè)計

為了解決生物激勵神經(jīng)網(wǎng)絡(luò)存在的“死區(qū)”問題，本節(jié)設(shè)計了機器人脫困機制，包括基于元胞自動機的脫困點搜索和改進RRT算法的脫困路徑規(guī)劃等兩方面內(nèi)容。

3.1 脫困點搜索

元胞自動機是模擬生物自復(fù)制現(xiàn)象提出的[10]，元胞自動機系統(tǒng)定義在一個由有限狀態(tài)的元胞組成的離散空間中，給定元胞初始條件和演化規(guī)則，元胞就能夠根據(jù)演化規(guī)則自動迭代演化。元胞系統(tǒng)符號表達(dá)式為：

式中：M—元胞系統(tǒng)；Ld—元胞空間，d—空間維度；S—元胞狀態(tài)；N ={s1，s2，…，sn} —鄰居元胞集合；n—鄰居元胞數(shù)量；f—演化規(guī)則。

這里機器人工作空間為二維，因此元胞空間維度也為二維，即d=2。元胞狀態(tài)S取有限個離散狀態(tài)，如{1 ，2，…，?} 。前文中指出，使用“八叉樹”方形柵格，每個元胞具有8個鄰居元胞，此時n=8。演化規(guī)則是元胞自動機系統(tǒng)的核心內(nèi)容，是所有元胞的狀態(tài)轉(zhuǎn)移函數(shù)，直接決定了元胞下一時刻狀態(tài)。

首先為元胞自動機配置空間，也即元胞狀態(tài)初始化。在此需要強調(diào)的是，元胞位置與柵格位置（或神經(jīng)元位置）一一對應(yīng)，但是元胞狀態(tài)值與神經(jīng)元活性值是沒有任何關(guān)聯(lián)的，存在于不同的知識系統(tǒng)中。根據(jù)不用的柵格類型，元胞初始狀態(tài)設(shè)置為：

在介紹元胞演化規(guī)則前，首先對中心元胞和鄰居元胞進行明確，按照柵格“八叉樹”法，處于中心位置的元胞為中心元胞，其周圍的8個元胞為鄰居元胞。根據(jù)搜索脫困點這一目標(biāo)，制定元胞演化規(guī)則為：（1）首先查找狀態(tài)值為1的元胞，狀態(tài)更新從陷入死區(qū)位置元胞開始；（2）以死區(qū)元胞為中心元胞，將其鄰居元胞中狀態(tài)為0的元胞狀態(tài)更新為2；（3）以狀態(tài)值為2的元胞為中心元胞，將其鄰居元胞中狀態(tài)為0的元胞狀態(tài)更新為3；（4）而后分別以狀態(tài)為3的元胞為中心元胞、狀態(tài)為4的元胞為中心元胞，對其鄰居元胞進行更新，直至所有0元胞更新完畢。

從以上演化規(guī)則可以得到三點結(jié)論：（1）障礙物元胞的狀態(tài)值不更新；（2）障礙物元胞不作為中心元胞；（3）每個自由元胞只有一次狀態(tài)更新機會。按照以上演化規(guī)則，圖3（a）所示環(huán)境的元胞初始狀態(tài)值及更新狀態(tài)值，如圖4所示。

圖4 元胞自動機狀態(tài)演化Fig.4 State Evolution of Cellular Automata

圖中狀態(tài)值為1的元胞是機器人陷入死區(qū)的位置，彩色數(shù)字區(qū)域為機器人未覆蓋區(qū)域，未覆蓋區(qū)域中狀態(tài)最小的元胞位置即為機器人脫困點，也即圖4（b）中彩色9處的元胞位置。至此脫困點被找到，下節(jié)給出從死區(qū)位置到脫困點的路徑規(guī)劃方法。

3.2 改進RRT算法的脫困路徑規(guī)劃

快速擴展隨機樹（Rapidly-Exploring Random Tree，RRT）是一種在全局空間中隨機采樣、通過節(jié)點不斷擴展而連接起始點與目標(biāo)點的路徑規(guī)劃方法[11]。在二維規(guī)劃區(qū)域S?R2中，障礙物區(qū)域記為Sobs，自由區(qū)域記為Sfree，路徑規(guī)劃起點記為Pstart，目標(biāo)點記為Pend。RRT算法以起始點Pstart為根節(jié)點，在規(guī)劃區(qū)域內(nèi)使用隨機采樣法得到采樣點Prand，使用樹節(jié)點搜索的方法搜索到距離Prand最近的樹節(jié)點Pnear，以Pnear為父節(jié)點向Prand方向擴展一個步長，得到新的樹節(jié)點Pnew，對Pnew進行碰撞檢測和機器人動力學(xué)約束檢測，若Pnew未落在障礙物區(qū)域Sobs內(nèi)，且滿足機器人動力學(xué)約束，則Pnew擴展成功。重復(fù)上述步驟，直至目標(biāo)點Pend成為樹節(jié)點，或者與某一樹節(jié)點距離小于一個步長，而后以Pend為起點，反向追溯父節(jié)點直至回到起始點Pstart，此時路徑搜索完畢。

從上述RRT算法的原理可以看出，樹節(jié)點擴展時在整個規(guī)劃區(qū)域進行隨機采樣，這種盲目采樣方式增加了大量無效采樣點和樹節(jié)點，極大地增加了規(guī)劃時間、降低了規(guī)劃效率。為了解決這一問題，這里提出了神經(jīng)元活性引導(dǎo)的RRT脫困路徑規(guī)劃方法（RRT Guided by Neuronal Activity，RRTGNA）。在生物激勵神經(jīng)網(wǎng)絡(luò)算法中，機器人陷入“死區(qū)問題”后，未覆蓋區(qū)域神經(jīng)元活性值較高，如圖3（b）所示。較高地神經(jīng)元活性值根據(jù)式（1）向全域神經(jīng)元擴散，在全域范圍內(nèi)對機器人具有吸引作用，此時規(guī)劃區(qū)域內(nèi)必然存在一條或若干條活性值單調(diào)遞減的路線，且此路線必然連接脫困點和死區(qū)位置。根據(jù)這一結(jié)論，可以使用神經(jīng)元活性值對樹節(jié)點擴展進行引導(dǎo)。

在傳統(tǒng)RRT算法中，新節(jié)點Pnew只進行碰撞約束檢驗和機器人動力學(xué)約束檢驗，當(dāng)滿足約束時擴展成功，不滿足約束時則重新采樣。而在RRTGNA算法中，新節(jié)點Pnew首先要進行神經(jīng)元活性值檢驗，新節(jié)點Pnew活性值記為Anew，對應(yīng)的父節(jié)點Pnear活性值記為Anear，只有當(dāng)Anew≥Anear時才滿足神經(jīng)元活性值擴展約束，而后進行碰撞等檢驗。這種使用神經(jīng)元活性值對樹節(jié)點擴展進行引導(dǎo)的方式，避免了樹節(jié)點擴展的隨機性和盲目性，可以極大地提高隨機樹的擴展效率，減少隨機樹擴展點和路徑規(guī)劃時間。在此需要說明的是，任意節(jié)點處的活性值為此節(jié)點所在神經(jīng)元（或柵格）的活性值。

3.3 具有脫困機制的全覆蓋規(guī)劃方法

綜合第2節(jié)和第3節(jié)內(nèi)容，給出具有脫困機制的全覆蓋路徑規(guī)劃方法為：

（1）使用生物激勵神經(jīng)網(wǎng)絡(luò)方法進行全覆蓋路徑規(guī)劃，若不存在死區(qū)問題，則算法結(jié)束，給出全覆蓋路徑；若存在死區(qū)問題，則進入（2）；

（2）調(diào)用脫困機制，首先使用元胞自動機搜索脫困點，而后使用神經(jīng)元活性值引導(dǎo)的RRT算法進行脫困路徑規(guī)劃；

（3）機器人按照（2）步路徑行駛到脫困點，而后在未覆蓋區(qū)域使用生物激勵神經(jīng)網(wǎng)絡(luò)進行路徑規(guī)劃，完畢后判斷是否仍存在未覆蓋區(qū)域，若不存在則算法結(jié)束；若存在則進入（2），直至所有區(qū)域完成遍歷，算法結(jié)束。

4 仿真驗證與分析

以圖3（a）所示工作環(huán)境為規(guī)劃區(qū)域，使用柵格法將其分割為25×25個柵格，每個柵格對應(yīng)一個神經(jīng)元。按照柵格類型為其賦不同屬性值，同時初始化神經(jīng)元活性值。生物激勵神經(jīng)網(wǎng)絡(luò)算法參數(shù)設(shè)置為：衰減速率RB=20，活性值上限UB=1，活性值下限LB=-1，外部輸入值EB=100，方向權(quán)值η=0.03，距離常數(shù)μ=0.8。使用生物激勵神經(jīng)網(wǎng)絡(luò)算法以左上角S點為起點進行遍歷路徑規(guī)劃，結(jié)果如圖3（a）所示。從圖中可以看出，機器人陷入了“死區(qū)”問題，A點為“死區(qū)位置”。

按照3.3節(jié)規(guī)劃流程，此時調(diào)用脫困機制，首先使用元胞自動機搜索脫困點，從陷入死區(qū)位置的元胞開始演化，得到元胞演化穩(wěn)定狀態(tài)，如圖4（b）所示。未覆蓋區(qū)域（彩色數(shù)字區(qū)域）中狀態(tài)值最小的元胞位置為脫困點，即彩色數(shù)字“9”對應(yīng)的元胞位置。

而后進行脫困路徑規(guī)劃，為了形成對比效果，分別使用傳統(tǒng)RRT算法和神經(jīng)元活性值引導(dǎo)的RRT算法進行規(guī)劃，每種算法各自獨立規(guī)劃50次，從規(guī)劃結(jié)果中隨機抽取一組規(guī)劃結(jié)果進行展示結(jié)果，如圖5所示。

圖5 脫困路徑規(guī)劃Fig.5 Escape Path Planning

圖5中隱藏了機器人已行駛路線，只給出了規(guī)劃路徑和采樣點。圖中A點為“死區(qū)位置”，B點為元胞自動機確定的脫困點。從圖中可以看出，傳統(tǒng)RRT算法為全局采樣，采樣具有盲目性和隨機性。而改進RRT算法在神經(jīng)元活性值的引導(dǎo)作用下，采樣點的采樣和隨機樹的擴展向神經(jīng)元活性值較高的方向前進，具有較強的方向性，避免了全局范圍內(nèi)的采樣和擴展，極大地減少了無效節(jié)點數(shù)量。統(tǒng)計傳統(tǒng)RRT算法和神經(jīng)元活性值引導(dǎo)RRT算法（RRTGNA）50次運行結(jié)果的平均時間、路徑平均長度、擴展節(jié)點數(shù)，如表1所示。

表1 脫困路徑規(guī)劃結(jié)果Tab.1 Escape Path Planning Result

從表中可以看出，RRTGNA算法平均運行時間為0.403s，比傳統(tǒng)RRT算法小了約一個數(shù)量級；RRTGNA 算法規(guī)劃的脫困路徑平均長度比傳統(tǒng)RRT算法減少了12.96%；RRTGNA算法的擴展節(jié)點數(shù)為306個，比傳統(tǒng)RRT算法少了約兩倍。以上數(shù)據(jù)說明了RRTGNA 算法在采樣和擴展時具有極強的方向性，沿著神經(jīng)元活性提高的方向擴展，極大地減少了擴展節(jié)點數(shù)，降低了算法運行的時間消耗，同時神經(jīng)元的引導(dǎo)作用使路徑擴展目的性強，起到了降低路徑長度的效果。

機器人沿著脫困路徑到達(dá)脫困點，而后使用生物激勵神經(jīng)網(wǎng)絡(luò)對未覆蓋區(qū)域繼續(xù)進行遍歷規(guī)劃結(jié)果，如圖6所示。

圖6 全覆蓋規(guī)劃結(jié)果Fig.6 Complete Planning Result

從圖中可以看出，機器人沿脫困路徑擺脫死區(qū)后到達(dá)脫困點，以脫困點為起點使用生物激勵神經(jīng)網(wǎng)絡(luò)算法繼續(xù)進行遍歷路徑規(guī)劃，完成了對整個工作區(qū)域的遍歷。圖6（b）中除障礙物神經(jīng)元外，其余神經(jīng)元活性值為0，也表示機器人對整個區(qū)域完成了遍歷。由此可以看出，具有脫困機制的生物激勵神經(jīng)網(wǎng)絡(luò)算法能夠有效遍歷整個工作區(qū)域，當(dāng)陷入“死區(qū)問題”時，調(diào)用脫困機制能夠高效地擺脫死區(qū)而完成所有區(qū)域的遍歷。

5 結(jié)論

這里研究了機器人對工作區(qū)域的遍歷路徑規(guī)劃問題，以生物激勵神經(jīng)網(wǎng)絡(luò)算法為基礎(chǔ)，當(dāng)機器人陷入死區(qū)后調(diào)用脫困機制，可以高效脫困并完成區(qū)域遍歷。仿真驗證，得出了以下結(jié)論：（1）基于元胞自動機的脫困點搜索方法可以有效找到最佳脫困點；（2）神經(jīng)元活性值引導(dǎo)的RRT算法在節(jié)點擴展時具有較強的方向性，減少了擴展節(jié)點和運行時間，降低了脫困路徑長度；（3）帶脫困機制的生物激勵神經(jīng)網(wǎng)絡(luò)算法可以完成區(qū)域遍歷，是一種有效的區(qū)域遍歷方法。