呂戰(zhàn)永，曹江濤

LV Zhanyong,CAO Jiangtao

遼寧石油化工大學(xué) 信息與控制工程學(xué)院，遼寧 撫順 113001

School of Information and Control Engineering,Liaoning Shihua University,Fushun,Liaoning 113001,China

1 引言

路徑規(guī)劃是移動(dòng)機(jī)器人自主導(dǎo)航的關(guān)鍵技術(shù)之一。移動(dòng)機(jī)器人路徑規(guī)劃是指在有障礙物的工作環(huán)境中，尋找一條從給定起點(diǎn)到終點(diǎn)的適當(dāng)運(yùn)動(dòng)路徑，使機(jī)器人在運(yùn)動(dòng)過(guò)程中能安全、無(wú)碰地繞過(guò)所有障礙物。移動(dòng)機(jī)器人的路徑規(guī)劃方法可分為基于地圖的全局路徑規(guī)劃和基于傳感器的局部路徑規(guī)劃[1]。

人工勢(shì)場(chǎng)法，遺傳算法，人工神經(jīng)網(wǎng)絡(luò)等是現(xiàn)在運(yùn)用在機(jī)器人全局路徑規(guī)劃中比較成功的算法。傳統(tǒng)的人工勢(shì)場(chǎng)法存在幾大缺陷：在相近的障礙物之間存在盲區(qū)不能發(fā)現(xiàn)路徑；當(dāng)目標(biāo)點(diǎn)附近處有障礙物時(shí)機(jī)器人無(wú)法到達(dá)目標(biāo)點(diǎn)[2]。遺傳算法在環(huán)境中存在大量復(fù)雜的不規(guī)則障礙物時(shí)運(yùn)算速度很慢。一些傳統(tǒng)神經(jīng)網(wǎng)絡(luò)模型需要學(xué)習(xí)并且僅能處理在靜態(tài)環(huán)境下的情況[3]。SimonX.Yang提出了生物激勵(lì)神經(jīng)網(wǎng)（Biologically Inspired Neural Network，BINN）路徑規(guī)劃方法來(lái)解決動(dòng)態(tài)環(huán)境中生成實(shí)時(shí)的避障路徑，它不需要學(xué)習(xí)過(guò)程，并且在網(wǎng)絡(luò)結(jié)構(gòu)中各神經(jīng)元之間只存在局部的側(cè)連接，計(jì)算速度較快因此能對(duì)動(dòng)態(tài)環(huán)境中的變化作出迅速反應(yīng)[4-5]。但是這種方法也存在靜態(tài)路徑規(guī)劃中所得路徑不是最優(yōu)或者次優(yōu)路徑，在一些復(fù)雜動(dòng)態(tài)環(huán)境中對(duì)動(dòng)態(tài)目標(biāo)追蹤效果不理想的情況。文中針對(duì)這些情況，提出了帶自反饋的BINN，并引入了新的權(quán)值函數(shù)求取方法。與原方法比在多個(gè)指標(biāo)上得到了改善。

2 BINN路徑規(guī)劃原理

1999年SimonX.Yang把BINN應(yīng)用在機(jī)器人路徑規(guī)劃上，它的應(yīng)用原理是將移動(dòng)機(jī)器人的運(yùn)動(dòng)空間映射為由BINN組成的拓?fù)錉顟B(tài)空間，其中每一個(gè)神經(jīng)元活性值變化由方程（1）來(lái)求取。

式中，xi為第i個(gè)神經(jīng)元的激活值，A為正常數(shù)，代表衰減率，B為神經(jīng)元活性值的上界，-D為神經(jīng)元活性值的下界，Ii為第i個(gè)神經(jīng)元的外部輸入，k為第i個(gè)神經(jīng)個(gè)神經(jīng)元的激勵(lì)輸入，S-=(D+xi)[xi]-表示抑制輸入。ωij為第 j個(gè)神經(jīng)元到第i個(gè)神經(jīng)元的連接權(quán)，計(jì)算公式如式（2）所示：

式中，|qi-qj|為相鄰神經(jīng)元qi和qj之間的歐氏距離，μ和r為正的常數(shù)，顯然ωij=ωji，即ωij和ωji是對(duì)稱(chēng)的，非線性門(mén)限值函數(shù)為：

通過(guò)上述一組方程，經(jīng)過(guò)一定次數(shù)的迭代計(jì)算就能得到BINN拓?fù)淇臻g的神經(jīng)元活性值狀態(tài)圖，沿著活性值的最大梯度上升方向就能找到一條由起點(diǎn)到目標(biāo)點(diǎn)的路徑[4-6]。

3 基于自反饋BINN的建模及路徑規(guī)劃

3.1 提出自反饋BINN的原因

BINN雖然有許多優(yōu)點(diǎn)但是也存在不足。

圖1是BINN在靜態(tài)環(huán)境下的路徑規(guī)劃仿真，發(fā)現(xiàn)在路徑規(guī)劃的過(guò)程中BINN路徑規(guī)劃方法在多個(gè)地方出現(xiàn)了波浪形路徑，造成了路徑的加長(zhǎng)從而使得路徑不是最優(yōu)或者次優(yōu)。

圖1 BINN在靜態(tài)環(huán)境中的路徑生成

圖2 （a）是BINN方法在追蹤動(dòng)態(tài)目標(biāo)時(shí)的路徑生成，機(jī)器人和目標(biāo)的運(yùn)動(dòng)速度相同，由于機(jī)器人對(duì)運(yùn)動(dòng)目標(biāo)的追蹤不夠靈敏，因此當(dāng)運(yùn)動(dòng)目標(biāo)到達(dá)終點(diǎn)時(shí)機(jī)器人都無(wú)法對(duì)運(yùn)動(dòng)目標(biāo)進(jìn)行無(wú)差別跟蹤。

3.2 自反饋BINN

針對(duì)上面的問(wèn)題，提出了自反饋BINN，它有兩項(xiàng)改進(jìn)：

圖2 兩種算法對(duì)運(yùn)動(dòng)目標(biāo)的追蹤

第一：在神經(jīng)元上增加一個(gè)自反饋鏈接設(shè)計(jì)了自反饋權(quán)值函數(shù)求取方法，增強(qiáng)其前一刻的活性值狀態(tài)對(duì)下一刻的影響，從而起到抑制波浪形路徑產(chǎn)生的作用。自反饋BINN活性值方程如下：在式（5）中a為一個(gè)常數(shù)，ω為自反饋權(quán)值函數(shù)，由式（6）可知當(dāng)神經(jīng)元當(dāng)前時(shí)刻激活值和前一刻激活值之差的絕對(duì)值增大時(shí)，自反饋權(quán)值ω就會(huì)變小，使最終的激活值不會(huì)出現(xiàn)激烈的變化，從而避免了圖1中所出現(xiàn)的因激活值突變而形成的波浪形的不平滑路徑。

第二：權(quán)值大小與神經(jīng)元距離之間的關(guān)系并不是簡(jiǎn)單的線性關(guān)系，而是一種復(fù)雜的非線性關(guān)系，因此采用了文獻(xiàn)[7]中所用的指數(shù)型的求取方法，從而增強(qiáng)算法對(duì)運(yùn)動(dòng)目標(biāo)的追蹤能力，其權(quán)值求取方式如式（7）：

式中，β為正常數(shù)，其他參數(shù)與BINN相同。

在增加自反饋和新的權(quán)值求取方式后算法能夠?qū)\(yùn)動(dòng)的目標(biāo)進(jìn)行無(wú)差別的跟蹤如圖2（b）所示，機(jī)器人經(jīng)過(guò)簡(jiǎn)單的變向之后就可以無(wú)差別地跟蹤運(yùn)動(dòng)的目標(biāo)。

3.3 基于自反饋BINN模型的環(huán)境建模

進(jìn)行機(jī)器人路徑規(guī)劃首先要對(duì)機(jī)器人的運(yùn)動(dòng)環(huán)境進(jìn)行建模。先用柵格法把機(jī)器人的運(yùn)動(dòng)空間分割，然后把機(jī)器人的運(yùn)動(dòng)空間映射為由自反饋BINN組成的拓?fù)錉顟B(tài)空間，每一個(gè)柵格都對(duì)應(yīng)一個(gè)神經(jīng)元，機(jī)器人所要達(dá)到的目標(biāo)位置對(duì)應(yīng)的神經(jīng)元初始激活值為1，障礙物所對(duì)應(yīng)的神經(jīng)元初始激活值為 -1，機(jī)器人及自由空間所對(duì)應(yīng)的神經(jīng)元初始激活值都為0，其中拓?fù)錉顟B(tài)空間的每一個(gè)神經(jīng)元的激活值變化都由方程（5）來(lái)決定。當(dāng)自反饋BINN應(yīng)用于機(jī)器人路徑規(guī)劃時(shí)，第i個(gè)神經(jīng)元的外部輸入Ii的求取方式如下：

式中的E是一個(gè)遠(yuǎn)遠(yuǎn)大于神經(jīng)元活性值上界B的正的常數(shù)，一般情況下取值100。

3.4 自反饋BINN路徑規(guī)劃

第一，先用柵格法把機(jī)器人的運(yùn)動(dòng)空間建模，然后把機(jī)器人的位姿空間映射到神經(jīng)網(wǎng)絡(luò)中，每一個(gè)柵格都對(duì)應(yīng)一個(gè)神經(jīng)元。

第二，神經(jīng)網(wǎng)絡(luò)中除目標(biāo)和障礙外的所有神經(jīng)元激活值初始化為零，并利用式（6）通過(guò)迭代計(jì)算使目標(biāo)點(diǎn)的神經(jīng)元激活值經(jīng)由神經(jīng)元之間的側(cè)連接傳播到出發(fā)點(diǎn)。

第三，當(dāng)目標(biāo)激活值傳播到起始點(diǎn)時(shí)，利用爬山法搜索當(dāng)前位置鄰域內(nèi)激活值最大的神經(jīng)元，如果鄰域內(nèi)神經(jīng)元激活值都不大于當(dāng)前神經(jīng)元的激活值，則機(jī)器人保持在原處不動(dòng)；否則機(jī)器人的下一個(gè)位置為其鄰域內(nèi)具有最大激活值的神經(jīng)元[7]。

第四，如果機(jī)器人的位置坐標(biāo)和目標(biāo)的位置坐標(biāo)重合，則路徑規(guī)劃過(guò)程結(jié)束，否則轉(zhuǎn)第三步。

4 自反饋BINN機(jī)器人路徑規(guī)劃仿真

為了驗(yàn)證本文提出的自反饋BINN移動(dòng)機(jī)器人路徑規(guī)劃方法的有效性和可行性，利用Matlab2010a對(duì)本文提出的路徑規(guī)劃算法進(jìn)行了計(jì)算機(jī)仿真實(shí)驗(yàn)。機(jī)器人運(yùn)動(dòng)環(huán)境空間為二維，機(jī)器人也為二維，機(jī)器人模型為圓形，機(jī)器人是完整的，可以在原地轉(zhuǎn)向。地圖大小為35 m×35 m，由1 225個(gè)35×35的神經(jīng)元方陣組成的網(wǎng)絡(luò)結(jié)構(gòu)來(lái)表示，星型符號(hào)（*）所組成的軌跡曲線表示機(jī)器人的規(guī)劃路徑，機(jī)器人由一個(gè)（*）位置到達(dá)臨近（*）位置為一次運(yùn)動(dòng)，機(jī)器人每一次橫向和縱向運(yùn)動(dòng)都為1 m，每一次斜向運(yùn)動(dòng)為1.414 m。圓圈（o）所組成的軌跡曲線為目標(biāo)的運(yùn)動(dòng)軌跡，黑色方格表示的是障礙物，符號(hào)（+）所組成的軌跡曲線表示的是移動(dòng)障礙運(yùn)動(dòng)的軌跡，菱形圖標(biāo)表示機(jī)器人所在的初始位置。自反饋BINN模型的參數(shù)設(shè)置為 A=1，B=D=1，E=100，a=0.7，r=1.5，β=6 。

4.1 靜態(tài)環(huán)境下的仿真與比較

這一部分將在靜態(tài)地圖環(huán)境下對(duì)自反饋BINN算法與BINN算法[4]進(jìn)行仿真比較。

仿真1是U型地圖環(huán)境下的仿真，U型地圖是測(cè)試機(jī)器人路徑規(guī)劃能力的經(jīng)典地圖，在此次仿真中目標(biāo)起始的坐標(biāo)位置為（17，32），機(jī)器人的起始坐標(biāo)位置為（17，23），機(jī)器人的移動(dòng)速度為1 m/s，仿真結(jié)果如圖3所示。

圖3 U型地圖仿真

在圖3（a）中可以看到路徑總共有15次變向，在無(wú)障礙時(shí)的波浪形運(yùn)動(dòng)一次，最后它的路徑長(zhǎng)度為47.694 m。在圖3（b）中路徑總共有8次變向，在無(wú)障礙處沒(méi)有波浪運(yùn)動(dòng)，最后它的路徑總長(zhǎng)度為44.796 m。因此可以看出自反饋BINN比單純的BINN能生成更短更加平滑的無(wú)碰撞路徑。在現(xiàn)實(shí)生活中變向會(huì)浪費(fèi)更多的時(shí)間和能源，自反饋BINN比BINN少了7次轉(zhuǎn)向，因此自反饋BINN比單純的BINN更加節(jié)能環(huán)保。兩者具體的數(shù)據(jù)比較如表1。

表1 仿真1比較結(jié)果

4.2 復(fù)雜動(dòng)態(tài)環(huán)境下仿真

這一部分將在復(fù)雜動(dòng)態(tài)地圖環(huán)境下進(jìn)行路徑規(guī)劃仿真，地圖中目標(biāo)是運(yùn)動(dòng)的，不但有固定的障礙，同時(shí)還有運(yùn)動(dòng)著的障礙，仿真中機(jī)器人每一次橫向和縱向運(yùn)動(dòng)都為1 m，每一次斜向運(yùn)動(dòng)為1.414 m。

仿真2是在動(dòng)態(tài)的地圖環(huán)境中追蹤移動(dòng)的目標(biāo)，并同時(shí)對(duì)移動(dòng)的障礙作出反應(yīng)。目標(biāo)以1 m/s的速度由左至右從（1，34）運(yùn)動(dòng)到終點(diǎn)坐標(biāo)（34，33），先階梯向下運(yùn)動(dòng)，然后階梯向上運(yùn)動(dòng)，最后停留在坐標(biāo)（34，33），在這期間目標(biāo)共變向11次。移動(dòng)障礙以1 m/s的速度由左至右從（4，21）移動(dòng)到（29，21）。機(jī)器人的起始位置為（23，10），仿真結(jié)果如圖4所示。在圖4（a）中是BINN算法所生成的實(shí)時(shí)避障路徑，當(dāng)目標(biāo)開(kāi)始移動(dòng)時(shí)機(jī)器人也開(kāi)始向相同的方向移動(dòng)，當(dāng)機(jī)器人快要通過(guò)右側(cè)固定障礙時(shí)，從左側(cè)移動(dòng)過(guò)來(lái)的移動(dòng)障礙正好把右側(cè)出口堵住，機(jī)器人重新從左側(cè)通過(guò)了障礙，在這個(gè)過(guò)程中機(jī)器人有兩次在無(wú)障礙處出現(xiàn)波浪形的運(yùn)動(dòng)，在隨后的過(guò)程中機(jī)器人無(wú)法對(duì)機(jī)器人進(jìn)行無(wú)差別的追蹤，在整個(gè)路徑中機(jī)器人一共轉(zhuǎn)向23次，最終路徑長(zhǎng)度為67.36 m。圖4（b）是自反饋BINN生成的實(shí)時(shí)避障路徑，其避障路徑生成的過(guò)程同BINN方法的相似。但是當(dāng)機(jī)器人通過(guò)障礙物后可以對(duì)移動(dòng)的目標(biāo)進(jìn)行無(wú)差別追蹤。在這個(gè)過(guò)程中機(jī)器人轉(zhuǎn)向13次，最終路徑長(zhǎng)度為66.178 m。因此可以看出在復(fù)雜的動(dòng)態(tài)環(huán)境中自反饋BINN比單純的BINN能生成更短更加平滑的實(shí)時(shí)無(wú)碰撞路徑，并且能對(duì)運(yùn)動(dòng)目標(biāo)進(jìn)行無(wú)差別追蹤。在現(xiàn)實(shí)生活中變向會(huì)浪費(fèi)更多的時(shí)間和能源，自反饋BINN比BINN少了10次轉(zhuǎn)向，因此自反饋BINN比單純的BINN更加節(jié)能環(huán)保。兩者具體數(shù)據(jù)比較如表2。

4.3 仿真結(jié)果討論

通過(guò)對(duì)新算法在動(dòng)態(tài)和靜態(tài)地圖下的模擬仿真，可以總結(jié)出自反饋BINN算法模型的優(yōu)點(diǎn)：

圖4 復(fù)雜動(dòng)態(tài)環(huán)境仿真

表2 仿真2比較結(jié)果

（1）自反饋BINN算法能夠使機(jī)器人通過(guò)可行路徑到達(dá)目標(biāo)并同時(shí)消除了波浪形路徑的產(chǎn)生，并且能夠大量減少轉(zhuǎn)向次數(shù)。

（2）動(dòng)態(tài)環(huán)境下，改善了BINN追蹤效果不理想的情況，能夠預(yù)判目標(biāo)運(yùn)動(dòng)的方向從而在和目標(biāo)同速的情況下對(duì)運(yùn)動(dòng)的目標(biāo)進(jìn)行無(wú)差別追蹤。

5 結(jié)論

文章提出了一種基于BINN的帶自反饋的BINN移動(dòng)機(jī)器人路徑規(guī)劃方法，在靜態(tài)和動(dòng)態(tài)的環(huán)境下和文獻(xiàn)[4]的方法進(jìn)行了仿真比較。結(jié)果表明該路徑規(guī)劃方法比原方法有了很好的提高，不僅保證了移動(dòng)機(jī)器人在靜態(tài)環(huán)境下能夠得到更優(yōu)的路徑，而且在動(dòng)態(tài)環(huán)境中給機(jī)器人提供了更強(qiáng)的對(duì)目標(biāo)的追蹤能力。

[1]席裕庚，張純剛.一類(lèi)動(dòng)態(tài)不確定環(huán)境下機(jī)器人的滾動(dòng)路徑規(guī)劃[J].自動(dòng)化學(xué)報(bào)，2002，28（2）：161-175.

[2]羅乾又，張華，王姮，等.改進(jìn)人工勢(shì)場(chǎng)法在機(jī)器人路徑規(guī)劃中的應(yīng)用[J].計(jì)算機(jī)工程與設(shè)計(jì)，2011（4）.

[3]魏冠偉，付夢(mèng)印.基于神經(jīng)網(wǎng)絡(luò)的機(jī)器人路徑規(guī)劃算法[J].計(jì)算機(jī)仿真，2010，27（7）：112-116.

[4]Yang S X，Luo C.A bioinspired neural network for realtime concurrent map building and complete coverage robot navigation in unknown environments[J].IEEE Transactions on Neural Networks，2008，19（7）：1279-1298.

[5]Yang S X，Meng M.An efficient neural network approach to dynamic robot motion planning[J].Neural Networks，2000，13（2）：143-148.

[6]范莉麗，王奇志.改進(jìn)的生物激勵(lì)神經(jīng)網(wǎng)絡(luò)的機(jī)器人路徑規(guī)劃[J].計(jì)算機(jī)技術(shù)與發(fā)展，2006，16（4）：19-21.

[7]宋勇，李貽斌，栗春，等.基于神經(jīng)網(wǎng)絡(luò)的移動(dòng)機(jī)器人路徑規(guī)劃方法研究[J].系統(tǒng)工程與電子技術(shù)，2008，30（2）：316-319.