，， ，

(中國科學技術大學 工程科學學院，合肥 230026)

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

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

(中國科學技術大學工程科學學院，合肥230026)

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

移動機器人；射頻識別；導航；網(wǎng)絡優(yōu)化

0 引言

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

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

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

1 路徑導引方法

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

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

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

圖1 拓撲地圖示例

上一個節(jié)點ID目標節(jié)點ID發(fā)送指令下一個節(jié)點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

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

2 巡邏路徑問題

2.1 問題分析

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

圖2 拓撲地圖

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

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

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

2.2 最小生成樹

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

圖3 最小生成樹

3 路徑優(yōu)化

3.1 路程最短

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

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

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

根據(jù)以上分析確定每個機器人的巡邏區(qū)域，由拓撲地圖構造出賦權網(wǎng)絡圖G=(N，E，W)，其中:

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

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

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

(1)

而決策變量定義為：

(2)

目標函數(shù)則為：

(3)

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

(4)

使得機器人只到達每個節(jié)點一次，約束:

(5)

使得機器人只離開每個節(jié)點一次，約束條件總結為：

(6)

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

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

3.2 限定時間

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

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

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

(7)

每路機器人巡邏過程中，往返時間不超過24 min，即：

(8)

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

(9)

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

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

4 試驗結果與分析

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

圖6 移動機器人平臺

實施的測試項目分為以下6項：單段移動測試；多段移動測試；環(huán)狀移動測試；格狀移動測試；交叉狀移動測試；多線段移動測試。路徑軌跡如圖7所示。

圖7 路徑軌跡

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

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

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

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

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

5 結束語

本文考慮RFID在移動機器人路徑導引中的應用，并對機器人巡邏路徑的優(yōu)化做了分析研究。通過求解最小生成樹，進行節(jié)點分組，對巡邏問題進行簡化，得到了均勻性較好的分組巡邏路徑。通過試驗測試，RFID確實具有協(xié)助移動機器人巡邏導引的潛能。同時，本文針對該巡邏問題的解決也還有不足。試驗中存在標簽讀取的時間誤差現(xiàn)象，如果要提高路徑探測的精度，需要加大RFID節(jié)點標簽的布置數(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] 艾明曦, 時 偉. 基于低成本INS/RFID的室內(nèi)定位技術[J]. 計算機測量與控制, 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] 吳忻生, 竹利平, 胡躍明. 一種改進的移動機器人全局路徑規(guī)劃算法[J]. 計算機測量與控制, 2003 11 (11): 890-892.

[9] 張歆奕, 吳今培, 張其善. 車載導航儀中路徑規(guī)劃算法及其實現(xiàn)[J]. 計算機測量與控制, 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。

國家自然科學基金項目(51275501)。

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

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

1671-4598(2017)10-0194-04

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

TP242

A