，， ，

(中國(guó)科學(xué)技術(shù)大學(xué) 工程科學(xué)學(xué)院，合肥 230026)

基于RFID的移動(dòng)機(jī)器人巡邏路徑優(yōu)化研究

陳飛，董二寶，許旻，楊杰

(中國(guó)科學(xué)技術(shù)大學(xué)工程科學(xué)學(xué)院，合肥230026)

針對(duì)移動(dòng)機(jī)器人在大范圍環(huán)境中的巡邏路徑優(yōu)化問題，提出一種基于RFID信息節(jié)點(diǎn)導(dǎo)引方法的路徑和時(shí)間優(yōu)化策略;研究了在一由實(shí)際環(huán)境抽象得出的拓?fù)涞貓D環(huán)境下，使用RFID標(biāo)簽來(lái)標(biāo)記環(huán)境中的關(guān)鍵位置，例如走廊，交叉點(diǎn)，拐角等，并且利用標(biāo)簽中儲(chǔ)存的導(dǎo)航指令來(lái)指導(dǎo)移動(dòng)機(jī)器人的行動(dòng);將機(jī)器人分為3路巡邏，優(yōu)化得出巡邏總路程最短且歷經(jīng)信息節(jié)點(diǎn)數(shù)均衡的路徑;設(shè)定機(jī)器人在節(jié)點(diǎn)的停留時(shí)間，研究了機(jī)器人在一限定時(shí)間內(nèi)巡邏完所有節(jié)點(diǎn)的分組及路徑優(yōu)化方法;為大范圍布置RFID信息節(jié)點(diǎn)導(dǎo)引機(jī)器人行動(dòng)的環(huán)境下，提供了一種巡邏路徑優(yōu)化方案。

移動(dòng)機(jī)器人；射頻識(shí)別；導(dǎo)航；網(wǎng)絡(luò)優(yōu)化

0 引言

隨著機(jī)器人技術(shù)的發(fā)展，機(jī)器人被越來(lái)越多地應(yīng)用于博物館、醫(yī)院、辦公室等場(chǎng)合，如向人們提供物品傳送，陪伴老人，引導(dǎo)游客和娛樂等互動(dòng)服務(wù)。機(jī)器人的導(dǎo)航是完成這些任務(wù)的基礎(chǔ)，機(jī)器人的定位則是導(dǎo)航問題的基礎(chǔ)。目前機(jī)器人依靠自己的里程計(jì)來(lái)定位自身，但隨著工作環(huán)境范圍的擴(kuò)大，這種里程計(jì)會(huì)產(chǎn)生累積誤差，并且僅僅依靠它來(lái)實(shí)現(xiàn)機(jī)器人的自身定位還達(dá)不到所需的精度[1]。

研究人員提出了基于多傳感器融合的機(jī)器人自定位方法，這種方法是通過組合來(lái)自機(jī)器人自身所攜帶的傳感器的感知信息和里程計(jì)的信息[2]。但是在大范圍環(huán)境下，環(huán)境的不確定性也會(huì)影響定位的精度。近年來(lái)，使用地標(biāo)來(lái)輔助機(jī)器人的自定位，從而實(shí)現(xiàn)精確的導(dǎo)航已經(jīng)引起了學(xué)者的關(guān)注，并且已經(jīng)獲得了許多研究成果[3]。地標(biāo)的引入，可以降低機(jī)器人自身所攜帶傳感器的數(shù)量和精度，使得機(jī)器人得以高質(zhì)量地完成導(dǎo)航任務(wù)[4]。

針對(duì)機(jī)器人在大范圍環(huán)境下的巡邏問題，本文使用RFID信息節(jié)點(diǎn)來(lái)標(biāo)記環(huán)境中的關(guān)鍵位置，機(jī)器人通過讀取信息節(jié)點(diǎn)中的導(dǎo)航指令來(lái)導(dǎo)引機(jī)器人的行動(dòng)。主要研究了大范圍環(huán)境下RFID標(biāo)簽導(dǎo)引機(jī)器人巡邏問題的路徑優(yōu)化方法。

1 路徑導(dǎo)引方法

RFID是無(wú)線射頻辨識(shí)系統(tǒng)(radio frequency identification)的英文縮寫，是由閱讀器(reader)和RFID Tag(電子識(shí)別標(biāo)簽)所組成的系統(tǒng)。它的工作原理是當(dāng)電子識(shí)別標(biāo)簽進(jìn)入閱讀器的感應(yīng)范圍內(nèi)時(shí)，閱讀器即發(fā)射無(wú)線電波，RFID Tag產(chǎn)生感應(yīng)電流獲得其工作所需的電力，并回應(yīng)給閱讀器，是一種利用射頻通信完成非接觸式自動(dòng)識(shí)別的技術(shù)。以被動(dòng)式的電子識(shí)別標(biāo)簽為例，其尚未進(jìn)入閱讀器的感應(yīng)范圍內(nèi)時(shí)，標(biāo)簽是靜止的，當(dāng)標(biāo)簽進(jìn)入到閱讀器的感應(yīng)范圍內(nèi)時(shí)，標(biāo)簽即轉(zhuǎn)為啟動(dòng)狀態(tài)，閱讀器接收到標(biāo)簽信息之后傳送至應(yīng)用程序端作后續(xù)的處理[5]。

該導(dǎo)引方法首先需要獲取環(huán)境的平面地形圖，選擇標(biāo)簽節(jié)點(diǎn)的位置并創(chuàng)建相應(yīng)的導(dǎo)航指令表。標(biāo)簽節(jié)點(diǎn)的位置的選擇是簡(jiǎn)單的：部署在環(huán)境中機(jī)器人具有多個(gè)路徑選擇的交叉點(diǎn)位置以及機(jī)器人的起點(diǎn)及目的地節(jié)點(diǎn)的位置。當(dāng)機(jī)器人通過交叉點(diǎn)位置時(shí)，它查詢?cè)诮徊纥c(diǎn)位置處的標(biāo)簽信息，從而取得到到達(dá)目的地的導(dǎo)航指令，并執(zhí)行它[6]。

圖1說(shuō)明了存儲(chǔ)在RFID節(jié)點(diǎn)標(biāo)簽中的導(dǎo)航指令表所提供的信息。該圖示出了由機(jī)器人巡邏的區(qū)域的平面圖。由字母A，B，...，F(xiàn)標(biāo)記的圓圈表示存在多個(gè)路徑選擇或可能的目的地的位置處的信息節(jié)點(diǎn)。節(jié)點(diǎn)S是該區(qū)域的入口點(diǎn)。在該圖中，節(jié)點(diǎn)B，C，E，F(xiàn)是目的地節(jié)點(diǎn)，它們的唯一功能是標(biāo)記各個(gè)位置。節(jié)點(diǎn)A和D是機(jī)器人必須選擇在這些位置中的每一個(gè)之后采取多條路徑中的哪一條的位置。表1示出了存儲(chǔ)在節(jié)點(diǎn)A處的導(dǎo)航指令表的一部分。

圖1 拓?fù)涞貓D示例

上一個(gè)節(jié)點(diǎn)ID目標(biāo)節(jié)點(diǎn)ID發(fā)送指令下一個(gè)節(jié)點(diǎn)IDSB左轉(zhuǎn)135°BC左轉(zhuǎn)45°CE直行DF直行DBS右轉(zhuǎn)135°SC左轉(zhuǎn)90°CE左轉(zhuǎn)45°DF左轉(zhuǎn)45°DCS右轉(zhuǎn)45°SB右轉(zhuǎn)90°BE左轉(zhuǎn)135°DF左轉(zhuǎn)135°D

機(jī)器人上安裝有讀取RFID標(biāo)簽的閱讀器，標(biāo)簽在閱讀器的讀取范圍之內(nèi)時(shí)，標(biāo)簽從閱讀器發(fā)出的射頻能量中提取工作所需的電能。每個(gè)節(jié)點(diǎn)都有自己的ID，通過讀取節(jié)點(diǎn)信息，機(jī)器人可以獲取導(dǎo)航指令。

2 巡邏路徑問題

2.1 問題分析

圖1僅僅是為了說(shuō)明導(dǎo)引方法的一個(gè)簡(jiǎn)單示例，然而實(shí)際應(yīng)用環(huán)境要復(fù)雜很多，尤其是在大范圍環(huán)境下的機(jī)器人巡邏問題，所布置的節(jié)點(diǎn)數(shù)量巨大。在大范圍環(huán)境下，機(jī)器人的巡邏路徑是需要做優(yōu)化的。本文將一實(shí)際巡邏環(huán)境抽象得到其拓?fù)涞貓D環(huán)境，如圖2所示[7]。

圖2 拓?fù)涞貓D

字母A，B，...，R標(biāo)記的為一級(jí)節(jié)點(diǎn)，數(shù)字1，2，...，35標(biāo)記的為二級(jí)節(jié)點(diǎn)，字母O為機(jī)器人的起點(diǎn)。假設(shè)機(jī)器人的行駛速度恒定，且在巡邏途中，在每級(jí)節(jié)點(diǎn)的停留時(shí)間一定。

將機(jī)器人分為3路巡邏，設(shè)計(jì)一總路徑最短且各路節(jié)點(diǎn)數(shù)目盡可能均衡的路線。將節(jié)點(diǎn)間的路徑看作圖中對(duì)應(yīng)節(jié)點(diǎn)間的邊，各個(gè)節(jié)點(diǎn)間的距離看作對(duì)應(yīng)的邊的權(quán)，則上圖所示的拓?fù)涞貓D就轉(zhuǎn)化為加權(quán)網(wǎng)絡(luò)圖。問題便轉(zhuǎn)化為在給定的加權(quán)圖中從一起點(diǎn)出發(fā)，行遍所有節(jié)點(diǎn)后再回到起點(diǎn)，使得總權(quán)值最小[8]。

設(shè)G(V，E)為拓?fù)涞貓D的賦權(quán)無(wú)向連通圖，將其分為3個(gè)連通的子圖Gi，并且每個(gè)子圖都與起點(diǎn)O相連接，然后在每個(gè)子圖當(dāng)中尋找一條包含O點(diǎn)的最佳回路。采用Kruskal算法求解出圖G的最小樹圖，然后將其分為3個(gè)子區(qū)域，最后，采用哈密頓回路法求解出每個(gè)子圖內(nèi)的最佳巡邏路徑[9]。

2.2 最小生成樹

最小生成樹可以包含圖G中的所有節(jié)點(diǎn)，而最小生成樹的邊權(quán)是相鄰兩節(jié)點(diǎn)之間的距離，所以可以采用最小生成樹將圖G中的節(jié)點(diǎn)進(jìn)行分組。算法可分成三步：1)選取邊ei，使得權(quán)值之和w(ei)最小；2)設(shè)e1，e2，...，ei已經(jīng)被選取，則在E={e1，e2，...，ei}中選取邊ei+1使得：(i)G[{e1，e2，...，ei+1}]中不含圈；(ii)w(ei+1)盡可能地??；3)當(dāng)?shù)?步不能再進(jìn)行時(shí)則停止。得到圖G的最小生成樹如圖3所示[10]。

圖3 最小生成樹

3 路徑優(yōu)化

3.1 路程最短

現(xiàn)在將機(jī)器人分為三組路徑進(jìn)行巡邏，需要把圖G分為3個(gè)子圖Gi(i=1,2,3)，在每個(gè)子圖Gi中尋找最佳的回路Li(i=1,2,3)。由于該問題不存在多項(xiàng)式時(shí)間內(nèi)的精確解，且圖中節(jié)點(diǎn)數(shù)目較多，所以只能遵循一種稍合理的劃分原則，初步劃分之后，再求出各區(qū)域近似最佳回路的權(quán)，然后進(jìn)行進(jìn)一步調(diào)整，最后使得各部分滿足均衡性條件。

將得到的最小生成樹進(jìn)行分解，獲得3個(gè)子圖Gi并使得分解后的結(jié)果盡量均衡。在最小生成樹中，邊權(quán)接近可以近似認(rèn)為其均衡，也就是各個(gè)子圖包含的節(jié)點(diǎn)數(shù)目是相近的。因此各個(gè)子圖的節(jié)點(diǎn)數(shù)目應(yīng)當(dāng)盡可能地接近17個(gè)，并且遵循以下4條劃分原則：1)劃分點(diǎn)為O或者盡可能地接近O點(diǎn)；2)劃分后所得出的3個(gè)子圖Gi的節(jié)點(diǎn)數(shù)目應(yīng)當(dāng)盡可能地接近17個(gè)；3)盡量使得劃分后所得到的子圖是連通的；4)盡量使得子圖Gi和節(jié)點(diǎn)O的最短路徑上的節(jié)點(diǎn)在子圖內(nèi)，并且使得各個(gè)子圖的節(jié)點(diǎn)在子圖的內(nèi)部形成環(huán)路。

之后采用哈密頓回路法求解出各個(gè)子圖的最佳巡邏路徑。尋找最佳巡邏路徑也就是在圖中尋找最優(yōu)的哈密頓圈，而包含圖中所有節(jié)點(diǎn)的圈稱為哈密頓圈。于是問題轉(zhuǎn)化為已知3個(gè)子圖中各個(gè)節(jié)點(diǎn)之間的距離，從起點(diǎn)O出發(fā)，經(jīng)過子圖中的所有節(jié)點(diǎn)，最后又回到節(jié)點(diǎn)O[11]。

根據(jù)以上分析確定每個(gè)機(jī)器人的巡邏區(qū)域，由拓?fù)涞貓D構(gòu)造出賦權(quán)網(wǎng)絡(luò)圖G=(N，E，W)，其中:

N={0,1,2...,52},

E={(i,j)|i,j∈N},

W={w(i,j)|i,j∈N}

(1)

而決策變量定義為：

(2)

目標(biāo)函數(shù)則為：

(3)

α被定義為均衡度，取值在0～1之間，值越小說(shuō)明分組的路徑均衡度越好。目標(biāo)函數(shù)給出了最小哈密頓圈長(zhǎng)度的表達(dá)式。約束:

(4)

使得機(jī)器人只到達(dá)每個(gè)節(jié)點(diǎn)一次，約束:

(5)

使得機(jī)器人只離開每個(gè)節(jié)點(diǎn)一次，約束條件總結(jié)為：

(6)

求得的巡邏路徑分布如圖4所示[12]。

圖4 最短巡邏路徑優(yōu)化結(jié)果

3.2 限定時(shí)間

設(shè)定機(jī)器人在一級(jí)節(jié)點(diǎn)的停留時(shí)間為2 min，在二級(jí)節(jié)點(diǎn)的停留時(shí)間為1 min，以及機(jī)器人的行駛速度為35 m每分鐘，要求機(jī)器人在24 min內(nèi)完成該拓?fù)涞貓D環(huán)境的巡邏?？芍患?jí)節(jié)點(diǎn)共有17個(gè)，二級(jí)節(jié)點(diǎn)共有35個(gè)，于是可以計(jì)算得到機(jī)器人在所有節(jié)點(diǎn)停留的總時(shí)間為17*2+35=69 min。此外，從之前的分析結(jié)果可知，巡邏的總里程至少為500 m，所以機(jī)器人行駛所需要的總時(shí)間至少為14 min。由此可得，每路巡邏所需要的總時(shí)間之和超過83 min，因此要想在24 min內(nèi)完成該巡邏則應(yīng)該滿足：83/i<24(i為分的組數(shù))。得到i的最小值為4，所以至少應(yīng)分為4組。

現(xiàn)在嘗試將標(biāo)簽節(jié)點(diǎn)分為4組，分組的原則建立在最小生成樹的分解原則上，所以應(yīng)當(dāng)遵循以下原則：1)分解點(diǎn)為起點(diǎn)O或盡可能地接近起點(diǎn)O；2)分解后所得到的4個(gè)子圖的節(jié)點(diǎn)數(shù)目應(yīng)當(dāng)盡可能地接近14個(gè)；3)盡量應(yīng)當(dāng)使分解所得的子圖是連通圖；4)盡量使子圖Gi與起點(diǎn)O的最短路徑上的節(jié)點(diǎn)在該子圖的內(nèi)部，并且盡量使得各子圖的節(jié)點(diǎn)在子圖的內(nèi)部形成環(huán)路；5)盡量使得各路機(jī)器人的巡邏時(shí)間相等。

采用上述原則將圖G分成為4個(gè)子圖，并應(yīng)用哈密頓回路法找出各路的最佳巡邏路徑。然后計(jì)算得出各組最佳巡邏路徑的總長(zhǎng)度及機(jī)器人行駛所需的時(shí)間，同時(shí)計(jì)算得到各組巡邏路徑的機(jī)器人停留時(shí)間，從而得出各路巡邏的總時(shí)間。目標(biāo)函數(shù)為:

(7)

每路機(jī)器人巡邏過程中，往返時(shí)間不超過24 min，即：

(8)

其中:ai為第i路機(jī)器人巡邏經(jīng)過的一級(jí)節(jié)點(diǎn)數(shù)，bi為第i路機(jī)器人巡邏經(jīng)過的二級(jí)節(jié)點(diǎn)數(shù)。則針對(duì)此問題的約束條件概括為:

(9)

所得到的巡邏路徑如圖5所示。

圖5 限定時(shí)間巡邏路徑優(yōu)化結(jié)果

4 試驗(yàn)結(jié)果與分析

本研究選定一寬闊場(chǎng)地作測(cè)試實(shí)驗(yàn)，可避免空間中其他干擾因素的影響。實(shí)驗(yàn)場(chǎng)地的標(biāo)簽排布距離是每隔1.8 m放置一個(gè)RFID標(biāo)簽，所使用的移動(dòng)機(jī)器人平臺(tái)如圖6所示，而地面附近則為所布設(shè)的RFID電子標(biāo)簽。另在RFID讀取器的安置高度方面，設(shè)置為離地面5厘米，以使其可以有效讀取標(biāo)簽內(nèi)的相關(guān)信息。

圖6 移動(dòng)機(jī)器人平臺(tái)

實(shí)施的測(cè)試項(xiàng)目分為以下6項(xiàng)：?jiǎn)味我苿?dòng)測(cè)試；多段移動(dòng)測(cè)試；環(huán)狀移動(dòng)測(cè)試；格狀移動(dòng)測(cè)試；交叉狀移動(dòng)測(cè)試；多線段移動(dòng)測(cè)試。路徑軌跡如圖7所示。

圖7 路徑軌跡

通過上述6種不同類型的路徑測(cè)試，記錄下RFID讀取器經(jīng)過路徑上任意相鄰兩組標(biāo)簽之間的時(shí)間讀取誤差，并且在移動(dòng)平臺(tái)經(jīng)過標(biāo)簽節(jié)點(diǎn)之際，采用人工輔助的方式加以記錄時(shí)間誤差，以此測(cè)試RFID讀取標(biāo)簽節(jié)點(diǎn)的效果。測(cè)試得到的相關(guān)數(shù)據(jù)結(jié)果整理如表2所示。

表2 不同類型路徑的節(jié)點(diǎn)讀取時(shí)間間隔

由表2的時(shí)間讀取測(cè)試結(jié)果可知，RFID閱讀器讀取標(biāo)簽信息的時(shí)間反應(yīng)誤差大約在0.3～0.5 s之間，而根據(jù)6種不同移動(dòng)路徑所測(cè)得的標(biāo)簽節(jié)點(diǎn)平均讀取時(shí)間誤差則為0.4 s，造成這種誤差的主要原因應(yīng)該是RFID讀取器的系統(tǒng)反應(yīng)時(shí)間及移動(dòng)路徑的復(fù)雜程度所導(dǎo)致，該問題可以通過改換較高性能的RFID硬件加以解決。

而針對(duì)上文中的兩個(gè)巡邏路徑優(yōu)化問題的結(jié)果對(duì)比如表2所示，可以看到均衡度均較好，符合實(shí)際分派巡邏任務(wù)的情況。

表3 巡邏路徑優(yōu)化結(jié)果

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

本文考慮RFID在移動(dòng)機(jī)器人路徑導(dǎo)引中的應(yīng)用，并對(duì)機(jī)器人巡邏路徑的優(yōu)化做了分析研究。通過求解最小生成樹，進(jìn)行節(jié)點(diǎn)分組，對(duì)巡邏問題進(jìn)行簡(jiǎn)化，得到了均勻性較好的分組巡邏路徑。通過試驗(yàn)測(cè)試，RFID確實(shí)具有協(xié)助移動(dòng)機(jī)器人巡邏導(dǎo)引的潛能。同時(shí)，本文針對(duì)該巡邏問題的解決也還有不足。試驗(yàn)中存在標(biāo)簽讀取的時(shí)間誤差現(xiàn)象，如果要提高路徑探測(cè)的精度，需要加大RFID節(jié)點(diǎn)標(biāo)簽的布置數(shù)量和密度，必要時(shí)需要改換更高性能的RFID硬件。

[1] Kato Y. Research and development environments for robot services and its implementation[A]. 2011 IEEE/SICE International Symposium on System Integration (SII)[C]. Kyoto, 2011:306-311.

[2] Doki K, Suyama K, Funabora Y,et al.Robust localization for mobile robot by K-L Divergence-based sensor data fusion[A]. IECON 2015 - 41st Annual Conference of the IEEE[C]. Yokohama, 2015: 002638-002643.

[3] 艾明曦, 時(shí) 偉. 基于低成本INS/RFID的室內(nèi)定位技術(shù)[J]. 計(jì)算機(jī)測(cè)量與控制, 2016,24 (4): 122-125.

[4] Takahashi Y.Mobile robot self localization based on multi-antenna-RFID reader and IC tag textile[A]. 2013 IEEE Workshop on Advanced Robotics and its Social Impacts[C]. Tokyo, 2013:106-112.

[5] Mi J,Takahashi Y.Low cost design of HF-band RFID system for mobile robot self-localization based on multiple readers and tags[A]. 2015 IEEE International Conference on Robotics and Biomimetics (ROBIO)[C]. Zhuhai, 2015: 194-199.

[6] Lu F, Wang X,Tian G.The structure and application of intelligent space system oriented to home service robot[A]. 2012 International Conference on Information and Automation (ICIA) [C]. Shenyang, 2012: 289-294.

[7] Kavraki E, Svestka P, Latombe J C,et al.Probabilistic roadmaps for path planning in high-dimensional configuration spaces[J]. IEEE Transactions on Robotics and Automation.1996,12(4):566-580.

[8] 吳忻生, 竹利平, 胡躍明. 一種改進(jìn)的移動(dòng)機(jī)器人全局路徑規(guī)劃算法[J]. 計(jì)算機(jī)測(cè)量與控制, 2003 11 (11): 890-892.

[9] 張歆奕, 吳今培, 張其善. 車載導(dǎo)航儀中路徑規(guī)劃算法及其實(shí)現(xiàn)[J]. 計(jì)算機(jī)測(cè)量與控制, 2001,9 (4): 15-17.

[10] Asadi S, Azimirad V, Eslami A,et al.A novel global optimal path planning and trajectory method based on adaptive dijkstra-immune approach for mobile robot[A]. Advanced Intelligent Mechatronics (AIM), 2011 IEEE/ASME International Conference on[C]. Budapest, 2011:1093-1098.

[11] Yao L, Wu J, Wang Y, et al.Research on vehicle integrated control algorithm based on MATLAB and CANoe co-simulation[A]. 2014 IEEE Transportation Electrification Conference and Expo (ITEC) Asia-Pacific[C]. 2014.

[12] Han S, Lim H, Lee J.An Efficient localization scheme for a differential-driving mobile Robot Based on RFID System[J]. IEEE Transactions on Industrial Electronics,2007, 54 (6): 3362-3369.

ResearchonPatrolPathOptimizationofMobileRobotBasedonRFID

Chen Fei，Dong Erbao，Xu Min，Yang Jie

(School of Engineering Science, University of Science and Technology of China,Hefei 230026, China)

Aiming at the problem of path optimization of mobile robot in a wide range of environments, this paper proposed a route and time optimization strategy based on RFID nodes’ navigation instruction. In a topological map environment, using the RFID information nodes to label critical locations such as corridors, intersections, corners and so on in the environment and guide the robot with navigation instruction. The robots are divided into three patrols to solve the total distance of the shortest and balanced route. Set the robot at the node's dwell time, study the path optimization method for traversal all nodes at a given time. This study provides a path optimization scheme for large-scale placement of RFID nodes to guide robots.

mobile robot; RFID; navigation; network optimization

2017-03-28；

2017-04-15。

國(guó)家自然科學(xué)基金項(xiàng)目(51275501)。

陳 飛(1991-)，男，安徽合肥人，碩士研究生，主要從事移動(dòng)機(jī)器人方向的研究。

楊 杰(1946-)，男，上海市人，教授，主要從事仿生機(jī)器人方向的研究。

1671-4598(2017)10-0194-04

10.16526/j.cnki.11-4762/tp.2017.10.049

TP242

A