基于改進(jìn)生物啟發(fā)神經(jīng)網(wǎng)絡(luò)的機(jī)器人目標(biāo)搜索方法

張智彤，倪建軍，莫正佩

(河海大學(xué)物聯(lián)網(wǎng)工程學(xué)院，江蘇 常州 213022)

0 引 言

針對未知環(huán)境中目標(biāo)搜索的問題，國內(nèi)外的學(xué)者做了大量的研究。戴良軍等[1]提出了協(xié)同搜索策略，并分析了分區(qū)域搜索和橫隊(duì)平行搜索的優(yōu)勢與不足。肖瀟等[2]提出了一種結(jié)合全區(qū)域搜索與動(dòng)態(tài)模板匹配的未知環(huán)境中目標(biāo)搜索方法，與常規(guī)的覆蓋搜索算法[3]相比，可以不受起始位置影響，具有較好的避障能力，但該方法仍屬于覆蓋搜素，盡管具有較強(qiáng)的魯棒性，但搜索時(shí)間和空間的開銷太大，搜索效率不高。為了降低搜索代價(jià)，Aydemir等[4]提出了一種間接搜索的方法，即首先搜索與目標(biāo)有關(guān)的“中間對象”，然后根據(jù)關(guān)聯(lián)關(guān)系對目標(biāo)進(jìn)行搜索。該方法由于利用了目標(biāo)關(guān)聯(lián)信息，在一定程度上可以提高搜索效率，但通常間接關(guān)系很難確定，同時(shí)對間接目標(biāo)的搜索也很困難。動(dòng)態(tài)目標(biāo)搜索問題的最優(yōu)解很難通過理論方法得到其解析形式。在動(dòng)態(tài)搜索問題中，最主要的難題在于搜索過程中搜索者會(huì)逐步退化，導(dǎo)致對環(huán)境的探索能力降低。在動(dòng)態(tài)目標(biāo)搜索中，任何關(guān)于目標(biāo)運(yùn)動(dòng)行為的先驗(yàn)知識(shí)都將對預(yù)測目標(biāo)有極大的幫助。當(dāng)目標(biāo)的運(yùn)動(dòng)模型完全已知時(shí)，稱其為“確定性”搜索問題，對導(dǎo)彈的航跡追蹤即為經(jīng)典確定性跟蹤問題。當(dāng)目標(biāo)的運(yùn)動(dòng)模式可以用一類包含隨機(jī)變量的模型表示時(shí)，稱其為“概率性”搜索問題[5]。關(guān)于此類問題的研究通常采用遞歸貝葉斯估計(jì)模型更新目標(biāo)在空間中的概率分布，逐步獲得目標(biāo)的準(zhǔn)確位置[6-8]。

獲得目標(biāo)的狀態(tài)信息是異構(gòu)機(jī)器人目標(biāo)搜索的目的。根據(jù)異構(gòu)機(jī)器人對目標(biāo)狀態(tài)信息的了解程度，有2種目標(biāo)搜索方法，例如楊日杰等[9]提出了基于馬爾科夫過程的目標(biāo)啟發(fā)式搜索方法，根據(jù)已知的目標(biāo)先驗(yàn)位置分布信息，對目標(biāo)的運(yùn)動(dòng)位置進(jìn)行估計(jì)和更新以得到更為精確的目標(biāo)后驗(yàn)分布，再利用啟發(fā)函數(shù)得到下一步的最佳搜索節(jié)點(diǎn)。這是目標(biāo)先驗(yàn)信息已知的情況下。另一種是在目標(biāo)狀態(tài)信息完全未知的情況下進(jìn)行目標(biāo)搜索，如王宏健等[10]提出了一種分區(qū)域隨機(jī)搜索方法，其意是將機(jī)器人分配到自己的責(zé)任區(qū)后開始搜索，運(yùn)動(dòng)目標(biāo)點(diǎn)隨機(jī)選取。雖然此方法的優(yōu)點(diǎn)是計(jì)算量小、反應(yīng)快速，但是缺點(diǎn)明顯。若要搜索任務(wù)高效完成，需要將子區(qū)域的范圍劃分得很小，即多機(jī)器人系統(tǒng)的成員數(shù)量大，否則在一個(gè)較大范圍的三維環(huán)境中隨機(jī)搜索一個(gè)目標(biāo)，隨機(jī)性大，成功率低。雷斌等[11]首先采用全局隨機(jī)搜索方式檢測到目標(biāo)信號(hào)強(qiáng)度較大的區(qū)域，然后采用PSO算法進(jìn)行局部搜索，通過更新局部最優(yōu)和全局最優(yōu)位置信息尋找目標(biāo)。

在未知環(huán)境中對目標(biāo)進(jìn)行搜索，目標(biāo)位置信息以及障礙物的信息是未知的，移動(dòng)目標(biāo)在某時(shí)刻有可能出現(xiàn)在已經(jīng)搜索過的區(qū)域，也可能出現(xiàn)在未搜索過的區(qū)域，但是目標(biāo)會(huì)在局部范圍內(nèi)釋放一些信息素，這些信息素會(huì)隨著時(shí)間的推移而減少，而且機(jī)器人可以探測到這些信息素。針對這種情況，本文提出改進(jìn)生物啟發(fā)神經(jīng)網(wǎng)絡(luò)的方式并結(jié)合遺傳算法，根據(jù)機(jī)器人能力不同分配不同的搜索區(qū)域。

1 基于遺傳算法機(jī)器人區(qū)域分配

本文采用遺傳算法[12-13]根據(jù)機(jī)器人搜索能力的大小對搜索區(qū)域進(jìn)行劃分，并讓機(jī)器人移動(dòng)到相應(yīng)的搜索區(qū)域進(jìn)行下一步的搜索。

1)編碼方式。

染色體的長度為機(jī)器人個(gè)數(shù)。染色體表示給每個(gè)機(jī)器人分配區(qū)域的范圍。每一條染色體p表示為：

p={[(xmin 1,xmax 1),(ymin 1,ymax 1)],…,

[(xmin k,xmax k),(ymin k,ymax k)]}

(1)

2)適應(yīng)度函數(shù)。

結(jié)合本次搜索區(qū)域的分配，應(yīng)該考慮以下的問題：①機(jī)器人的初始位置；②機(jī)器人搜索能力；③劃分范圍的面積。所以適應(yīng)度函數(shù)如公式(2)所示。

(2)

其中，posi和roboti分別表示區(qū)域的中心位置和第i個(gè)機(jī)器人的初始位置，posAreai和robotCapi分別表示第i個(gè)區(qū)域的面積和第i個(gè)機(jī)器人的搜索范圍的能力。

基于遺傳算法區(qū)域分配的操作步驟如下：

1)初始化。初始化種群大小為PopSize，迭代次數(shù)為PopGeneration，染色體長度為ChromeLength，變異概率為MutProb，交叉概率為CrossProb，最好個(gè)體的適應(yīng)度值為BestPop和整個(gè)群體最佳的適應(yīng)度值為BestFitness。

2)計(jì)算個(gè)體適應(yīng)度值。根據(jù)公式(2)計(jì)算每個(gè)個(gè)體的適應(yīng)度值fi。

3)選擇操作。采用輪盤賭策略，則每個(gè)個(gè)體被選擇到下一代的概率為：

(3)

4)交叉操作。根據(jù)交叉概率隨機(jī)選擇2條染色體進(jìn)行交叉，并對交叉后的結(jié)果按步驟6進(jìn)行調(diào)整，使得分配搜索的每個(gè)區(qū)域范圍的合集可以覆蓋整個(gè)地圖。

5)變異操作。根據(jù)變異概率選擇某條染色體進(jìn)行變異，這里變異操作采用增大或減小某個(gè)搜索的范圍，并對變異后的結(jié)果按步驟6進(jìn)行調(diào)整，使得分配搜索的每個(gè)區(qū)域范圍的合集可以覆蓋整個(gè)地圖。

6)調(diào)整。當(dāng)出現(xiàn)某個(gè)染色體表示搜索區(qū)域的范圍發(fā)生重疊的時(shí)候，隨機(jī)選擇一個(gè)發(fā)生重疊的區(qū)域，并把該區(qū)域重疊的部分去除掉。當(dāng)出現(xiàn)搜索范圍沒有覆蓋整個(gè)地圖時(shí)，則終止本次交叉或變異操作。

2 基于改進(jìn)生物啟發(fā)神經(jīng)網(wǎng)絡(luò)的目標(biāo)搜索

2.1 未知環(huán)境中地圖的劃分

地圖構(gòu)建是目標(biāo)搜索任務(wù)的關(guān)鍵。在未知環(huán)境下機(jī)器人在搜索之前不可能獲得地圖信息。

圖1 環(huán)境建模方法

由于環(huán)境的全局信息是未知的，所以不可能用全局環(huán)境信息來構(gòu)建地圖。然而，該機(jī)器人可以利用車載傳感器對周圍環(huán)境信息進(jìn)行檢測，因此，可以根據(jù)機(jī)器人檢測到的局部信息，利用柵格法建立地圖，并根據(jù)此地圖獲得障礙物的坐標(biāo)。環(huán)境建模方法如圖1所示。

2.2 生物啟發(fā)神經(jīng)網(wǎng)絡(luò)方程改進(jìn)

在傳統(tǒng)的生物啟發(fā)神經(jīng)網(wǎng)絡(luò)[14-16]中，每一個(gè)神經(jīng)元(表示為q)對應(yīng)于環(huán)境中的一個(gè)位置。機(jī)器人總是選擇鄰居神經(jīng)元中活性值最大的神經(jīng)元作為它的下一步動(dòng)作位置，其選擇規(guī)則是[15-16]：

qn←xqn=max{xj,j=1,2,…,k}

(4)

在一個(gè)范圍很大的環(huán)境中，該特性會(huì)大幅度增加計(jì)算的復(fù)雜度。為了降低計(jì)算復(fù)雜度，本文采用動(dòng)態(tài)生物啟發(fā)神經(jīng)網(wǎng)絡(luò)模型，即BINN是一個(gè)動(dòng)態(tài)的網(wǎng)絡(luò)，以機(jī)器人為中心，以機(jī)器人的傳感器所能探測的最大范圍為半徑(R)。當(dāng)機(jī)器人在環(huán)境中運(yùn)動(dòng)時(shí)，只更新自己所能探測到范圍內(nèi)的神經(jīng)元的活性值。在動(dòng)態(tài)生物啟發(fā)神經(jīng)網(wǎng)絡(luò)模型搭建完成后，生物啟發(fā)神經(jīng)網(wǎng)絡(luò)模型中每個(gè)神經(jīng)元的活性值由如下方程計(jì)算得到：

(5)

其中，xi是第i個(gè)神經(jīng)元的活性值；A, B, D均為非負(fù)常數(shù)，分別代表被動(dòng)率、活性值的上限和下限；k表示第i個(gè)神經(jīng)元的鄰居神經(jīng)元個(gè)數(shù)。ωij是第i個(gè)神經(jīng)元與第j個(gè)神經(jīng)元之間的連接權(quán)值。函數(shù)[x]+和[x]-是非線性函數(shù)，定義為：[x]+=max{x, 0}, [x]-=max{-x, 0}。

由于目標(biāo)在不斷運(yùn)動(dòng)中，并且目標(biāo)走過的地方會(huì)留下目標(biāo)特有的信息素。某時(shí)刻它既可能出現(xiàn)在已經(jīng)搜過的區(qū)域，也有可能出現(xiàn)在未搜索的區(qū)域。所以對于已經(jīng)搜索過區(qū)域的活性值會(huì)隨著時(shí)間的變化而變化，對傳統(tǒng)的生物啟發(fā)神經(jīng)網(wǎng)絡(luò)公式進(jìn)行改進(jìn)：

(6)

當(dāng)?shù)趇個(gè)神經(jīng)元已經(jīng)被探測過但在本時(shí)刻不在其探測范圍內(nèi)時(shí)，采用公式(7)計(jì)算。

(7)

其中，Activityi表示第i個(gè)神經(jīng)元的活性值，由公式(5)計(jì)算得到，ωia代表神經(jīng)元i和機(jī)器人位置a之間的權(quán)重，dia代表神經(jīng)元i和機(jī)器人a之間的距離。NArea指的是機(jī)器人a所探測的范圍中柵格的數(shù)目。visitedi表示神經(jīng)元i訪問的次數(shù)，t表示當(dāng)前循環(huán)次數(shù)，tmax表示總的循環(huán)次數(shù)，-t×visitedi/tmax可以防止多次選擇同一個(gè)神經(jīng)元。targetInfoi表示目標(biāo)在第i個(gè)神經(jīng)元上留下的信息素大小。Rangea表示第a個(gè)機(jī)器人探測的范圍。

機(jī)器人搜索的過程如下：

1)當(dāng)機(jī)器人走到指定的搜索區(qū)域之后，首先在探測范圍的外圍隨機(jī)選擇一個(gè)位置作為初始目標(biāo)點(diǎn)，初識(shí)目標(biāo)點(diǎn)的選擇如圖2所示。按公式(5)更新活性值。

2)選擇活性值最大的點(diǎn)作為下一個(gè)搜索的位置，把已經(jīng)探測過的范圍的活性值降為0，使用公式(6)，對未探測過的進(jìn)行更新，并使得該位置處的訪問記錄加1。如果該位置的訪問次數(shù)達(dá)到禁忌閾值，則把該位置加入禁忌表中，當(dāng)禁忌表的長度達(dá)到某個(gè)數(shù)值后，把禁忌表中最初加入的幾個(gè)數(shù)據(jù)從禁忌表中刪除，并重置該位置的活性值和訪問次數(shù)。

3)對于已經(jīng)探測過的并且不在本次探測范圍內(nèi)的活性值，按照公式(7)進(jìn)行更新。

圖2 初始目標(biāo)點(diǎn)選取

3 仿真實(shí)驗(yàn)及結(jié)果

為了驗(yàn)證未知環(huán)境下的基于禁忌搜索的動(dòng)態(tài)生物啟發(fā)神經(jīng)網(wǎng)絡(luò)方法的有效性，進(jìn)行了多次仿真實(shí)驗(yàn)。在機(jī)器人進(jìn)行目標(biāo)搜索的過程中，有2種情況：一種情況是目標(biāo)靜止的，另一種是目標(biāo)隨機(jī)運(yùn)動(dòng)。針對這2種情況進(jìn)行了多次實(shí)驗(yàn)。為了簡化實(shí)驗(yàn)，機(jī)器人以質(zhì)點(diǎn)表示，并且不考慮各種噪聲的干預(yù)。機(jī)器人和目標(biāo)分別用不同的顏色進(jìn)行標(biāo)識(shí)。機(jī)器人初始位置以及基于遺傳算法機(jī)器人搜索區(qū)域分配如表1所示。

表1 基于遺傳算法機(jī)器人搜索區(qū)域

Robot1Robot2Robot3Robot4初始位置(15,29)(0,17)(15,17)(0,29)最大搜索能力/柵格3453搜索范圍X[14,30][0,13][14,30][0,13]搜索范圍Y[18,30][0,17][0,17][18,30]

3.1 目標(biāo)處于靜止?fàn)顟B(tài)實(shí)驗(yàn)結(jié)果

在此實(shí)驗(yàn)中，目標(biāo)處于靜止?fàn)顟B(tài)。目標(biāo)初始位置分別為(5，4)和(2，26)。與隨機(jī)搜索算法和原始的生物啟發(fā)神經(jīng)網(wǎng)絡(luò)相比，結(jié)果如圖3和表2所示。從圖中可以看出，本算法可以有效搜索到目標(biāo)。

(a) 隨機(jī)算法

(b) 原始生物啟發(fā)神經(jīng)網(wǎng)絡(luò)

(c) 本文算法圖3 靜態(tài)目標(biāo)搜索結(jié)果

表2 靜態(tài)目標(biāo)搜索成功率對比

算法仿真次數(shù)成功次數(shù)成功率/%平均時(shí)間/s本文算法303010028.13原始算法302686.633.26隨機(jī)搜索30155048.25

3.2 目標(biāo)處于運(yùn)動(dòng)狀態(tài)實(shí)驗(yàn)結(jié)果

在此實(shí)驗(yàn)中，目標(biāo)處于運(yùn)動(dòng)狀態(tài)。目標(biāo)初始位置分別為(5，4)和(2，26)。與隨機(jī)搜索算法相比，結(jié)果如表3和圖4所示。從圖中可以看出，本算法可以有效搜索到目標(biāo)。

表3 動(dòng)態(tài)目標(biāo)搜索成功率對比

算法仿真次數(shù)成功次數(shù)成功率/%平均時(shí)間/s本文算法303010035.56原始算法302273.342.89隨機(jī)搜索301033.359.78

(a) 隨機(jī)算法

(b) 原始生物啟發(fā)神經(jīng)網(wǎng)絡(luò)

(c) 本文算法圖4 動(dòng)態(tài)目標(biāo)搜索結(jié)果

3.3 有效性驗(yàn)證

為了驗(yàn)證本文算法的有效性，又進(jìn)行了以下2個(gè)實(shí)驗(yàn)，第1個(gè)是目標(biāo)靜止在不同的位置(圖5)，第2個(gè)是目標(biāo)在不同位置移動(dòng)(圖6)。

(a)

(b)圖5 目標(biāo)靜止在不同位置

(a)

(b)圖6 目標(biāo)在不同位置移動(dòng)

4 結(jié)束語

本文研究了未知環(huán)境下的機(jī)器人目標(biāo)搜索問題，根據(jù)機(jī)器人搜索能力的不同提出基于遺傳算法搜索區(qū)域的劃分；由于沒有目標(biāo)的狀態(tài)信息以及目標(biāo)是隨機(jī)運(yùn)動(dòng)的，在某一時(shí)刻目標(biāo)可能出現(xiàn)在未搜索過的區(qū)域也可能出現(xiàn)在已經(jīng)搜索過的區(qū)域，針對這種情況提出了基于禁忌搜索改進(jìn)生物啟發(fā)神經(jīng)網(wǎng)絡(luò)的搜索方式。為了驗(yàn)證所提方法的有效性，本文設(shè)計(jì)了仿真實(shí)驗(yàn)，實(shí)驗(yàn)仿真結(jié)果表明，該方法能有效完成目標(biāo)搜索任務(wù)。

參考文獻(xiàn)：

[1] 戴良軍,陳宇強(qiáng),周紹磊. 無人機(jī)編隊(duì)協(xié)同搜索策略研究[C]// 2014(第五屆)中國無人機(jī)大會(huì)論文集. 2014:610-614.

[2] 肖瀟,方勇純,賀鋒,等. 未知環(huán)境下移動(dòng)機(jī)器人自主搜索技術(shù)研究[J]. 機(jī)器人, 2007,29(3):224-229.

[3] Gonzalez E, Alvarez O, Diaz Y, et al. BSA: A complete coverage algorithm[C]// Proceedings of the 2005 IEEE International Conference on Robotics and Automation. 2005:2040-2044.

[4] Aydemir A, Sj?? K, Jensfelt P. Object search on a mobile robot using relational spatial information[C]// Proceedings of the 2010 International Conference on Intelligent Autonomous Systems. 2010:111-120.

[5] Senanayake M, Senthooran I, Barca J C, et al. Search and tracking algorithms for swarms of robots: A survey[J]. Robotics and Autonomous Systems, 2016,75(Part B):422-434.

[6] Esmailifar S M, Saghafi F. Moving target localization by cooperation of multiple flying vehicles[J]. IEEE Transactions on Aerospace and Electronic Systems, 2015,51(1):739-746.

[7] Aziz A M. A joint possibilistic data association technique for tracking multiple targets in a cluttered environment[J]. Information Sciences, 2014,280:239-260.

[8] Lanillos P, Gan S K, Besada-Portas E, et al. Multi-UAV target search using decentralized gradient-based negotiation with expected observation[J]. Information Sciences, 2014,282:92-110.

[9] 楊日杰,吳芳,徐俊艷,等. 基于馬爾可夫過程的水下運(yùn)動(dòng)目標(biāo)啟發(fā)式搜索[J]. 兵工學(xué)報(bào), 2010,31(5):1088-1093.

[10] 王宏健,熊偉,陳子印,等. 多自主水下航行器區(qū)域搜索與協(xié)同圍捕方法研究[J]. 中國造船, 2010,51(2):117-125.

[11] 雷斌,李文鋒. 基于粒子群優(yōu)化的多機(jī)器人合作目標(biāo)搜索算法[J]. 武漢理工大學(xué)學(xué)報(bào), 2009,31(15):73-76.

[12] 劉耀軒,林煦涵,孫海洋. 遺傳算法的研究與改進(jìn)[J]. 電子世界, 2017(8):12-13.

[13] 馬永杰,云文霞. 遺傳算法研究進(jìn)展[J]. 計(jì)算機(jī)應(yīng)用研究, 2012,29(4):1201-1206.

[14] Ni Jianjun, Wu Liuying, Shi Pengfei, et al. A dynamic bioinspired neural network based real-time path planning method for autonomous underwater vehicles[J]. Computational Intelligence and Neuroscience, 2017-02-01, doi: 10.1155/2017/9269742.

[15] Ni Jianjun, Yang S X. Bioinspired neural network for real-time cooperative hunting by multirobots in unknown environments[J]. IEEE Transactions on Neural Networks, 2011,22(12):2062-2077.

[16] Ni Jianjun, Wu Liuying, Fan Xinnan, et al. Bioinspired intelligent algorithm and its applications for mobile robot control: A survey[J]. Computational Intelligence and Neuroscience, 2015-12-27, doi: 10.1155/2016/3810903.