基于RFID的移动机器人巡逻路径优化研究

，， ，

(中国科学技术大学 工程科学学院，合肥 230026)

基于RFID的移动机器人巡逻路径优化研究

陈飞，董二宝，许旻，杨杰

(中国科学技术大学工程科学学院，合肥230026)

针对移动机器人在大范围环境中的巡逻路径优化问题，提出一种基于RFID信息节点导引方法的路径和时间优化策略;研究了在一由实际环境抽象得出的拓扑地图环境下，使用RFID标签来标记环境中的关键位置，例如走廊，交叉点，拐角等，并且利用标签中储存的导航指令来指导移动机器人的行动;将机器人分为3路巡逻，优化得出巡逻总路程最短且历经信息节点数均衡的路径;设定机器人在节点的停留时间，研究了机器人在一限定时间内巡逻完所有节点的分组及路径优化方法;为大范围布置RFID信息节点导引机器人行动的环境下，提供了一种巡逻路径优化方案。

移动机器人；射频识别；导航；网络优化

0 引言

随着机器人技术的发展，机器人被越来越多地应用于博物馆、医院、办公室等场合，如向人们提供物品传送，陪伴老人，引导游客和娱乐等互动服务。机器人的导航是完成这些任务的基础，机器人的定位则是导航问题的基础。目前机器人依靠自己的里程计来定位自身，但随着工作环境范围的扩大，这种里程计会产生累积误差，并且仅仅依靠它来实现机器人的自身定位还达不到所需的精度[1]。

研究人员提出了基于多传感器融合的机器人自定位方法，这种方法是通过组合来自机器人自身所携带的传感器的感知信息和里程计的信息[2]。但是在大范围环境下，环境的不确定性也会影响定位的精度。近年来，使用地标来辅助机器人的自定位，从而实现精确的导航已经引起了学者的关注，并且已经获得了许多研究成果[3]。地标的引入，可以降低机器人自身所携带传感器的数量和精度，使得机器人得以高质量地完成导航任务[4]。

针对机器人在大范围环境下的巡逻问题，本文使用RFID信息节点来标记环境中的关键位置，机器人通过读取信息节点中的导航指令来导引机器人的行动。主要研究了大范围环境下RFID标签导引机器人巡逻问题的路径优化方法。

1 路径导引方法

RFID是无线射频辨识系统(radio frequency identification)的英文缩写，是由阅读器(reader)和RFID Tag(电子识别标签)所组成的系统。它的工作原理是当电子识别标签进入阅读器的感应范围内时，阅读器即发射无线电波，RFID Tag产生感应电流获得其工作所需的电力，并回应给阅读器，是一种利用射频通信完成非接触式自动识别的技术。以被动式的电子识别标签为例，其尚未进入阅读器的感应范围内时，标签是静止的，当标签进入到阅读器的感应范围内时，标签即转为启动状态，阅读器接收到标签信息之后传送至应用程序端作后续的处理[5]。

该导引方法首先需要获取环境的平面地形图，选择标签节点的位置并创建相应的导航指令表。标签节点的位置的选择是简单的：部署在环境中机器人具有多个路径选择的交叉点位置以及机器人的起点及目的地节点的位置。当机器人通过交叉点位置时，它查询在交叉点位置处的标签信息，从而取得到到达目的地的导航指令，并执行它[6]。

图1说明了存储在RFID节点标签中的导航指令表所提供的信息。该图示出了由机器人巡逻的区域的平面图。由字母A，B，...，F标记的圆圈表示存在多个路径选择或可能的目的地的位置处的信息节点。节点S是该区域的入口点。在该图中，节点B，C，E，F是目的地节点，它们的唯一功能是标记各个位置。节点A和D是机器人必须选择在这些位置中的每一个之后采取多条路径中的哪一条的位置。表1示出了存储在节点A处的导航指令表的一部分。

图1 拓扑地图示例

上一个节点ID目标节点ID发送指令下一个节点IDSB左转135°BC左转45°CE直行DF直行DBS右转135°SC左转90°CE左转45°DF左转45°DCS右转45°SB右转90°BE左转135°DF左转135°D

机器人上安装有读取RFID标签的阅读器，标签在阅读器的读取范围之内时，标签从阅读器发出的射频能量中提取工作所需的电能。每个节点都有自己的ID，通过读取节点信息，机器人可以获取导航指令。

2 巡逻路径问题

2.1 问题分析

图1仅仅是为了说明导引方法的一个简单示例，然而实际应用环境要复杂很多，尤其是在大范围环境下的机器人巡逻问题，所布置的节点数量巨大。在大范围环境下，机器人的巡逻路径是需要做优化的。本文将一实际巡逻环境抽象得到其拓扑地图环境，如图2所示[7]。

图2 拓扑地图

字母A，B，...，R标记的为一级节点，数字1，2，...，35标记的为二级节点，字母O为机器人的起点。假设机器人的行驶速度恒定，且在巡逻途中，在每级节点的停留时间一定。

将机器人分为3路巡逻，设计一总路径最短且各路节点数目尽可能均衡的路线。将节点间的路径看作图中对应节点间的边，各个节点间的距离看作对应的边的权，则上图所示的拓扑地图就转化为加权网络图。问题便转化为在给定的加权图中从一起点出发，行遍所有节点后再回到起点，使得总权值最小[8]。

设G(V，E)为拓扑地图的赋权无向连通图，将其分为3个连通的子图Gi，并且每个子图都与起点O相连接，然后在每个子图当中寻找一条包含O点的最佳回路。采用Kruskal算法求解出图G的最小树图，然后将其分为3个子区域，最后，采用哈密顿回路法求解出每个子图内的最佳巡逻路径[9]。

2.2 最小生成树

最小生成树可以包含图G中的所有节点，而最小生成树的边权是相邻两节点之间的距离，所以可以采用最小生成树将图G中的节点进行分组。算法可分成三步：1)选取边ei，使得权值之和w(ei)最小；2)设e1，e2，...，ei已经被选取，则在E={e1，e2，...，ei}中选取边ei+1使得：(i)G[{e1，e2，...，ei+1}]中不含圈；(ii)w(ei+1)尽可能地小；3)当第2步不能再进行时则停止。得到图G的最小生成树如图3所示[10]。

图3 最小生成树

3 路径优化

3.1 路程最短

现在将机器人分为三组路径进行巡逻，需要把图G分为3个子图Gi(i=1,2,3)，在每个子图Gi中寻找最佳的回路Li(i=1,2,3)。由于该问题不存在多项式时间内的精确解，且图中节点数目较多，所以只能遵循一种稍合理的划分原则，初步划分之后，再求出各区域近似最佳回路的权，然后进行进一步调整，最后使得各部分满足均衡性条件。

将得到的最小生成树进行分解，获得3个子图Gi并使得分解后的结果尽量均衡。在最小生成树中，边权接近可以近似认为其均衡，也就是各个子图包含的节点数目是相近的。因此各个子图的节点数目应当尽可能地接近17个，并且遵循以下4条划分原则：1)划分点为O或者尽可能地接近O点；2)划分后所得出的3个子图Gi的节点数目应当尽可能地接近17个；3)尽量使得划分后所得到的子图是连通的；4)尽量使得子图Gi和节点O的最短路径上的节点在子图内，并且使得各个子图的节点在子图的内部形成环路。

之后采用哈密顿回路法求解出各个子图的最佳巡逻路径。寻找最佳巡逻路径也就是在图中寻找最优的哈密顿圈，而包含图中所有节点的圈称为哈密顿圈。于是问题转化为已知3个子图中各个节点之间的距离，从起点O出发，经过子图中的所有节点，最后又回到节点O[11]。

根据以上分析确定每个机器人的巡逻区域，由拓扑地图构造出赋权网络图G=(N，E，W)，其中:

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

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

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

(1)

而决策变量定义为：

(2)

目标函数则为：

(3)

α被定义为均衡度，取值在0～1之间，值越小说明分组的路径均衡度越好。目标函数给出了最小哈密顿圈长度的表达式。约束:

(4)

使得机器人只到达每个节点一次，约束:

(5)

使得机器人只离开每个节点一次，约束条件总结为：

(6)

求得的巡逻路径分布如图4所示[12]。

图4 最短巡逻路径优化结果

3.2 限定时间

设定机器人在一级节点的停留时间为2 min，在二级节点的停留时间为1 min，以及机器人的行驶速度为35 m每分钟，要求机器人在24 min内完成该拓扑地图环境的巡逻。可知一级节点共有17个，二级节点共有35个，于是可以计算得到机器人在所有节点停留的总时间为17*2+35=69 min。此外，从之前的分析结果可知，巡逻的总里程至少为500 m，所以机器人行驶所需要的总时间至少为14 min。由此可得，每路巡逻所需要的总时间之和超过83 min，因此要想在24 min内完成该巡逻则应该满足：83/i<24(i为分的组数)。得到i的最小值为4，所以至少应分为4组。

现在尝试将标签节点分为4组，分组的原则建立在最小生成树的分解原则上，所以应当遵循以下原则：1)分解点为起点O或尽可能地接近起点O；2)分解后所得到的4个子图的节点数目应当尽可能地接近14个；3)尽量应当使分解所得的子图是连通图；4)尽量使子图Gi与起点O的最短路径上的节点在该子图的内部，并且尽量使得各子图的节点在子图的内部形成环路；5)尽量使得各路机器人的巡逻时间相等。

采用上述原则将图G分成为4个子图，并应用哈密顿回路法找出各路的最佳巡逻路径。然后计算得出各组最佳巡逻路径的总长度及机器人行驶所需的时间，同时计算得到各组巡逻路径的机器人停留时间，从而得出各路巡逻的总时间。目标函数为:

(7)

每路机器人巡逻过程中，往返时间不超过24 min，即：

(8)

其中:ai为第i路机器人巡逻经过的一级节点数，bi为第i路机器人巡逻经过的二级节点数。则针对此问题的约束条件概括为:

(9)

所得到的巡逻路径如图5所示。

图5 限定时间巡逻路径优化结果

4 试验结果与分析

本研究选定一宽阔场地作测试实验，可避免空间中其他干扰因素的影响。实验场地的标签排布距离是每隔1.8 m放置一个RFID标签，所使用的移动机器人平台如图6所示，而地面附近则为所布设的RFID电子标签。另在RFID读取器的安置高度方面，设置为离地面5厘米，以使其可以有效读取标签内的相关信息。

图6 移动机器人平台

实施的测试项目分为以下6项：单段移动测试；多段移动测试；环状移动测试；格状移动测试；交叉状移动测试；多线段移动测试。路径轨迹如图7所示。

图7 路径轨迹

通过上述6种不同类型的路径测试，记录下RFID读取器经过路径上任意相邻两组标签之间的时间读取误差，并且在移动平台经过标签节点之际，采用人工辅助的方式加以记录时间误差，以此测试RFID读取标签节点的效果。测试得到的相关数据结果整理如表2所示。

表2 不同类型路径的节点读取时间间隔

由表2的时间读取测试结果可知，RFID阅读器读取标签信息的时间反应误差大约在0.3～0.5 s之间，而根据6种不同移动路径所测得的标签节点平均读取时间误差则为0.4 s，造成这种误差的主要原因应该是RFID读取器的系统反应时间及移动路径的复杂程度所导致，该问题可以通过改换较高性能的RFID硬件加以解决。

而针对上文中的两个巡逻路径优化问题的结果对比如表2所示，可以看到均衡度均较好，符合实际分派巡逻任务的情况。

表3 巡逻路径优化结果

5 结束语

本文考虑RFID在移动机器人路径导引中的应用，并对机器人巡逻路径的优化做了分析研究。通过求解最小生成树，进行节点分组，对巡逻问题进行简化，得到了均匀性较好的分组巡逻路径。通过试验测试，RFID确实具有协助移动机器人巡逻导引的潜能。同时，本文针对该巡逻问题的解决也还有不足。试验中存在标签读取的时间误差现象，如果要提高路径探测的精度，需要加大RFID节点标签的布置数量和密度，必要时需要改换更高性能的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的室内定位技术[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] 吴忻生, 竹利平, 胡跃明. 一种改进的移动机器人全局路径规划算法[J]. 计算机测量与控制, 2003 11 (11): 890-892.

[9] 张歆奕, 吴今培, 张其善. 车载导航仪中路径规划算法及其实现[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