移動(dòng)機(jī)器人未知環(huán)境下無(wú)線基站搜索

廖列法，張幸平+，李 帥，楊翌虢

(1.江西理工大學(xué) 信息工程學(xué)院，江西 贛州 341000；2.斯旺西大學(xué) 工程學(xué)院，英國(guó) 威爾士 斯旺西 SA1 8EN)

0 引 言

許多生物通過(guò)感知?dú)馕缎畔⒌淖兓梢赃M(jìn)行自主活動(dòng)。例如飛蛾利用氣味可以成群飛行[1-3]，魚(yú)和鳥(niǎo)利用氣味可以尋找食物[4-6]，蟲(chóng)類(lèi)利用氣味可以搜尋營(yíng)養(yǎng)物質(zhì)[7]。與仿生原理類(lèi)似，機(jī)器人主動(dòng)嗅覺(jué)問(wèn)題[8,9]可理解為機(jī)器人通過(guò)感知器的反饋進(jìn)行自主定位、環(huán)境探索與自主導(dǎo)航等。在一些特定場(chǎng)景下，通過(guò)機(jī)器人的感知原理能夠完成特定氣味源的定位，比如在火場(chǎng)中可利用機(jī)器人搜索火災(zāi)源以及滅火。因此，特定信號(hào)源的定位應(yīng)用廣泛且具有與人互補(bǔ)的優(yōu)勢(shì)。

從函數(shù)優(yōu)化的角度理解定位問(wèn)題：信號(hào)源是信號(hào)最強(qiáng)的點(diǎn)，即在全局空間尋找信號(hào)最強(qiáng)的位置。信號(hào)在傳輸?shù)倪^(guò)程中，受到信號(hào)輻射與擴(kuò)散的影響，信號(hào)強(qiáng)度從信號(hào)源逐漸向外擴(kuò)散減弱。若可用函數(shù)表示信號(hào)強(qiáng)度的變化，則可以通過(guò)梯度上升定位信號(hào)源。但大多數(shù)情況下，無(wú)法確定信號(hào)源擴(kuò)散形成的信號(hào)場(chǎng)，不能用函數(shù)進(jìn)行表示，而且信號(hào)受到干擾的影響，可能形成局部最強(qiáng)。近些年，針對(duì)在函數(shù)未知的情形下全局尋優(yōu)，往往可以使用蟻群算法[10,11]、粒子群算法[12]、微粒群優(yōu)化(PSO)算法[13,14]、遺傳算法[15,16]、螢火蟲(chóng)算法[17]等，并且結(jié)果大多比較理想。但這些算法往往都源于生物種群思想，即需要很多粒子或者機(jī)器人才可以進(jìn)行搜尋，同時(shí)協(xié)作要求高、實(shí)時(shí)性要求強(qiáng)。

天牛須搜索(beetle antennae search，BAS)算法[18,19]是利用天牛覓食行為的仿生機(jī)制提出的一種全局尋優(yōu)方法。它沒(méi)有梯度信息，可在函數(shù)未知的情況下，通過(guò)單個(gè)個(gè)體實(shí)現(xiàn)高效尋優(yōu)。由此，基于BAS提出一種單機(jī)器人尋源算法，并應(yīng)用于未知環(huán)境下無(wú)線基站搜索。

1 無(wú)線基站搜索模型與環(huán)境模型

1.1 無(wú)線信號(hào)模型

無(wú)線信號(hào)的傳播是從信號(hào)源(發(fā)射端)到信號(hào)接收(接收端)的過(guò)程。在理想狀態(tài)下(沒(méi)有干擾和損耗)，其過(guò)程符合自由空間傳播模型。但在現(xiàn)實(shí)生活中，信號(hào)往往會(huì)受到各種各樣的影響，比如傳播過(guò)程受到建筑物、無(wú)線干擾等影響，其過(guò)程符合對(duì)數(shù)距離損耗模型[20]，公式表達(dá)如下

(1)

式中：Ss和Ss0為信號(hào)強(qiáng)度(dBm)；s和s0為與發(fā)射端的距離，單位為m，并且s0為參考取值，常為1 m;n為路徑損耗的速率，一般為常數(shù)，取值范圍受到環(huán)境的影響；Xα為正態(tài)隨機(jī)變量，α為標(biāo)準(zhǔn)差(3.0 dBm-14.1 dBm)，表示如下

Xα～(0,α2)

(2)

式(1)中Ss受到Ss0(距離為1 m時(shí)的信號(hào)強(qiáng)度)、n(路徑損耗，比如周?chē)h(huán)境)、s和s0(距離)、Xα(正態(tài)隨機(jī)變量)等影響，對(duì)其簡(jiǎn)化后的模型可表示為

(3)

另外，設(shè)置s0=1,Ss0=A， 式(3)可進(jìn)一步表示為

Ss=A-10nlog10s

(4)

式中：A為常數(shù)(s0為1時(shí)信號(hào)的強(qiáng)度)。對(duì)式(4)描述了信號(hào)強(qiáng)度Ss與距離s的函數(shù)表示，假設(shè)信號(hào)強(qiáng)度為rssi，s可進(jìn)一步表示為

(5)

式中：n受到周?chē)h(huán)境(理想環(huán)境、空曠環(huán)境、半空曠環(huán)境、密閉環(huán)境等)的影響，其參考取值范圍見(jiàn)表1。

表1 n取值范圍

1.2 機(jī)器人環(huán)境模型

移動(dòng)機(jī)器人所處的環(huán)境未知，為方便實(shí)驗(yàn)，這里假設(shè)分為室內(nèi)和室外兩類(lèi)，同時(shí)將3維空間轉(zhuǎn)換為2維空間。

室內(nèi)場(chǎng)景的2維表示：如圖1所示，為直角坐標(biāo)系中(20,0)，(20,100)，(80,0)，(80,100)4個(gè)頂點(diǎn)組成的區(qū)域，其由房間1、房間2、房間3、房間4、房間5、房間6組成，假設(shè)空間中的直線為墻壁，空白區(qū)域?yàn)榭尚凶邊^(qū)域。

圖1 室內(nèi)環(huán)境模型

室外場(chǎng)景的2維表示：如圖2所示，為直角坐標(biāo)系中(0,0)，(0,200)，(200,0)，(200,200)4個(gè)頂點(diǎn)組成的區(qū)域，其包含障礙物1、障礙物2、障礙物3、障礙物4等不規(guī)則不同形狀的障礙物，同理，空白區(qū)域?yàn)榭尚凶邊^(qū)域。

圖2 室外環(huán)境模型

2 基于天牛須搜索的無(wú)線信號(hào)搜索算法

2.1 天牛須搜索算法原理

BAS算法是源于天牛覓食的仿生機(jī)制，其覓食過(guò)程主要是通過(guò)兩個(gè)觸角感知食物氣味強(qiáng)弱的變化，不斷調(diào)整行走的方向，最終找到食物。當(dāng)左邊方向的氣味更強(qiáng)，則向左邊方向行走，反之則向右側(cè)方向行走。行走的方向是根據(jù)食物氣味的強(qiáng)度動(dòng)態(tài)調(diào)整，其覓食過(guò)程的函數(shù)表達(dá)如下：

(1)天牛的起始朝向和兩觸角間的方向都是隨機(jī)的，假設(shè)為dir，n為空間維數(shù)， rands(n,1) 為隨機(jī)方向向量，對(duì)其進(jìn)行歸一化后表示如下

(6)

(2)假設(shè)xl和xr為兩觸角的空間坐標(biāo)，可表示為

(7)

式中：t為循環(huán)次數(shù)，xt為t次時(shí)天牛的坐標(biāo)，d0為天牛觸角間的距離。

(3)假設(shè)f(x) 函數(shù)的值為氣味的強(qiáng)度， f(xr) 為左邊方向的氣味函數(shù)， f(xl) 為右邊方向的氣味函數(shù)。

(4)天牛每下一步的位置都是根據(jù)左右兩側(cè)的食物氣味強(qiáng)度來(lái)動(dòng)態(tài)更新，其函數(shù)表示如下

xt=xt-1+δt*dir*sign(f(xl)-f(xr))

(8)

式中：xt-1為上一步天牛的位置，δt為經(jīng)過(guò)t次迭代(每次迭代通過(guò)一個(gè)衰減系數(shù)來(lái)更新)后的步長(zhǎng)(step)， sign() 為符號(hào)函數(shù)。式(8)可簡(jiǎn)化為

(9)

(5)結(jié)束？

若找到食物(滿(mǎn)足預(yù)設(shè)條件)或?qū)ふ沂?達(dá)到迭代最大值)則結(jié)束，反之則繼續(xù)步驟(2)～步驟(4)。

2.2 天牛須無(wú)線信號(hào)搜索算法原理

從2.1節(jié)天牛須搜索算法原理可知，算法以初始位置、初始方向、步長(zhǎng)、步長(zhǎng)衰減系數(shù)等作為參數(shù)。首先，以初始參數(shù)計(jì)算天牛的下一步運(yùn)動(dòng)位置。然后，把初始位置和下一步位置理解為左右兩觸角的位置(位置1和位置2)，兩位置之間的距離為步長(zhǎng)。根據(jù)位置1和位置2感知的無(wú)線信號(hào)強(qiáng)度來(lái)動(dòng)態(tài)調(diào)整運(yùn)動(dòng)軌跡，始終朝著信號(hào)更強(qiáng)的方向運(yùn)動(dòng)。每一次運(yùn)動(dòng)后，都把下一步位置和上一步位置更新為位置1和位置2，并通過(guò)步長(zhǎng)衰減系數(shù)更新步長(zhǎng)，如此循環(huán)迭代，直到搜索結(jié)束，其具體過(guò)程如下：

(1)機(jī)器人的參數(shù)：假設(shè)x0為起始位置，step為每一步運(yùn)動(dòng)的距離，dir為運(yùn)動(dòng)的方向。x1為算法計(jì)算的下一步位置的坐標(biāo)。根據(jù)式(9)，x1可表達(dá)為

x1=x0+step*dir

(10)

(2)x0和x1為左右兩個(gè)方向的坐標(biāo)， f(x0) 為左邊(x0)方向的函數(shù)， f(x1) 為右邊(x1)方向的函數(shù)。

(3)根據(jù)x0和x1的無(wú)線信號(hào)強(qiáng)度值，計(jì)算下一步的運(yùn)動(dòng)位置x2(根據(jù)式(9)的位置更新策略)，表示為

(11)

(4)建立位置迭代模型，其更新策略可表示為

(12)

其中，x0(位置1)表示為位置x0和x1接收到的信號(hào)強(qiáng)度更強(qiáng)的位置，x1(位置2)表示為以x0、x1、 f(x0)、 f(x1) 為參數(shù)，根據(jù)BAS算法計(jì)算出機(jī)器人下一步的運(yùn)動(dòng)位置。

(5)結(jié)束？

若找到食物(滿(mǎn)足預(yù)設(shè)條件)或?qū)ふ沂?達(dá)到迭代最大值)則結(jié)束，反之則繼續(xù)步驟(2)～步驟(4)。

2.3 天牛須無(wú)線信號(hào)搜索算法流程

(1)初始化:初始化x0(記為位置1)、dir(運(yùn)動(dòng)方向)、step(每一步的運(yùn)動(dòng)距離)。

(2)計(jì)算位置2:把初始參數(shù)x0、dir、step代入式(10)，得出x1， 記為位置2(下一步的運(yùn)動(dòng)位置)。

(3)x1更新:如果x1為無(wú)效坐標(biāo)(坐標(biāo)在障礙物空間內(nèi)或受到障礙物影響需要繞行)，則x1更新為與障礙物的交匯坐標(biāo)。反之，x1為有效坐標(biāo)，直接進(jìn)行下一步。

(4)計(jì)算位置x2:把x0、x1、dir、step代入式(11)，得出x2(下一步運(yùn)動(dòng)位置)。

(5)x2更新:同理(3)，若x2為無(wú)效坐標(biāo)，則x2更新為與障礙物的交匯坐標(biāo)。反之，x2為有效坐標(biāo)，直接進(jìn)行下一步。

(6)更新位置1和位置2:根據(jù)x1和x2的無(wú)線信號(hào)強(qiáng)度來(lái)動(dòng)態(tài)調(diào)整運(yùn)動(dòng)軌跡，始終朝著信號(hào)更強(qiáng)的方向運(yùn)動(dòng)。x1和x2的更新策略見(jiàn)式(12)。

(7)預(yù)期位置:若找到無(wú)線信號(hào)源(滿(mǎn)足預(yù)設(shè)條件)或?qū)ふ沂?達(dá)到迭代最大值)則結(jié)束，反之則繼續(xù)步驟(4)～步驟(7)。

(8)結(jié)束。

圖3為天牛須無(wú)線信號(hào)搜索算法的流程。

圖3 算法流程

3 實(shí)驗(yàn)仿真與算法分析

實(shí)驗(yàn)分為室內(nèi)場(chǎng)景和室外場(chǎng)景，在仿真工具(MATALAB_R2017b)上進(jìn)行模擬實(shí)驗(yàn)，記錄天牛須無(wú)線信號(hào)搜索算法計(jì)算的每一次運(yùn)動(dòng)位置(坐標(biāo))，每一次實(shí)驗(yàn)所有點(diǎn)坐標(biāo)的連接曲線即為運(yùn)動(dòng)軌跡。

3.1 室內(nèi)環(huán)境

圖4為室內(nèi)場(chǎng)景中實(shí)驗(yàn)的結(jié)果。設(shè)圖4按上到下的順序依次記為圖4(a)、圖4(b)、圖4(c)、圖4(d)。圖4(a) 的初始參數(shù)：路徑衰減因子n為2、初始坐標(biāo)為(22，15)、步長(zhǎng)為3(衰減系數(shù)0.98)、信號(hào)源為坐標(biāo)(70,90) 處的正方形、迭代最大值為100、誤差值為1。圖4(b) 的n為2.5、初始坐標(biāo)為(48，10)。圖4(c)的n為3，初始坐標(biāo)為(28，41)。圖4(d)的n為3.5，初始坐標(biāo)為(26，90)。圖4(b)、圖4(c)和圖4(d)的其它參數(shù)與圖4(a)一致。圖4(a)～圖4(d)表明不同的環(huán)境(理想環(huán)境、空曠環(huán)境、半空曠環(huán)境、密閉環(huán)境)中不同的路徑衰減速率n(2、2.5、3、3.5)下都可以通過(guò)BAS算法成功搜索到無(wú)線信號(hào)源的位置。

圖4 室內(nèi)場(chǎng)景不同起點(diǎn)和相同終點(diǎn)時(shí)的實(shí)驗(yàn)結(jié)果

3.2 室外環(huán)境

圖5為室外場(chǎng)景的實(shí)驗(yàn)結(jié)果。設(shè)圖5按上到下的順序依次記為圖5(a)、圖5(b)、圖5(c)、圖5(d)。圖5(a) 的初始參數(shù)：路徑衰減因子n為2、初始坐標(biāo)為(7,40)、步長(zhǎng)為20(衰減系數(shù)0.98)、信號(hào)源為坐標(biāo)(185,185)處的正方形、迭代最大值為100、誤差值為1。圖5(b)的n為2.5、初始坐標(biāo)為(34,75)。圖5(c)的

圖5 室外場(chǎng)景不同起點(diǎn)和相同終點(diǎn)時(shí)的實(shí)驗(yàn)結(jié)果

n為3，初始坐標(biāo)為(10,144)。圖5(d)的n為3.5，初始坐標(biāo)為(133,30)。圖5(b)、圖5(c)和圖5(d)的其它參數(shù)與圖5(a)一致。圖5(a)～圖5(d)表明不同的環(huán)境(理想環(huán)境、空曠環(huán)境、半空曠環(huán)境、密閉環(huán)境)中不同的路徑衰減速率n(2、2.5、3、3.5)下都可以通過(guò)BAS算法成功搜索到無(wú)線信號(hào)源的位置。

3.3 天牛須無(wú)線信號(hào)搜索算法分析

3.3.1 實(shí)驗(yàn)結(jié)果分析

為保證實(shí)驗(yàn)的有效性和可靠性，室內(nèi)場(chǎng)景中針對(duì)路徑衰減因子n的每一次取值(2,2.5,3,3.5)都分別執(zhí)行30、60、120次，記錄下每一次實(shí)驗(yàn)的結(jié)果并對(duì)實(shí)驗(yàn)數(shù)據(jù)進(jìn)行統(tǒng)計(jì)，統(tǒng)計(jì)結(jié)果見(jiàn)表2。從表2可知，n的取值對(duì)整個(gè)實(shí)驗(yàn)的結(jié)果影響不大，隨著實(shí)驗(yàn)次數(shù)的增加，機(jī)器人移動(dòng)的坐標(biāo)數(shù)趨于穩(wěn)定，說(shuō)明算法在室內(nèi)場(chǎng)景中不同起點(diǎn)的情況下有效。

表2 室內(nèi)場(chǎng)景的統(tǒng)計(jì)結(jié)果/步數(shù)

同樣，室外場(chǎng)景中也針對(duì)n的每一次取值都分別執(zhí)行30、60、120次，記錄下每一次實(shí)驗(yàn)的結(jié)果并對(duì)實(shí)驗(yàn)數(shù)據(jù)進(jìn)行統(tǒng)計(jì)，統(tǒng)計(jì)結(jié)果見(jiàn)表3。從表3可知，n的取值對(duì)整個(gè)實(shí)驗(yàn)的結(jié)果影響不大，隨著實(shí)驗(yàn)次數(shù)的增加，機(jī)器人移動(dòng)的坐標(biāo)數(shù)趨于穩(wěn)定，說(shuō)明算法在室外場(chǎng)景中不同起點(diǎn)的情況下有效。

表3 室外場(chǎng)景的統(tǒng)計(jì)結(jié)果/步數(shù)

3.3.2 與經(jīng)典算法對(duì)比分析

隨機(jī)選取室內(nèi)與室外場(chǎng)景下連續(xù)測(cè)試120次，然后對(duì)120次的實(shí)驗(yàn)結(jié)果取平均，并將其作為搜索無(wú)線信號(hào)源的位置，再與PSO算法、GA算法進(jìn)行對(duì)比，結(jié)果見(jiàn)表4。從表4中可知，BAS與PSO、GA算法對(duì)比中可知，BAS的收斂速度最快，驗(yàn)證了算法的優(yōu)越性。

表4 3種算法對(duì)比

3.3.3 算法時(shí)間復(fù)雜度分析

從2.2節(jié)天牛須無(wú)線信號(hào)搜索算法原理可知，算法包含動(dòng)態(tài)計(jì)算無(wú)線信號(hào)與機(jī)器人之間的距離和不斷優(yōu)化下一步運(yùn)動(dòng)位置兩個(gè)部分，故其時(shí)間復(fù)雜度是這兩部的時(shí)間復(fù)雜度。假設(shè)一次搜索過(guò)程中，計(jì)算下一步運(yùn)動(dòng)位置的次數(shù)(節(jié)點(diǎn)數(shù))為M， 則時(shí)間復(fù)雜度為o(n2)。

證明[21]：第一部分(算法在優(yōu)化下一步運(yùn)動(dòng)位置)：計(jì)算f(x) 的最優(yōu)值(信號(hào)最強(qiáng))時(shí)，共計(jì)算n次，則時(shí)間復(fù)雜度為o(n)； 第二部分(動(dòng)態(tài)計(jì)算節(jié)點(diǎn)距離)：為了提高算法的準(zhǔn)確性與可靠性，每個(gè)節(jié)點(diǎn)的取值都是m次后取平均，則時(shí)間復(fù)雜度為o(n×m)。 算法中m=n， 所以其時(shí)間復(fù)雜度為

o(n×m+n)≈o(n2)

(13)

動(dòng)態(tài)計(jì)算搜索節(jié)點(diǎn)與無(wú)線信號(hào)源之間距離的時(shí)間復(fù)雜度為o(M)， 若M個(gè)節(jié)點(diǎn)同時(shí)搜索，則時(shí)間復(fù)雜度為o(M×n2)， 但整個(gè)算法中只需要一個(gè)機(jī)器人完成搜索，即只需要確定單個(gè)個(gè)體的位置。通過(guò)以上的分析可得，算法在單個(gè)個(gè)體搜索過(guò)程中的時(shí)間復(fù)雜度為o(n2)。

4 結(jié)束語(yǔ)

通過(guò)天牛須無(wú)線信號(hào)搜索算法，機(jī)器人在未知環(huán)境下進(jìn)行無(wú)線信號(hào)源搜尋，只需要一個(gè)信號(hào)感知器，簡(jiǎn)單方便的同時(shí)實(shí)現(xiàn)了高效的全局尋優(yōu)。實(shí)驗(yàn)結(jié)果表明，機(jī)器人在仿真的室內(nèi)與室外環(huán)境中都可以完成預(yù)定的無(wú)線信號(hào)源搜尋任務(wù)，同時(shí)結(jié)合與經(jīng)典算法的對(duì)方分析，驗(yàn)證了算法的優(yōu)越性。后續(xù)將在其它此類(lèi)的應(yīng)用場(chǎng)景中進(jìn)一步改善優(yōu)化算法。