一种基于RFID场景布局的AGV改进花朵授粉定位算法

韩共乐，张接信，张富强

HAN Gong-le,ZHANG Jie-xin,ZHANG Fu-qiang

（长安大学 道路施工技术与装备教育部重点实验室，西安 710064）

0 引言

AGV（Automated Guided Vehicle）是指应用于工业生产中具备自动导引功能的搬运车。无需轨道铺设，不受场地、道路和空间限制等优势，高效、准确、经济、灵活的自动运料功能可显著提高制造系统的生产柔性和市场竞争力[1,2]。当前，新一代IT技术（物联网、大数据、云计算）与智能物流装备技术蓬勃发展，正逐步改变我国物流行业管理效率低下、信息化程度较低的现状，降低物流成本的同时推动着我国物流智能化的变革。

AGV定位问题是学术界研究的热点，也是工业领域推广应用的难点。目前主流的3种AGV导引方式分别是磁导引、激光导引和视觉导引。其中磁导引方式的成本最低也较容易实现，其定位方式也较简单，但精确低；采用激光导引AGV的定位精度高，但其成本较高，且设备安装难度大；采用视觉导引AGV具有导引精度高、性价比好等特点，但是其技术还不太成熟[3]。RFID（Radio Frequency Identification）技术的成熟应用，为我们研究AGV定位问题提供了新的思路。将RFID技术应用于AGV定位中，不仅可以提高AGV定位精度，还可以降低AGV的定位成本[4]。

另一方面，一些新型智能优化算法在求解AGV位置过程中存在不足之处。例如，粒子群算法和差分进化算法应用于AGV定位时精度差，易陷于局部最优，BP神经网络算法和遗传算法运算速度慢，时效性弱，萤火虫算法定位精度低而且定位速度慢[5]。花朵授粉算法（Flower pollination algorithm，简称FPA）是根据自然界中植物花朵授粉行为机理进行模拟而设计的一种新型启发式优化算法，其局部搜索和全局搜索过程分别模拟自花授粉和异花授粉行为，利用转换概率动态地控制全局搜索和局部搜索之间的转换，较好地解决了全局搜索和局部搜索之间的平衡问题[6]。FPA具有参数少、易调节、搜索能力强、鲁棒性强、实现简单等优点，在定位计算上可以取得很高的精度。

因此，本文首先根据RFID信号的强弱估算出AGV和固定读写器之间的距离；然后根据读写器的位置信息，以及估算出的AGV和读写器之间的距离，建立花朵授粉算法模型；最后采用花朵授粉算法精确定位AGV。

1 RFID定位模型

在自动化生产车间内，每隔n米的距离布置一个RFID读写器，以确保RFID信号的全覆盖。在RFID信号网络覆盖整个生产车间的基础上，在AGV上粘贴电子标签，当AGV在车间行走时，选择离AGV最近的m个RFID读写器（读写器坐标为（xi，yi））来实现AGV定位。

RFID信号在传播过程中一定会有衰减，可以根据RFID信号强弱初步估计待定位的AGV到读写器的距离。设定初步估计的RFID读写器到待定位的AGV的距离为Ci，设当前坐标Q（x0，y0）到m个RFID读写器之间的距离Ei。

本文以距离为Ci与距离Ei之差的平方和的最小值为优化目标，相应的数学模型如下：

优化目标：

其他条件：

式(1)为优化目标函数；式(2)为室内环境下RFID信号衰减与距离的传播模型；式(3)为当前坐标Q（x0，y0）到m个RFID读写器之间的距离公式；式(4)表示下标变量的取值范围。

2 花朵授粉算法求解

2.1 基本花朵授粉算法

花朵授粉算法是一种新型的优化算法。基于在传粉过程中花朵的异花授粉行为与自花授粉行为将花朵授粉算法的搜索过程分为全局搜索过程与局部搜索过程，为了协调两种搜索过程间的转换，使得算法的搜索性能更优，算法借由一个概率因子p来平衡两种搜索过程的比重[7]。

以花粉异花授粉行为对应全局搜索过程，假设算法的种群规模为N，搜索空间维度为d，花粉个体i当前处于t时刻，则可用下列公式表示其位置的更新过程：

其中，为标准伽马函数，λ的值为1.5。

以花粉自花授粉行为对应局部搜索过程，花粉个体i当前处于t时刻，则可用下列公式表示其位置的更新过程：

2.2 改进花朵授粉算法

在基本花朵授粉算法中，转换概率p为常数，即执行全局搜索和局部搜索的概率是不变的。但是在算法运行中若p值过大，则执行全局搜索的次数较多，容易得到全局最优解，但不易于收敛；若p值过小，则执行局部搜索的次数较多，易陷入局部最优解[8]。因此，改进花朵授粉算法中对p做出一定调整：

其中，rand1是[0，1]之间的随机数。改进后的算法中，每迭代一次，p值更新一次，自适应地调节全局搜索和局部搜索的执行概率，不仅能够避免FPA算法陷入局部最优，同时提高算法的收敛速度。

当花粉在解的搜索空间移动时，在开始迭代初始，解离最优解的距离较大，此时应该使移动步长较大，随着解在移动过程中渐渐靠近最优解，步长应当逐渐减小，因此可通过如下方式来定义步长因子：

其中，N表示最大迭代次数，t表示当前迭代次数。此时的全局搜索公式：

在标准FPA的局部授粉过程中，利用[0，1]之间产生的随机数ε来控制第i个花粉的变异概率。若ε过小，可以遍历搜索空间的所有位置，但需要太多的运行时间；若ε过大，可以节约运行时间，但不利于找到最优解，因此随机的变异概率会导致算法的收敛速度较慢，或者收敛到较差的解。鉴于此，在改进花朵授粉算法中，对变异因子ε修改为：

其中，rand2，rand3是[0，1]之间的随机数，εt是第t次迭代时的变异因子，εt+1是第t+1次迭代时的变异因子[7]。通过测量计算发现，初始值ε0为（0.25，0.75）之间的随机数，τ和εu分别去0.1和0.9时，计算结果最好[9]。

2.3 改进花朵授粉算法流程图

图1 改进花朵授粉算法流程图

3 案例验证

3.1 案例参数

以某长方形的自动化生产车间为例对改进花朵授粉算法进行验证。在自动化生产车间内每隔3m的距离布置一个RFID读写器，以确保RFID信号的全覆盖。在实现RFID信号的生产车间全覆盖中，选用北京华荣汇通讯设备有限公司生产的有源HR-6020C读写器和WSHT06电子标签。

在RFID信号网络覆盖整个生产车间的基础上，在AGV上粘贴电子标签，当AGV在车间行走时，在其周围总有一定数量的RFID读写器在读取RFID信号，我们选择离AGV最近的4个RFID读写器建立数学模型，以这4个RFID读写器的坐标和其读取的信号强度来定位AGV的位置。

设定待定位的AGV上的RFID标签的坐标为（1.4664，1.36）。4个RFID读写器的坐标为：A1（0，0）、A2（0，3）、A3（3，0）、A4（3，3）。

3.2 AGV的定位

RFID信号在传播过程中一定会有衰减，当读写器与待定点位置距离较近时，信号的强度会比较强。根据实验分析，建立在室内环境下RFID信号衰减与距离的传播模型[10]：

公式中d为读写器到电子标签之间的距离，n为环境影响因子，Xσ是指标准差为σ的零均值正态分布的随机变量，Pd0是相距为d0处RFID信号节点接收到无线信号强度的值。根据文献[11]可知，在室内环境下，通过做实验测得当d0=1时，n=2.1082，Pd0=-64.25。

根据传播模型式(8)所示，可以计算出RFID信号强度对应的距离；在实验环境下，可以实际测量RFID信号强度对应的距离。统计分析得出无线信号功率与距离的关系如表1所示。

表1 实际距离与计算距离的关系

在实验环境中测量的数据是离散的，对表中的数据分析可知，实际距离和计算距离近似为二次函数，选择实际距离为1.6、2.2、2.8时的三组数据进行插值，可以得到一个连续的二次插值多项式：

根据式(12)、式(13)所示，我们初步估计待定位的电子标签到4个RFID读写器的距离C1、C2、C3、C4为2.0901、2.1710、2.3313、2.3762。在改进花朵授粉算法中，设当前坐标Q到4个RFID读写器之间的距离Ei。

由表1可知，实际距离和计算距离有误差，当我们在实验环境得到计算距离后，可以先估算误差大小，选择计算距离的三组数据进行插值，可以近似得到一个关于误差的连续的二次插值多项式：

根据式(15)估计计算距离C1、C2、C3、C4的误差为0.0901、0.1018、0.1313和0.1412。通过下面的函数可以表示这样的关系衡量什么是“离待定位电子标签最近”，式中根据误差的大小加以比重因子。

fit越小表示离待定位的AGV越接近。

3.2 用改进花朵授粉算法求解

1）参数设定

分别设定花粉配子种群规模n=20、基本花朵授粉最大迭代次数4000、改进花朵授粉最大迭代次数1500。计算随机产生的花粉配子对应的目标函数值，得到当前最优值g*及其对应的状态fit。然后开始迭代计算。

2）计算分析

为了得到尽可能精确的最优解，迭代次数选的很大，在程序运行时发现，在迭代达到一定次数时，计算结果不再发生变化，基本花朵授粉算法得到的最优解为（1.4544,1.3434），改进花朵授粉算法得到的最优解为（1.4544,1.3434）。

为分析改进花朵授粉算法的有效性，分别采用改进花朵授粉算法、基本花朵授粉算法、三边测量法和多边质心法进行验证分析。本定位模型是由三边测量法的思想改进而来，三边测量法得到的待定位坐标为（1.4524,1.3324）。多边质心法是以初步估计的计算距离为半径，对应的读写器坐标为圆心，以两两个相交的圆的交点组成的多边形的质心为待定位的坐标。经过计算可知，四个交点坐标为M1（1.6187,1.3223）、M2（1.4425,1.5112）、M3（1.4648,1.1863）、M4（1.2954,1.3445）。所以得到的待定位坐标为（1.4553,1.3411）[10]。Y由已设定的参数可知，实际坐标为（1.4664,1.3600），AGV不同的定位方法对比结果如表2所示。

表2 不同算法结果对比

改进花朵授粉算法和基本花朵授粉算法迭代过程对比如表3和图2所示。

表3 迭代次数和迭代时间的对比

图2 算法距离误差对比图

由表2可知，三种方法得到的横纵坐标的精度都达到了厘米级别，满足AGV的使用要求，而本文设计改进花朵授粉算法和基本花朵授粉算法精度更高。由表3和图2可知，改进花朵授粉算法收敛速度更快，所需的迭代次数更少。（由于算法中有取随机数的步骤，迭代初期距离误差不唯一，迭代后期结果唯一，此为其中一次较稳定的数据）。因此，本文提出的改进花朵授粉算法是有效的，能应用于AGV的定位问题中。

4 结语

通过对AGV现有的定位方式的分析，结合RFID技术，为用于生产车间的AGV提出了一种新型定位方法。本文首先分析了现有的AGV定位方式，阐述了现有定位算法的不足；然后结合RFID技术，提供了一种用于生产车间的AGV定位模型，并采用改进花朵授粉算法对模型进行优化解算。最后通过案例对改进花朵授粉算法和基本花朵授粉进行了分析和比较，验证了算法设计的可行性和有效性。需要注意的是，采用RFID技术进行AGV定位时，需要根据AGV精度定位要求选择合理的RFID读写器和电子标签。这是下一步的研究方向。