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

錢金偉，戴曉強，高宏博，朱延栓

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

1 引言

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

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

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

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

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

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

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

(1)

(2)

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

圖1 二維生物激勵神經(jīng)網(wǎng)絡結構

2.2 路徑規(guī)劃算法

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

機器人柵格地圖的位置pc已知，下個時刻的位置表示為

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

(3)

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

yj=1-Δθj/π

(4)

這里Δθj∈[0，π]，是指當前時刻和下個時刻的方向角改變的絕對值大小。Δθj定義如下

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

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

(5)

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

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

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

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

3.1 內螺旋算法

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

圖2 內螺旋覆蓋算法路徑示意圖

3.2 A*算法

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

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

(6)

式中：F(n)即為A*算法對于每個節(jié)點的評估函數(shù)[12]，包含兩個子函數(shù)：G(n)是從起點到當前位置的n運行代價，即從起點至目前所在位置的移動距離長度；H(n)是從當前位置n至目標點的運行代價，即當前節(jié)點到目標點的移動距離長度。

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

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

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

(7)

即歐氏平面幾何距離為在直角坐標系中兩個坐標軸上的投影距離之和。

3.3 改進算法

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

機器人旋轉角度為

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

(8)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 仿真及分析

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

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

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

圖5 運行內螺旋覆蓋算法

圖6 運行A*算法脫困

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

圖7 生物激勵重復覆蓋路徑

圖8 內螺旋搜索重復覆蓋路徑圖

圖9 生物激勵算法路徑圖

圖10 內螺旋搜索算法路徑圖

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

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

5 結束語

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