基于內(nèi)螺旋搜索的生物激勵(lì)遍歷路徑規(guī)劃算法

錢金偉，戴曉強(qiáng)，高宏博，朱延栓

(江蘇科技大學(xué)，江蘇鎮(zhèn)江 212003)

1 引言

隨著海洋探索事業(yè)的不斷發(fā)展，海洋資源開發(fā)及海洋探索搜救成為必需，但是由于水下環(huán)境未知，人類下潛深度有限及操作風(fēng)險(xiǎn)高等原因，需要水下機(jī)器人替代人類進(jìn)行水下探索及搜救作業(yè)。水下機(jī)器人通過岸上操作臺(tái)進(jìn)行控制，通過自身搭載的聲吶、深度計(jì)、加速度計(jì)及水下云臺(tái)等傳感器采集水下數(shù)據(jù)并實(shí)時(shí)傳輸至岸上操作臺(tái)，從而達(dá)到觀測(cè)水下環(huán)境，探索水下資源的功能。因此，對(duì)于水下機(jī)器人移動(dòng)路徑規(guī)劃及避障的研究有利于推進(jìn)海洋資源開發(fā)、海洋工程結(jié)構(gòu)探傷及人員搜救方面的應(yīng)用。

目前，水下機(jī)器人路徑規(guī)劃分為兩種，一種是規(guī)劃出一條從起點(diǎn)至目標(biāo)點(diǎn)能夠避開所有障礙物的最優(yōu)路徑，另一種是在已知水下環(huán)境信息的情況下，規(guī)劃出一條能夠遍歷地圖的全局路徑。全局路徑規(guī)劃方法主要有人工勢(shì)場(chǎng)法，但是人工勢(shì)場(chǎng)法也存在著固有缺陷：局部極小值引起的陷阱區(qū)域問題；存在相近障礙物時(shí)難以發(fā)現(xiàn)移動(dòng)路徑；目標(biāo)點(diǎn)附近存在障礙物時(shí)無法到達(dá)目標(biāo)點(diǎn)；在障礙物前振蕩[1]。隨機(jī)路徑規(guī)劃方法是由Goodman和Heathcote提出在未知地圖環(huán)境中的遍歷路徑規(guī)劃方法[2]。該方法控制機(jī)器人以設(shè)定角度直線行走，直至到達(dá)規(guī)定時(shí)間或者觸碰到障礙物后，隨機(jī)選擇角度旋轉(zhuǎn)后繼續(xù)直線行走。該方法簡(jiǎn)單易實(shí)現(xiàn)，但缺點(diǎn)是無法確保地圖的完全遍歷。通過重復(fù)執(zhí)行隨機(jī)算法可以提高地圖的覆蓋率，但也會(huì)浪費(fèi)搜索時(shí)間及增加運(yùn)行路徑[3]。Simon X.Yang提出的一種基于生物激勵(lì)的神經(jīng)網(wǎng)絡(luò)算法[4](BINN算法)，在未知地圖環(huán)境信息時(shí)依舊可以遍歷整個(gè)地圖環(huán)境，遍歷路徑過程中不需要學(xué)習(xí)過程，也可解決存在動(dòng)態(tài)障礙物情況下的路徑規(guī)劃。雖然該方法在全覆蓋路徑規(guī)劃中有一定優(yōu)勢(shì)，但是也存在著一些不足，如當(dāng)難以脫離死區(qū)，需要等待周圍神經(jīng)元活性值降低后才可逃脫死區(qū)，規(guī)劃路徑轉(zhuǎn)彎次數(shù)太多，子區(qū)域之間的路徑規(guī)劃并非最短等。

本文在生物激勵(lì)神經(jīng)網(wǎng)絡(luò)算法(BINN算法)的基礎(chǔ)上，結(jié)合內(nèi)螺旋覆蓋算法與A*算法的優(yōu)點(diǎn)，提出了基于內(nèi)螺旋搜索的生物激勵(lì)遍歷路徑規(guī)劃算法，有效解決了重復(fù)覆蓋率高、脫離死區(qū)時(shí)間長(zhǎng)、分離區(qū)域路徑規(guī)劃不是最優(yōu)的問題，優(yōu)化了規(guī)劃路徑質(zhì)量。

2 基于BINN的遍歷路徑規(guī)劃算法

1952年，著名的生物物理學(xué)家Hodgkin和Huxley提出了神經(jīng)細(xì)胞膜的著名電路模型和描述細(xì)胞膜的動(dòng)力學(xué)方程(H-H模型[5])。Grossberg在H-H模型的基礎(chǔ)上總結(jié)并開發(fā)了該模型，提出了分流模型，并將其應(yīng)用于生物和機(jī)器視覺，傳感和運(yùn)動(dòng)控制以及其它應(yīng)用領(lǐng)域[6]。Yang和Meng于2001年根據(jù)Crossberg提出的神經(jīng)動(dòng)力學(xué)網(wǎng)絡(luò)模型，將生物激勵(lì)神經(jīng)網(wǎng)絡(luò)應(yīng)用于移動(dòng)機(jī)器人的地圖環(huán)境建模和路徑規(guī)劃，實(shí)驗(yàn)結(jié)果顯示取得了很好的效果[7]。

2.1 生物激勵(lì)神經(jīng)網(wǎng)絡(luò)模型

在生物激勵(lì)神經(jīng)網(wǎng)絡(luò)中，神經(jīng)元的活性值大小決定機(jī)器人的運(yùn)動(dòng)路徑。神經(jīng)元初始值為0，神經(jīng)元的變化值由分流方程(Shunting Equations)決定[8]

(1)

(2)

μ和r0都是正常數(shù)。每個(gè)神經(jīng)元僅與半徑為r0的圓內(nèi)的神經(jīng)元有直接聯(lián)系，權(quán)系數(shù)ωij是對(duì)稱的，生物激勵(lì)神經(jīng)網(wǎng)絡(luò)模型如圖1所示。

圖1 二維生物激勵(lì)神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)

2.2 路徑規(guī)劃算法

Yang和Luo在移動(dòng)機(jī)器人的全覆蓋路徑規(guī)劃領(lǐng)域，針對(duì)靜態(tài)已知環(huán)境與動(dòng)態(tài)未知環(huán)境的情況下對(duì)生物激勵(lì)神經(jīng)網(wǎng)絡(luò)進(jìn)行了研究[9]。以下為路徑規(guī)劃算法。

機(jī)器人柵格地圖的位置pc已知，下個(gè)時(shí)刻的位置表示為

pn?xpn=max{xj+cyj，j=1，2，…k}

(3)

c為一個(gè)正常數(shù)，k為以當(dāng)前位置為圓心，設(shè)置長(zhǎng)度為鄰域半徑內(nèi)的神經(jīng)元的總數(shù)。yj定義為

yj=1-Δθj/π

(4)

這里Δθj∈[0，π]，是指當(dāng)前時(shí)刻和下個(gè)時(shí)刻的方向角改變的絕對(duì)值大小。Δθj定義如下

Δθj=|θj-θc|=atan 2(ypj-ypc，xpj-xpc)

-atan 2(ypc-ypp，xpc-xpp)

(5)

由上式可知yj是一個(gè)遞減函數(shù)，Δθj越大，yj值越小。

根據(jù)該路徑規(guī)劃方法，水下機(jī)器人的路徑生成過程具體如下：首先從起始點(diǎn)開始，機(jī)器人朝著設(shè)定的方向行進(jìn)，同時(shí)不斷計(jì)算所在柵格神經(jīng)元鄰域內(nèi)的其它神經(jīng)元的活性值，若周圍的其它神經(jīng)元活性值相等，則機(jī)器人根據(jù)路徑規(guī)劃算法及生物激勵(lì)神經(jīng)網(wǎng)絡(luò)算法的權(quán)值比較選擇下一個(gè)位置的行進(jìn)方向，默認(rèn)行進(jìn)方向直行，否則下一個(gè)位置為設(shè)置鄰域范圍內(nèi)最大神經(jīng)元的位置，當(dāng)機(jī)器人觸碰到障礙物時(shí)，機(jī)器人根據(jù)路徑規(guī)劃方法選擇旋轉(zhuǎn)的角度，當(dāng)機(jī)器人陷入死區(qū)時(shí)，機(jī)器人計(jì)算當(dāng)前柵格鄰域內(nèi)其它柵格的神經(jīng)元活性值，若均小于等于所處位置的柵格神經(jīng)元活性值，則機(jī)器人維持原狀不動(dòng)，否則機(jī)器人移動(dòng)至活性值最大的位置，如此直到完成區(qū)域的全覆蓋。

該路徑規(guī)劃方法能夠應(yīng)用在存在死角及障礙物多的情況，也能夠運(yùn)用在存在動(dòng)態(tài)障礙物的情形，能夠遍歷地圖內(nèi)的所有空間。但是該路徑規(guī)劃方法缺點(diǎn)即路徑重復(fù)，在從死區(qū)逃脫到下一個(gè)遍歷區(qū)域的路徑不是最短，搜索時(shí)間長(zhǎng)，搜索效率低。

3 基于內(nèi)螺旋搜索的生物激勵(lì)遍歷路徑規(guī)劃算法

3.1 內(nèi)螺旋算法

內(nèi)螺旋覆蓋算法是由Butler等人提出來的[10]，該算法的覆蓋流程具體如下：移動(dòng)機(jī)器人按照設(shè)定的初始方向沿著順時(shí)鐘或者逆時(shí)針方向運(yùn)行，當(dāng)前方無障礙物時(shí)，機(jī)器人保持直線行駛，當(dāng)遇到障礙物時(shí)，機(jī)器人按順時(shí)針或者逆時(shí)針旋轉(zhuǎn)90度后繼續(xù)行駛，如此往復(fù)，完成整個(gè)區(qū)域的覆蓋。覆蓋路徑圖如圖2所示。

圖2 內(nèi)螺旋覆蓋算法路徑示意圖

3.2 A*算法

A*算法結(jié)合Dijkstra算法與傳統(tǒng)BFS(廣度優(yōu)先搜索算法)算法[11]，通過求解當(dāng)前節(jié)點(diǎn)到起點(diǎn)的路徑代價(jià)與當(dāng)前節(jié)點(diǎn)至目標(biāo)點(diǎn)的路徑代價(jià)之和，對(duì)周圍的搜索位置進(jìn)行評(píng)估，得到最好的位置，以此求解起點(diǎn)至終點(diǎn)的最短路徑。其啟發(fā)函數(shù)采用的代價(jià)計(jì)算公式如下

F(n)=G(n)+H(n)

(6)

式中：F(n)即為A*算法對(duì)于每個(gè)節(jié)點(diǎn)的評(píng)估函數(shù)[12]，包含兩個(gè)子函數(shù)：G(n)是從起點(diǎn)到當(dāng)前位置的n運(yùn)行代價(jià)，即從起點(diǎn)至目前所在位置的移動(dòng)距離長(zhǎng)度；H(n)是從當(dāng)前位置n至目標(biāo)點(diǎn)的運(yùn)行代價(jià)，即當(dāng)前節(jié)點(diǎn)到目標(biāo)點(diǎn)的移動(dòng)距離長(zhǎng)度。

A*算法的路徑搜索過程還需要兩個(gè)表：OPEN表和CLOSE表，OPEN表存儲(chǔ)經(jīng)過代價(jià)計(jì)算后F值最小的下一個(gè)節(jié)點(diǎn)，CLOSE存儲(chǔ)已完成訪問的節(jié)點(diǎn)。

H(n)是A*算法的距離估計(jì)值，A*算法需要一個(gè)距離評(píng)估函數(shù)來計(jì)算這個(gè)值。由于使用柵格地圖法進(jìn)行水下環(huán)境建模，曼哈頓距離函數(shù)較為合適，從數(shù)學(xué)上描述，曼哈頓距離是當(dāng)前點(diǎn)至目標(biāo)點(diǎn)在各個(gè)坐標(biāo)軸上的距離差值的和，對(duì)于二維平面上的兩個(gè)點(diǎn)(x1，y1)與(x2，y2)來說，其曼哈頓距離為

D=|x1-x2|+|y1-y2|

(7)

即歐氏平面幾何距離為在直角坐標(biāo)系中兩個(gè)坐標(biāo)軸上的投影距離之和。

3.3 改進(jìn)算法

水下機(jī)器人運(yùn)行生物激勵(lì)神經(jīng)網(wǎng)絡(luò)算法遍歷整個(gè)柵格地圖，根據(jù)負(fù)值神經(jīng)元活性值提取出障礙物的X、Y軸信息并存入ZHANGAI表中，需要進(jìn)行覆蓋的柵格神經(jīng)元活性值逐漸增長(zhǎng)，柵格信息存入DITU表中，已覆蓋的柵格信息存入LUJING表中運(yùn)行估計(jì)代價(jià)h存入DAIJIA表中。水下機(jī)器人運(yùn)行基于BINN的路徑規(guī)劃算法，根據(jù)柵格地圖的活性值進(jìn)行地圖覆蓋，當(dāng)機(jī)器人觸碰到障礙物柵格或者已覆蓋路徑時(shí)，開始運(yùn)行改進(jìn)算法。

機(jī)器人旋轉(zhuǎn)角度為

i=Δθ/π(Δθ∈{-π/2，π/2})

(8)

求得的i存入JIAODU表中，當(dāng)i的值為-1/2時(shí)，表示機(jī)器人在當(dāng)前行進(jìn)方向上右轉(zhuǎn)，1/2時(shí)表示機(jī)器人左轉(zhuǎn)，本文中機(jī)器人根據(jù)當(dāng)前所在位置選擇旋轉(zhuǎn)方向。如圖3所示。

圖3 (x，y)坐標(biāo)周圍信息

當(dāng)機(jī)器人從下向上運(yùn)行時(shí)，即從(x，y-1)向(x，y)方向運(yùn)行，由(x-1，y+1)至(x+1，y+1)為障礙物，機(jī)器人通過神經(jīng)元活性值選擇向(x-1，y)或(x+1，y)行進(jìn)；

當(dāng)機(jī)器人從上向下運(yùn)行時(shí)，即從(x，y+1)向(x，y)方向運(yùn)行，由(x-1，y-1)至(x+1，y-1)為障礙物，機(jī)器人通過神經(jīng)元活性值選擇向(x-1，y)或(x+1，y)行進(jìn)；

當(dāng)機(jī)器人從左向右運(yùn)行時(shí)，即從(x-1，y)向(x，y)方向運(yùn)行，由(x+1，y-1)至(x+1，y+1)為障礙物，機(jī)器人通過神經(jīng)元活性值選擇向(x，y+1)或(x，y-1)行進(jìn)；

當(dāng)機(jī)器人從右向左運(yùn)行時(shí)，即從(x+1，y)向(x，y)方向運(yùn)行，由(x-1，y-1)至(x-1，y+1)為障礙物，機(jī)器人通過神經(jīng)元活性值選擇向(x，y+1)或(x，y-1)行進(jìn)；

上述機(jī)器人旋轉(zhuǎn)后的角度i存入JIAODU表中，在機(jī)器人完成矩形區(qū)域遍歷陷入死區(qū)前，下一步的旋轉(zhuǎn)方向均為角度i。

機(jī)器人陷入死區(qū)時(shí)進(jìn)行脫困運(yùn)行A*算法，算法具體實(shí)現(xiàn)如下：

Step1：初始化建立一個(gè)OPEN表與CLOSE表，將當(dāng)前節(jié)點(diǎn)作為起點(diǎn)S加入OPEN表中，搜索建立的DITU表與LUJING表，尋找DITU表中未完成覆蓋且距離當(dāng)前節(jié)點(diǎn)最近的點(diǎn)，將該節(jié)點(diǎn)作為目標(biāo)點(diǎn)G，估計(jì)代價(jià)起點(diǎn)S至目標(biāo)點(diǎn)G的距離，估計(jì)函數(shù)選擇曼哈頓距離函數(shù)，左、右、上、下的柵格估計(jì)代價(jià)均為柵格距離1，左上、右上、左下、右下的柵格估計(jì)代價(jià)為柵格距離2，估計(jì)代價(jià)函數(shù)h(n)=length(n，G)，n表示當(dāng)前節(jié)點(diǎn)，當(dāng)前節(jié)點(diǎn)計(jì)算完成后，將當(dāng)前節(jié)點(diǎn)n加入到CLOSE表中，選擇周圍F值最小的柵格n+1作為子節(jié)點(diǎn)加入到OPEN表中；

Step2：判斷OPEN表是否為空，是則轉(zhuǎn)移到Step5，否則繼續(xù)執(zhí)行；

Step3：判斷n+1節(jié)點(diǎn)是否為目標(biāo)點(diǎn)G，是則轉(zhuǎn)到Step5，否則轉(zhuǎn)到Step4；

Step4：計(jì)算n+1節(jié)點(diǎn)至G的估計(jì)代價(jià)h(n+1)=length(n+1，G)，取n+1節(jié)點(diǎn)周圍估計(jì)代價(jià)最小的節(jié)點(diǎn)n+2作為子節(jié)點(diǎn)加入到OPEN表中，將n+1節(jié)點(diǎn)加入到CLOSE表中，轉(zhuǎn)到Step2；

Step5：從G點(diǎn)搜索子節(jié)點(diǎn)鏈直至S點(diǎn)，最優(yōu)路徑搜索完成，算法結(jié)束。

機(jī)器人脫困后，繼續(xù)運(yùn)行基于BINN的路徑規(guī)劃算法，并通過內(nèi)螺旋算法與A*算法完成局部遍歷脫困，如此完成整個(gè)柵格地圖的覆蓋。

4 仿真及分析

在MATLAB仿真環(huán)境下，設(shè)置水下環(huán)境為30×20的二維柵格地圖(如下圖4所示)，環(huán)境中的障礙物信息已知，水下機(jī)器人起始位置是(1，20)，考慮到水下環(huán)境中會(huì)出現(xiàn)U形區(qū)域，柵格地圖設(shè)置了U形障礙及不規(guī)則障礙物。水下機(jī)器人的任務(wù)是從起點(diǎn)出發(fā)，按照最小重復(fù)覆蓋率完成對(duì)整個(gè)柵格地圖的遍歷，同時(shí)運(yùn)行路徑盡可能短。生物激勵(lì)神經(jīng)網(wǎng)絡(luò)參數(shù)設(shè)置為：A=10，B=1，D=1，μ=0.05，權(quán)值占比c=0.5，神經(jīng)元鄰域半徑r0=1.5，能夠覆蓋周圍8個(gè)神經(jīng)元，即k=8(Willms and Yang 2006)[13]。設(shè)置神經(jīng)元活性值最大為0.9，障礙物活性值最低為-0.9。

圖4 水下環(huán)境柵格地圖

圖5是采用改進(jìn)路徑規(guī)劃算法后內(nèi)螺旋算法覆蓋部分與脫困示意圖，機(jī)器人在運(yùn)行至(7，28)時(shí)，開始運(yùn)行內(nèi)螺旋覆蓋算法，完成矩形區(qū)域的遍歷后，機(jī)器人運(yùn)行A*算法脫困，如圖6所示。

圖5 運(yùn)行內(nèi)螺旋覆蓋算法

圖6 運(yùn)行A*算法脫困

圖7是按照生物激勵(lì)神經(jīng)網(wǎng)絡(luò)算法運(yùn)行后的重復(fù)路徑圖，其中，綠色圓形為起點(diǎn)，藍(lán)色正方形為重復(fù)覆蓋柵格，白色正方形表示機(jī)器人經(jīng)過生物激勵(lì)神經(jīng)網(wǎng)絡(luò)無法搜索到的未知區(qū)域，黑色正方形表示障礙物，紅色三角形為已覆蓋的柵格，比較圖8內(nèi)螺旋搜索重復(fù)路徑圖，可以看出兩種算法均完成了100%的遍歷覆蓋率，但是內(nèi)螺旋搜索在重復(fù)覆蓋率上相比較原生物激勵(lì)神經(jīng)網(wǎng)絡(luò)算法有很大的降低。

圖7 生物激勵(lì)重復(fù)覆蓋路徑

圖8 內(nèi)螺旋搜索重復(fù)覆蓋路徑圖

圖9 生物激勵(lì)算法路徑圖

圖10 內(nèi)螺旋搜索算法路徑圖

圖9為機(jī)器人運(yùn)行生物激勵(lì)神經(jīng)網(wǎng)絡(luò)生成的運(yùn)動(dòng)路徑圖，圖10為機(jī)器人基于內(nèi)螺旋搜索的生物激勵(lì)遍歷路徑規(guī)劃算法的運(yùn)動(dòng)路徑圖，從圖中可以看出，相比較傳統(tǒng)基于生物激勵(lì)神經(jīng)網(wǎng)絡(luò)的路徑規(guī)劃，基于內(nèi)螺旋搜索的生物激勵(lì)神經(jīng)網(wǎng)絡(luò)遍歷路徑規(guī)劃在運(yùn)行路徑長(zhǎng)度上要更短。表1列出了兩種算法在相同條件下的各種性能指標(biāo)上的差異。

表1 兩種算法參數(shù)比較圖

5 結(jié)束語(yǔ)

本文提出的基于內(nèi)螺旋搜索的生物激勵(lì)神經(jīng)網(wǎng)絡(luò)遍歷路徑規(guī)劃算法能優(yōu)先解決基于生物激勵(lì)的全覆蓋路徑規(guī)劃算法的重復(fù)覆蓋率高、分離區(qū)域間路徑規(guī)劃不是最優(yōu)、脫離死區(qū)時(shí)間長(zhǎng)的問題。在相同仿真條件下，及遍歷覆蓋率是100%的基礎(chǔ)上，相對(duì)于基于生物激勵(lì)神經(jīng)網(wǎng)絡(luò)路徑規(guī)劃算法，本文提出的算法在重復(fù)覆蓋率、運(yùn)行時(shí)間、路徑長(zhǎng)度指標(biāo)上均有明顯提高，表示該方法具有一定的優(yōu)越性和有效性。