趙文勇，王丹丹，徐守祥，張 瑞，馬 超

（深圳信息職業(yè)技術(shù)學(xué)院，廣東 深圳 518172）

引言

未知環(huán)境下的完全遍歷路徑規(guī)劃是移動(dòng)機(jī)器人自主導(dǎo)航中的一個(gè)重要問題。當(dāng)機(jī)器人工作在未知環(huán)境下，為了完全遍歷工作空間，需要實(shí)時(shí)構(gòu)建地圖和動(dòng)態(tài)路徑規(guī)劃。常見的完全遍歷路徑規(guī)劃方法有人工勢(shì)場(chǎng)法、模板模型法、神經(jīng)網(wǎng)絡(luò)算法等[1-4,12]。

傳統(tǒng)的人工勢(shì)場(chǎng)法[2]通過構(gòu)造虛擬引力場(chǎng)和斥力場(chǎng)引導(dǎo)機(jī)器人向目標(biāo)運(yùn)動(dòng)。該方法在實(shí)時(shí)避障和平滑軌跡控制方面得到廣泛應(yīng)用，但該方法存在一些缺陷：在處理局部最優(yōu)解時(shí)，容易產(chǎn)生死鎖；在靠近障礙物時(shí)容易震蕩；在狹窄通道中擺動(dòng)；存在陷阱區(qū)域等。

Hofner和Schmidt[3]提出的模板模型法需要事先定義好典型模板，因此該方法不適于處理動(dòng)態(tài)變化的環(huán)境。

Simon X. Yang 提出了一種基于生物激勵(lì)的神經(jīng)網(wǎng)絡(luò)算法[4]，機(jī)器人在利用有限的傳感器信息進(jìn)行路徑規(guī)劃時(shí)，通過神經(jīng)動(dòng)力學(xué)建立了由正方形或矩形單元組成的環(huán)境地圖。該方法與其它模型相比，不需要先驗(yàn)地圖，不需要學(xué)習(xí)過程，不需要搜索全局自由空間，不需要精確計(jì)算代價(jià)函數(shù)，因此獲得了廣泛的應(yīng)用。雖然該方法在完全遍歷路徑規(guī)劃中有一定的優(yōu)勢(shì)，但也存在一些不足，如分離區(qū)域之間的路徑非最優(yōu)等。

本文在生物激勵(lì)神經(jīng)網(wǎng)絡(luò)算法的基礎(chǔ)上，結(jié)合回溯算法（Backtracking Algorithm[5]）與D*算法（D Star[6][7]）的優(yōu)點(diǎn)，提出了基于回溯搜索的生物激勵(lì)完全遍歷路徑規(guī)劃方法。通過仿真比較，該方法相較于基于生物激勵(lì)神經(jīng)網(wǎng)絡(luò)的完全遍歷路徑規(guī)劃方法在覆蓋重疊率與轉(zhuǎn)向次數(shù)等性能指標(biāo)上得到了改善與提高。

1 基于生物激勵(lì)神經(jīng)網(wǎng)絡(luò)的路徑規(guī)劃算法

1952年，生物物理學(xué)家Hodgkin和Huxley提出了著名的神經(jīng)細(xì)胞膜電路模型(membrane model[8])和描述該模型的細(xì)胞膜動(dòng)力方程（H-H模型[8]）。Grossberg在該模型的基礎(chǔ)上總結(jié)和發(fā)展出了分流方程（shunting cooperative competitive feedback network，簡(jiǎn)稱Shunting Equation[9]，又稱逃避方程），并將其應(yīng)用于機(jī)器視覺和感覺運(yùn)動(dòng)控制系統(tǒng)。Simon X. Yang將Shunting Equation應(yīng)用于移動(dòng)機(jī)器人運(yùn)動(dòng)的環(huán)境建模和路徑規(guī)劃，得到了很好的效果。

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

Grossberg提出的分流方程形式如下：

圖1 神經(jīng)元連接示意圖Fig.1 The illustration of the neuron connection

1.2 路徑規(guī)劃算法

在基于生物激勵(lì)的神經(jīng)網(wǎng)絡(luò)模型中，機(jī)器人的路徑由狀態(tài)方程及上一時(shí)刻所處的位置決定。給定機(jī)器人的當(dāng)前位置，假設(shè)下個(gè)時(shí)刻的位置為，則按下式確定：

當(dāng)機(jī)器人從當(dāng)前位置到達(dá)下一個(gè)位置，下一個(gè)位置就變成新的當(dāng)前位置（如果找到下一位置與當(dāng)前位置一樣，機(jī)器人將不會(huì)移動(dòng)）。機(jī)器人下一時(shí)刻的位置根據(jù)變化著的環(huán)境作適應(yīng)性地變化。圖2是由算法（3）所產(chǎn)生的局部路徑，該地圖由30*23個(gè)柵格組成。機(jī)器人默認(rèn)按照從左到右，上下往返運(yùn)動(dòng)（back and forward[11]），機(jī)器人從S（3，2）出發(fā)，將經(jīng)過點(diǎn)D（14，2），最終到達(dá)終點(diǎn)E（29，8）。圖3表示機(jī)器人在D的活性直方圖，活性值最高的區(qū)域表示檢測(cè)到的尚未遍歷的區(qū)域，左邊活性值衰減到接近0的區(qū)域表示已覆蓋的區(qū)域，未知區(qū)域的活性值保持在0。從圖中可以看出該算法在遍歷過程中可將障礙物輪廓構(gòu)建出來。

圖2 機(jī)器人位于點(diǎn)(14,2)的路徑Fig.2 The robot at D(14,2)

圖3 機(jī)器人位于點(diǎn)(14,2)的活性直方圖Fig.3 The coverage path planning with the robot at D(14,2)

1.3 生物激勵(lì)神經(jīng)網(wǎng)絡(luò)的優(yōu)點(diǎn)

由式（1）和式（3）可知，神經(jīng)元狀態(tài)方程是一個(gè)與周圍神經(jīng)元有關(guān)的一階微分方程，路徑規(guī)劃則由神經(jīng)元活性及前一時(shí)刻的位置綜合決定，因此生物激勵(lì)神經(jīng)網(wǎng)絡(luò)算法模型很簡(jiǎn)單。該算法不需要先驗(yàn)地圖，機(jī)器人在利用有限的傳感器信息進(jìn)行路徑規(guī)劃時(shí)，建立了由正方形或矩形單元組成的局部地圖，因此該算法可以實(shí)時(shí)構(gòu)建環(huán)境地圖。此外，該算法能有效處理死鎖（deadlock）狀態(tài)。當(dāng)機(jī)器人陷入死鎖時(shí)，能按照活性值由高到低的方向退出死鎖，使得機(jī)器人不會(huì)陷入局部死循環(huán)。如在圖4中，機(jī)器人自A往下運(yùn)動(dòng)到D，點(diǎn)D鄰域內(nèi)的8個(gè)點(diǎn)要么已經(jīng)清掃，要么是障礙，機(jī)器人陷入死鎖。然而，由式（1）可知，神經(jīng)元活性方程是單調(diào)遞減函數(shù)，當(dāng)D的活性值衰減到低于C的活性值時(shí)，機(jī)器人將按從下到上的方向退出死鎖，直到再次搜索到未完全遍歷的位置B。圖4和圖5分別是遍歷完成的規(guī)劃路徑和活性直方圖。

圖4 完全遍歷路徑Fig.4 The coverage path planning

圖5 完全遍歷活性直方圖Fig.5 The histogram of coverage path planning

1.4 生物激勵(lì)神經(jīng)網(wǎng)絡(luò)的不足

雖然生物激勵(lì)神經(jīng)網(wǎng)絡(luò)具有諸多優(yōu)點(diǎn)，但也存在不足。當(dāng)機(jī)器人陷入死區(qū)時(shí)（如圖2所示）機(jī)器人需在該處等待，直到周圍的神經(jīng)元活性大于當(dāng)前神經(jīng)元活性時(shí)，才能繼續(xù)覆蓋下去。特別是對(duì)相距較遠(yuǎn)的分離區(qū)域時(shí)，未遍歷區(qū)域的高活性值在傳遞過程中可能衰減到0，或者傳遞到相鄰神經(jīng)元時(shí)活性值已經(jīng)低于當(dāng)前活性值，這將使得遍歷不完整或路徑非最優(yōu)。為方便說明，可構(gòu)建雙U型障礙地圖，如圖6所示，機(jī)器人運(yùn)行到點(diǎn)D（29，18）陷入死鎖狀態(tài)，此時(shí)還有3塊區(qū)域S1，S2，S3未遍歷。此時(shí)的活性直方圖如圖7所示。

由于S2與S3相隔較近，機(jī)器人在陷入死鎖點(diǎn)D時(shí)，等待一段時(shí)間后能逃離死區(qū)，機(jī)器人將從上到下運(yùn)行到S3區(qū)域，完成S3區(qū)域的遍歷。然而，當(dāng)機(jī)器人覆蓋完S3區(qū)域時(shí)，由于S1與S2離S3較遠(yuǎn)，區(qū)域之間的神經(jīng)元活性值衰減到接近0，S1對(duì)機(jī)器人缺乏引導(dǎo)作用，機(jī)器人最終的行走路徑較為混亂。圖8（a）為最終遍歷后的路徑，明顯存在很多重疊路徑。

2 基于回溯搜索的生物激勵(lì)算法

針對(duì)生物激勵(lì)神經(jīng)網(wǎng)絡(luò)存在的上述不足，本文提出了基于生物激勵(lì)神經(jīng)網(wǎng)絡(luò)與BT回溯算法及D*搜索算法相結(jié)合的基于回溯搜索的生物激勵(lì)算法。BT回溯算法可以實(shí)現(xiàn)快速定位目標(biāo)點(diǎn)，D*算法是求解動(dòng)態(tài)二維環(huán)境最短路徑的有效算法，將兩種算法與生物激勵(lì)神經(jīng)網(wǎng)絡(luò)結(jié)合，可以有效規(guī)劃出分離區(qū)域之間的最短路徑。

圖6 未遍歷區(qū)域S1,S2,S3Fig.6 The uncovered area S1,S2,S3

圖7 機(jī)器人位于點(diǎn)(29,18)的活性直方圖Fig.7 The histogram of activity at (29,18)

2.1 算法描述

首先利用生物激勵(lì)神經(jīng)網(wǎng)絡(luò)使機(jī)器人覆蓋工作空間，直到陷入死鎖。機(jī)器人在行走過程中構(gòu)建空間地圖，將檢測(cè)到的鄰域內(nèi)有未遍歷的點(diǎn)作為節(jié)點(diǎn)記錄下來，并按時(shí)間先后順序保存在節(jié)點(diǎn)隊(duì)列表中，同時(shí)剔除已遍歷節(jié)點(diǎn)。當(dāng)機(jī)器人陷入死鎖時(shí)，說明局部區(qū)域已經(jīng)遍歷完成。這時(shí)，將當(dāng)前點(diǎn)設(shè)置為起始點(diǎn)，從節(jié)點(diǎn)隊(duì)列中找到距當(dāng)前時(shí)間最近的節(jié)點(diǎn)作為下一個(gè)目標(biāo)點(diǎn)。再根據(jù)已經(jīng)構(gòu)建的環(huán)境地圖，由D*算法規(guī)劃出一條點(diǎn)到點(diǎn)的最短避障路徑，當(dāng)?shù)竭_(dá)目標(biāo)后，由于目標(biāo)點(diǎn)鄰域內(nèi)有未遍歷區(qū)域，機(jī)器人退出死鎖，并按照生物激勵(lì)神經(jīng)網(wǎng)絡(luò)算法遍歷該區(qū)域。由于D*算法能實(shí)時(shí)更新啟發(fā)函數(shù)，因此即使在點(diǎn)到點(diǎn)規(guī)劃過程中遇到未知障礙，也能輕松避障，并以最短路徑到達(dá)目標(biāo)點(diǎn)。當(dāng)節(jié)點(diǎn)隊(duì)列的節(jié)點(diǎn)數(shù)為0時(shí)，說明已經(jīng)沒有未遍歷節(jié)點(diǎn)，結(jié)束遍歷工作。

在算法中，定義狀態(tài)變量 ，表示神經(jīng)元在位置 的狀態(tài)，取值如下：

改進(jìn)后的算法包含以下四個(gè)方面：

（1）初始化階段：初始化算法目的是初始化機(jī)器人起點(diǎn)位置，將所有神經(jīng)元狀態(tài)置0，將節(jié)點(diǎn)隊(duì)列清空，限定地圖大小等。具體見算法1。

（2）地圖與節(jié)點(diǎn)隊(duì)列構(gòu)建階段：本階段主要依賴于機(jī)器人攜帶的傳感器。本算法假設(shè)環(huán)境完全未知，外部輸入 包含了機(jī)器人本身的狀態(tài)和周圍環(huán)境狀態(tài)。因此，機(jī)器人對(duì)整個(gè)空間只有有限的認(rèn)識(shí)。在未知的環(huán)境下，機(jī)器人朝活性最高且轉(zhuǎn)向最小的未清掃區(qū)域移動(dòng)，并實(shí)時(shí)建立地圖，直到完全覆蓋可達(dá)區(qū)域。同時(shí)，當(dāng)機(jī)器人檢測(cè)到存在節(jié)點(diǎn)時(shí)，將該節(jié)點(diǎn)保存在節(jié)點(diǎn)隊(duì)列，并移除已經(jīng)遍歷過的節(jié)點(diǎn)。

（3）全局路徑規(guī)劃階段：未清掃區(qū)域通過神經(jīng)活性傳播在整個(gè)狀態(tài)空間吸引機(jī)器人，而障礙只在小區(qū)域內(nèi)使機(jī)器人避免碰撞。算法2給出了覆蓋算法。該算法中，一旦機(jī)器人從當(dāng)前位置移到下一個(gè)位置，下一個(gè)位置就成為新的當(dāng)前位置，之前的位置被標(biāo)記為已覆蓋（見算法2）。下一個(gè)位置由神經(jīng)活性和轉(zhuǎn)向角確定。

（4）點(diǎn)到點(diǎn)路徑規(guī)劃階段：該階段的執(zhí)行并不是必須的，只有當(dāng)機(jī)器人陷入死鎖（如圖6所示S1、S2、S3）才需要執(zhí)行此階段。此時(shí)，取隊(duì)列中與當(dāng)前位置相隔時(shí)間最近的節(jié)點(diǎn)作為下一個(gè)位置，利用D*算法規(guī)劃最短路徑。

2.2 算法偽碼

算法1：初始化算法

算法2：覆蓋算法

//未完全遍歷，則將當(dāng)前節(jié)點(diǎn)加入隊(duì)列首位

（3）掃描隊(duì)列，移除已經(jīng)遍歷的節(jié)點(diǎn)；

//檢測(cè)周圍環(huán)境，設(shè)置標(biāo)志位和外部輸入

（6）判斷當(dāng)前狀態(tài)：

3 仿真研究

本文提出的基于回溯搜索的生物激勵(lì)完全遍歷算法能夠使機(jī)器人在沒有任何人工干預(yù)下自動(dòng)完成完全遍歷路徑規(guī)劃。利用該算法，在圖6所示的地圖下能實(shí)現(xiàn)完全遍歷路徑規(guī)劃，規(guī)劃出的路徑如圖8（b）所示。

圖8（b）中，黑色代表障礙物，藍(lán)色帶箭頭直線表示運(yùn)行方向，紅色點(diǎn)表示死鎖點(diǎn)，綠色點(diǎn)表示從死鎖點(diǎn)規(guī)劃到目標(biāo)節(jié)點(diǎn)的最短路徑。根據(jù)圖8（b）的三條綠色路徑，機(jī)器人在陷入死鎖后，從節(jié)點(diǎn)隊(duì)列中找到距當(dāng)前時(shí)間最近的未完全遍歷節(jié)點(diǎn)，并由D*算法規(guī)劃出一條最短路徑，進(jìn)而逃離死鎖。通過與圖6進(jìn)行直觀對(duì)比，可以發(fā)現(xiàn)本算法產(chǎn)生的路徑更加合理，更少陷入死鎖。表1是兩種算法在雙U型障礙下的性能指標(biāo)對(duì)比。在本例中，兩種算法均實(shí)現(xiàn)了100%的遍歷覆蓋率，轉(zhuǎn)彎次數(shù)上也不相上下，但在遍歷重疊率上，本文提出的算法明顯優(yōu)于基于生物激勵(lì)神經(jīng)網(wǎng)絡(luò)算法。

圖8 研究雙U型地圖下的完全遍歷路徑規(guī)劃仿真

表1 雙U型障礙下的性能指標(biāo)對(duì)比Tab.1 The performance comparison of the double-U map

上述雙U型障礙環(huán)境下的仿真實(shí)例，驗(yàn)證了本方法相對(duì)于生物激勵(lì)神經(jīng)網(wǎng)絡(luò)算法在性能指標(biāo)上能得到顯著改善和提高，而且規(guī)劃的路徑更為合理有效。本仿真所假設(shè)的環(huán)境比較規(guī)則，下面對(duì)環(huán)境更為復(fù)雜的情況進(jìn)行仿真研究。

圖9所示環(huán)境中，有U型障礙物、梯形障礙區(qū)、窄道和其他不規(guī)則障礙物，圖9（a）是采用文獻(xiàn)[2]提出的生物激勵(lì)神經(jīng)網(wǎng)絡(luò)算法所規(guī)劃的遍歷路徑。該路徑從起點(diǎn)S（2，2）開始遍歷，當(dāng)遍歷到R（36，14）時(shí)，陷入死鎖，利用生物激勵(lì)神經(jīng)網(wǎng)絡(luò)方法，機(jī)器人能沿著活性降低及轉(zhuǎn)角最小的方向移動(dòng)，當(dāng)運(yùn)行到T（31，26）時(shí)，檢測(cè)到未遍歷區(qū)域，進(jìn)入正常的路徑規(guī)劃階段；當(dāng)機(jī)器人運(yùn)行到U（36，34）時(shí)，再次陷入死鎖，機(jī)器人沿著活性降低和轉(zhuǎn)角最小的方向移動(dòng)，直到運(yùn)行到V（23，18）時(shí)，檢測(cè)到前方有障礙物，才更改方向向下運(yùn)動(dòng)。

圖9（b）是采用本文提出的基于回溯搜索的生物激勵(lì)算法所規(guī)劃出的路徑。當(dāng)機(jī)器人遍歷到R（36，14）時(shí)，陷入死鎖，利用回溯搜索算法，找到距離當(dāng)前時(shí)間最近的目標(biāo)點(diǎn)T（31，26）（如紅色帶箭頭直線指示），利用D*算法規(guī)劃出最短路徑，當(dāng)?shù)竭_(dá)T后，檢測(cè)到未遍歷區(qū)域，進(jìn)入正常的路徑規(guī)劃階段；當(dāng)機(jī)器人運(yùn)行到U（36，34）時(shí)，再次陷入死鎖，回溯搜索法找到目標(biāo)點(diǎn)V（33，35）。由路徑圖可以直觀看出，基于回溯搜索的生物激勵(lì)算法規(guī)劃出的路徑比生物激勵(lì)神經(jīng)網(wǎng)絡(luò)算法規(guī)劃出的路徑具有更短的遍歷長(zhǎng)度和更少的轉(zhuǎn)彎次數(shù)。表2列出了兩種算法在復(fù)雜環(huán)境下各種性能指標(biāo)上的差異。

（a）生物激勵(lì)神經(jīng)網(wǎng)絡(luò)產(chǎn)生的路徑

Fig9 The coverage path planning of the Asymmetry map圖9 復(fù)雜環(huán)境下的完全遍歷路徑規(guī)劃仿真研究

表2 復(fù)雜環(huán)境下的性能指標(biāo)對(duì)比Tab.2 The performance comparision of the Asymmetry map

4 結(jié)束語

本文提出的基于回溯搜索的生物激勵(lì)完全遍歷路徑規(guī)劃算法能有效實(shí)現(xiàn)動(dòng)態(tài)障礙物和不確定環(huán)境下的完全遍歷路徑規(guī)劃問題。在兩組較為典型的環(huán)境情形下，將本文提出的算法與基于生物激勵(lì)的神經(jīng)網(wǎng)絡(luò)方法進(jìn)行比較研究，結(jié)果表明，本方法在轉(zhuǎn)彎次數(shù)、遍歷重疊率、遍歷長(zhǎng)度等指標(biāo)上都有明顯的提高，不僅保證了完全遍歷所有可達(dá)空間，而且優(yōu)化了運(yùn)行軌跡，減少了重覆蓋率，顯示了該方法具有一定的優(yōu)越性和有效性。下一步的研究工作將考慮把本方法應(yīng)用于動(dòng)態(tài)障礙物與不確定環(huán)境下的多機(jī)器人協(xié)同工作，實(shí)現(xiàn)完全遍歷路徑規(guī)劃問題。