張智彤,倪建軍,莫正佩
(河海大學(xué)物聯(lián)網(wǎng)工程學(xué)院,江蘇 常州 213022)
針對(duì)未知環(huán)境中目標(biāo)搜索的問(wèn)題,國(guó)內(nèi)外的學(xué)者做了大量的研究。戴良軍等[1]提出了協(xié)同搜索策略,并分析了分區(qū)域搜索和橫隊(duì)平行搜索的優(yōu)勢(shì)與不足。肖瀟等[2]提出了一種結(jié)合全區(qū)域搜索與動(dòng)態(tài)模板匹配的未知環(huán)境中目標(biāo)搜索方法,與常規(guī)的覆蓋搜索算法[3]相比,可以不受起始位置影響,具有較好的避障能力,但該方法仍屬于覆蓋搜素,盡管具有較強(qiáng)的魯棒性,但搜索時(shí)間和空間的開(kāi)銷太大,搜索效率不高。為了降低搜索代價(jià),Aydemir等[4]提出了一種間接搜索的方法,即首先搜索與目標(biāo)有關(guān)的“中間對(duì)象”,然后根據(jù)關(guān)聯(lián)關(guān)系對(duì)目標(biāo)進(jìn)行搜索。該方法由于利用了目標(biāo)關(guān)聯(lián)信息,在一定程度上可以提高搜索效率,但通常間接關(guān)系很難確定,同時(shí)對(duì)間接目標(biāo)的搜索也很困難。動(dòng)態(tài)目標(biāo)搜索問(wèn)題的最優(yōu)解很難通過(guò)理論方法得到其解析形式。在動(dòng)態(tài)搜索問(wèn)題中,最主要的難題在于搜索過(guò)程中搜索者會(huì)逐步退化,導(dǎo)致對(duì)環(huán)境的探索能力降低。在動(dòng)態(tài)目標(biāo)搜索中,任何關(guān)于目標(biāo)運(yùn)動(dòng)行為的先驗(yàn)知識(shí)都將對(duì)預(yù)測(cè)目標(biāo)有極大的幫助。當(dāng)目標(biāo)的運(yùn)動(dòng)模型完全已知時(shí),稱其為“確定性”搜索問(wèn)題,對(duì)導(dǎo)彈的航跡追蹤即為經(jīng)典確定性跟蹤問(wèn)題。當(dāng)目標(biāo)的運(yùn)動(dòng)模式可以用一類包含隨機(jī)變量的模型表示時(shí),稱其為“概率性”搜索問(wèn)題[5]。關(guān)于此類問(wèn)題的研究通常采用遞歸貝葉斯估計(jì)模型更新目標(biāo)在空間中的概率分布,逐步獲得目標(biāo)的準(zhǔn)確位置[6-8]。
獲得目標(biāo)的狀態(tài)信息是異構(gòu)機(jī)器人目標(biāo)搜索的目的。根據(jù)異構(gòu)機(jī)器人對(duì)目標(biāo)狀態(tài)信息的了解程度,有2種目標(biāo)搜索方法,例如楊日杰等[9]提出了基于馬爾科夫過(guò)程的目標(biāo)啟發(fā)式搜索方法,根據(jù)已知的目標(biāo)先驗(yàn)位置分布信息,對(duì)目標(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ū)后開(kāi)始搜索,運(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ī)搜索方式檢測(cè)到目標(biāo)信號(hào)強(qiáng)度較大的區(qū)域,然后采用PSO算法進(jìn)行局部搜索,通過(guò)更新局部最優(yōu)和全局最優(yōu)位置信息尋找目標(biāo)。
在未知環(huán)境中對(duì)目標(biāo)進(jìn)行搜索,目標(biāo)位置信息以及障礙物的信息是未知的,移動(dòng)目標(biāo)在某時(shí)刻有可能出現(xiàn)在已經(jīng)搜索過(guò)的區(qū)域,也可能出現(xiàn)在未搜索過(guò)的區(qū)域,但是目標(biāo)會(huì)在局部范圍內(nèi)釋放一些信息素,這些信息素會(huì)隨著時(shí)間的推移而減少,而且機(jī)器人可以探測(cè)到這些信息素。針對(duì)這種情況,本文提出改進(jìn)生物啟發(fā)神經(jīng)網(wǎng)絡(luò)的方式并結(jié)合遺傳算法,根據(jù)機(jī)器人能力不同分配不同的搜索區(qū)域。
本文采用遺傳算法[12-13]根據(jù)機(jī)器人搜索能力的大小對(duì)搜索區(qū)域進(jìn)行劃分,并讓機(jī)器人移動(dòng)到相應(yīng)的搜索區(qū)域進(jìn)行下一步的搜索。
1)編碼方式。
染色體的長(zhǎng)度為機(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)該考慮以下的問(wèn)題:①機(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,染色體長(zhǎng)度為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)行交叉,并對(duì)交叉后的結(jié)果按步驟6進(jìn)行調(diào)整,使得分配搜索的每個(gè)區(qū)域范圍的合集可以覆蓋整個(gè)地圖。
5)變異操作。根據(jù)變異概率選擇某條染色體進(jìn)行變異,這里變異操作采用增大或減小某個(gè)搜索的范圍,并對(duì)變異后的結(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)搜索范圍沒(méi)有覆蓋整個(gè)地圖時(shí),則終止本次交叉或變異操作。
地圖構(gòu)建是目標(biāo)搜索任務(wù)的關(guān)鍵。在未知環(huán)境下機(jī)器人在搜索之前不可能獲得地圖信息。
圖1 環(huán)境建模方法
由于環(huán)境的全局信息是未知的,所以不可能用全局環(huán)境信息來(lái)構(gòu)建地圖。然而,該機(jī)器人可以利用車載傳感器對(duì)周圍環(huán)境信息進(jìn)行檢測(cè),因此,可以根據(jù)機(jī)器人檢測(cè)到的局部信息,利用柵格法建立地圖,并根據(jù)此地圖獲得障礙物的坐標(biāo)。環(huán)境建模方法如圖1所示。
在傳統(tǒng)的生物啟發(fā)神經(jīng)網(wǎng)絡(luò)[14-16]中,每一個(gè)神經(jīng)元(表示為q)對(duì)應(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ī)器人的傳感器所能探測(cè)的最大范圍為半徑(R)。當(dāng)機(jī)器人在環(huán)境中運(yùn)動(dòng)時(shí),只更新自己所能探測(cè)到范圍內(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)走過(guò)的地方會(huì)留下目標(biāo)特有的信息素。某時(shí)刻它既可能出現(xiàn)在已經(jīng)搜過(guò)的區(qū)域,也有可能出現(xiàn)在未搜索的區(qū)域。所以對(duì)于已經(jīng)搜索過(guò)區(qū)域的活性值會(huì)隨著時(shí)間的變化而變化,對(duì)傳統(tǒng)的生物啟發(fā)神經(jīng)網(wǎng)絡(luò)公式進(jìn)行改進(jìn):
(6)
當(dāng)?shù)趇個(gè)神經(jīng)元已經(jīng)被探測(cè)過(guò)但在本時(shí)刻不在其探測(cè)范圍內(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所探測(cè)的范圍中柵格的數(shù)目。visitedi表示神經(jīng)元i訪問(wèn)的次數(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ī)器人探測(cè)的范圍。
機(jī)器人搜索的過(guò)程如下:
1)當(dāng)機(jī)器人走到指定的搜索區(qū)域之后,首先在探測(cè)范圍的外圍隨機(jī)選擇一個(gè)位置作為初始目標(biāo)點(diǎn),初識(shí)目標(biāo)點(diǎn)的選擇如圖2所示。按公式(5)更新活性值。
2)選擇活性值最大的點(diǎn)作為下一個(gè)搜索的位置,把已經(jīng)探測(cè)過(guò)的范圍的活性值降為0,使用公式(6),對(duì)未探測(cè)過(guò)的進(jìn)行更新,并使得該位置處的訪問(wèn)記錄加1。如果該位置的訪問(wèn)次數(shù)達(dá)到禁忌閾值,則把該位置加入禁忌表中,當(dāng)禁忌表的長(zhǎng)度達(dá)到某個(gè)數(shù)值后,把禁忌表中最初加入的幾個(gè)數(shù)據(jù)從禁忌表中刪除,并重置該位置的活性值和訪問(wèn)次數(shù)。
3)對(duì)于已經(jīng)探測(cè)過(guò)的并且不在本次探測(cè)范圍內(nèi)的活性值,按照公式(7)進(jìn)行更新。
圖2 初始目標(biāo)點(diǎn)選取
為了驗(yàn)證未知環(huán)境下的基于禁忌搜索的動(dòng)態(tài)生物啟發(fā)神經(jīng)網(wǎng)絡(luò)方法的有效性,進(jìn)行了多次仿真實(shí)驗(yàn)。在機(jī)器人進(jìn)行目標(biāo)搜索的過(guò)程中,有2種情況:一種情況是目標(biāo)靜止的,另一種是目標(biāo)隨機(jī)運(yùn)動(dòng)。針對(duì)這2種情況進(jìn)行了多次實(shí)驗(yàn)。為了簡(jiǎ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]
在此實(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)搜索成功率對(duì)比
算法仿真次數(shù)成功次數(shù)成功率/%平均時(shí)間/s本文算法303010028.13原始算法302686.633.26隨機(jī)搜索30155048.25
在此實(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)搜索成功率對(duì)比
算法仿真次數(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é)果
為了驗(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)
本文研究了未知環(huán)境下的機(jī)器人目標(biāo)搜索問(wèn)題,根據(jù)機(jī)器人搜索能力的不同提出基于遺傳算法搜索區(qū)域的劃分;由于沒(méi)有目標(biāo)的狀態(tài)信息以及目標(biāo)是隨機(jī)運(yùn)動(dòng)的,在某一時(shí)刻目標(biāo)可能出現(xiàn)在未搜索過(guò)的區(qū)域也可能出現(xiàn)在已經(jīng)搜索過(guò)的區(qū)域,針對(duì)這種情況提出了基于禁忌搜索改進(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),周紹磊. 無(wú)人機(jī)編隊(duì)協(xié)同搜索策略研究[C]// 2014(第五屆)中國(guó)無(wú)人機(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] 楊日杰,吳芳,徐俊艷,等. 基于馬爾可夫過(guò)程的水下運(yùn)動(dòng)目標(biāo)啟發(fā)式搜索[J]. 兵工學(xué)報(bào), 2010,31(5):1088-1093.
[10] 王宏健,熊偉,陳子印,等. 多自主水下航行器區(qū)域搜索與協(xié)同圍捕方法研究[J]. 中國(guó)造船, 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.