一種基于RFID場(chǎng)景布局的AGV改進(jìn)花朵授粉定位算法

韓共樂(lè)，張接信，張富強(qiáng)

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

（長(zhǎng)安大學(xué) 道路施工技術(shù)與裝備教育部重點(diǎn)實(shí)驗(yàn)室，西安 710064）

0 引言

AGV（Automated Guided Vehicle）是指應(yīng)用于工業(yè)生產(chǎn)中具備自動(dòng)導(dǎo)引功能的搬運(yùn)車。無(wú)需軌道鋪設(shè)，不受場(chǎng)地、道路和空間限制等優(yōu)勢(shì)，高效、準(zhǔn)確、經(jīng)濟(jì)、靈活的自動(dòng)運(yùn)料功能可顯著提高制造系統(tǒng)的生產(chǎn)柔性和市場(chǎng)競(jìng)爭(zhēng)力[1,2]。當(dāng)前，新一代IT技術(shù)（物聯(lián)網(wǎng)、大數(shù)據(jù)、云計(jì)算）與智能物流裝備技術(shù)蓬勃發(fā)展，正逐步改變我國(guó)物流行業(yè)管理效率低下、信息化程度較低的現(xiàn)狀，降低物流成本的同時(shí)推動(dòng)著我國(guó)物流智能化的變革。

AGV定位問(wèn)題是學(xué)術(shù)界研究的熱點(diǎn)，也是工業(yè)領(lǐng)域推廣應(yīng)用的難點(diǎn)。目前主流的3種AGV導(dǎo)引方式分別是磁導(dǎo)引、激光導(dǎo)引和視覺(jué)導(dǎo)引。其中磁導(dǎo)引方式的成本最低也較容易實(shí)現(xiàn)，其定位方式也較簡(jiǎn)單，但精確低；采用激光導(dǎo)引AGV的定位精度高，但其成本較高，且設(shè)備安裝難度大；采用視覺(jué)導(dǎo)引AGV具有導(dǎo)引精度高、性價(jià)比好等特點(diǎn)，但是其技術(shù)還不太成熟[3]。RFID（Radio Frequency Identification）技術(shù)的成熟應(yīng)用，為我們研究AGV定位問(wèn)題提供了新的思路。將RFID技術(shù)應(yīng)用于AGV定位中，不僅可以提高AGV定位精度，還可以降低AGV的定位成本[4]。

另一方面，一些新型智能優(yōu)化算法在求解AGV位置過(guò)程中存在不足之處。例如，粒子群算法和差分進(jìn)化算法應(yīng)用于AGV定位時(shí)精度差，易陷于局部最優(yōu)，BP神經(jīng)網(wǎng)絡(luò)算法和遺傳算法運(yùn)算速度慢，時(shí)效性弱，螢火蟲(chóng)算法定位精度低而且定位速度慢[5]?；ǘ涫诜鬯惴ǎ‵lower pollination algorithm，簡(jiǎn)稱FPA）是根據(jù)自然界中植物花朵授粉行為機(jī)理進(jìn)行模擬而設(shè)計(jì)的一種新型啟發(fā)式優(yōu)化算法，其局部搜索和全局搜索過(guò)程分別模擬自花授粉和異花授粉行為，利用轉(zhuǎn)換概率動(dòng)態(tài)地控制全局搜索和局部搜索之間的轉(zhuǎn)換，較好地解決了全局搜索和局部搜索之間的平衡問(wèn)題[6]。FPA具有參數(shù)少、易調(diào)節(jié)、搜索能力強(qiáng)、魯棒性強(qiáng)、實(shí)現(xiàn)簡(jiǎn)單等優(yōu)點(diǎn)，在定位計(jì)算上可以取得很高的精度。

因此，本文首先根據(jù)RFID信號(hào)的強(qiáng)弱估算出AGV和固定讀寫(xiě)器之間的距離；然后根據(jù)讀寫(xiě)器的位置信息，以及估算出的AGV和讀寫(xiě)器之間的距離，建立花朵授粉算法模型；最后采用花朵授粉算法精確定位AGV。

1 RFID定位模型

在自動(dòng)化生產(chǎn)車間內(nèi)，每隔n米的距離布置一個(gè)RFID讀寫(xiě)器，以確保RFID信號(hào)的全覆蓋。在RFID信號(hào)網(wǎng)絡(luò)覆蓋整個(gè)生產(chǎn)車間的基礎(chǔ)上，在AGV上粘貼電子標(biāo)簽，當(dāng)AGV在車間行走時(shí)，選擇離AGV最近的m個(gè)RFID讀寫(xiě)器（讀寫(xiě)器坐標(biāo)為（xi，yi））來(lái)實(shí)現(xiàn)AGV定位。

RFID信號(hào)在傳播過(guò)程中一定會(huì)有衰減，可以根據(jù)RFID信號(hào)強(qiáng)弱初步估計(jì)待定位的AGV到讀寫(xiě)器的距離。設(shè)定初步估計(jì)的RFID讀寫(xiě)器到待定位的AGV的距離為Ci，設(shè)當(dāng)前坐標(biāo)Q（x0，y0）到m個(gè)RFID讀寫(xiě)器之間的距離Ei。

本文以距離為Ci與距離Ei之差的平方和的最小值為優(yōu)化目標(biāo)，相應(yīng)的數(shù)學(xué)模型如下：

優(yōu)化目標(biāo)：

其他條件：

式(1)為優(yōu)化目標(biāo)函數(shù)；式(2)為室內(nèi)環(huán)境下RFID信號(hào)衰減與距離的傳播模型；式(3)為當(dāng)前坐標(biāo)Q（x0，y0）到m個(gè)RFID讀寫(xiě)器之間的距離公式；式(4)表示下標(biāo)變量的取值范圍。

2 花朵授粉算法求解

2.1 基本花朵授粉算法

花朵授粉算法是一種新型的優(yōu)化算法?；谠趥鞣圻^(guò)程中花朵的異花授粉行為與自花授粉行為將花朵授粉算法的搜索過(guò)程分為全局搜索過(guò)程與局部搜索過(guò)程，為了協(xié)調(diào)兩種搜索過(guò)程間的轉(zhuǎn)換，使得算法的搜索性能更優(yōu)，算法借由一個(gè)概率因子p來(lái)平衡兩種搜索過(guò)程的比重[7]。

以花粉異花授粉行為對(duì)應(yīng)全局搜索過(guò)程，假設(shè)算法的種群規(guī)模為N，搜索空間維度為d，花粉個(gè)體i當(dāng)前處于t時(shí)刻，則可用下列公式表示其位置的更新過(guò)程：

其中，為標(biāo)準(zhǔn)伽馬函數(shù)，λ的值為1.5。

以花粉自花授粉行為對(duì)應(yīng)局部搜索過(guò)程，花粉個(gè)體i當(dāng)前處于t時(shí)刻，則可用下列公式表示其位置的更新過(guò)程：

2.2 改進(jìn)花朵授粉算法

在基本花朵授粉算法中，轉(zhuǎn)換概率p為常數(shù)，即執(zhí)行全局搜索和局部搜索的概率是不變的。但是在算法運(yùn)行中若p值過(guò)大，則執(zhí)行全局搜索的次數(shù)較多，容易得到全局最優(yōu)解，但不易于收斂；若p值過(guò)小，則執(zhí)行局部搜索的次數(shù)較多，易陷入局部最優(yōu)解[8]。因此，改進(jìn)花朵授粉算法中對(duì)p做出一定調(diào)整：

其中，rand1是[0，1]之間的隨機(jī)數(shù)。改進(jìn)后的算法中，每迭代一次，p值更新一次，自適應(yīng)地調(diào)節(jié)全局搜索和局部搜索的執(zhí)行概率，不僅能夠避免FPA算法陷入局部最優(yōu)，同時(shí)提高算法的收斂速度。

當(dāng)花粉在解的搜索空間移動(dòng)時(shí)，在開(kāi)始迭代初始，解離最優(yōu)解的距離較大，此時(shí)應(yīng)該使移動(dòng)步長(zhǎng)較大，隨著解在移動(dòng)過(guò)程中漸漸靠近最優(yōu)解，步長(zhǎng)應(yīng)當(dāng)逐漸減小，因此可通過(guò)如下方式來(lái)定義步長(zhǎng)因子：

其中，N表示最大迭代次數(shù)，t表示當(dāng)前迭代次數(shù)。此時(shí)的全局搜索公式：

在標(biāo)準(zhǔn)FPA的局部授粉過(guò)程中，利用[0，1]之間產(chǎn)生的隨機(jī)數(shù)ε來(lái)控制第i個(gè)花粉的變異概率。若ε過(guò)小，可以遍歷搜索空間的所有位置，但需要太多的運(yùn)行時(shí)間；若ε過(guò)大，可以節(jié)約運(yùn)行時(shí)間，但不利于找到最優(yōu)解，因此隨機(jī)的變異概率會(huì)導(dǎo)致算法的收斂速度較慢，或者收斂到較差的解。鑒于此，在改進(jìn)花朵授粉算法中，對(duì)變異因子ε修改為：

其中，rand2，rand3是[0，1]之間的隨機(jī)數(shù)，εt是第t次迭代時(shí)的變異因子，εt+1是第t+1次迭代時(shí)的變異因子[7]。通過(guò)測(cè)量計(jì)算發(fā)現(xiàn)，初始值ε0為（0.25，0.75）之間的隨機(jī)數(shù)，τ和εu分別去0.1和0.9時(shí)，計(jì)算結(jié)果最好[9]。

2.3 改進(jìn)花朵授粉算法流程圖

圖1 改進(jìn)花朵授粉算法流程圖

3 案例驗(yàn)證

3.1 案例參數(shù)

以某長(zhǎng)方形的自動(dòng)化生產(chǎn)車間為例對(duì)改進(jìn)花朵授粉算法進(jìn)行驗(yàn)證。在自動(dòng)化生產(chǎn)車間內(nèi)每隔3m的距離布置一個(gè)RFID讀寫(xiě)器，以確保RFID信號(hào)的全覆蓋。在實(shí)現(xiàn)RFID信號(hào)的生產(chǎn)車間全覆蓋中，選用北京華榮匯通訊設(shè)備有限公司生產(chǎn)的有源HR-6020C讀寫(xiě)器和WSHT06電子標(biāo)簽。

在RFID信號(hào)網(wǎng)絡(luò)覆蓋整個(gè)生產(chǎn)車間的基礎(chǔ)上，在AGV上粘貼電子標(biāo)簽，當(dāng)AGV在車間行走時(shí)，在其周圍總有一定數(shù)量的RFID讀寫(xiě)器在讀取RFID信號(hào)，我們選擇離AGV最近的4個(gè)RFID讀寫(xiě)器建立數(shù)學(xué)模型，以這4個(gè)RFID讀寫(xiě)器的坐標(biāo)和其讀取的信號(hào)強(qiáng)度來(lái)定位AGV的位置。

設(shè)定待定位的AGV上的RFID標(biāo)簽的坐標(biāo)為（1.4664，1.36）。4個(gè)RFID讀寫(xiě)器的坐標(biāo)為：A1（0，0）、A2（0，3）、A3（3，0）、A4（3，3）。

3.2 AGV的定位

RFID信號(hào)在傳播過(guò)程中一定會(huì)有衰減，當(dāng)讀寫(xiě)器與待定點(diǎn)位置距離較近時(shí)，信號(hào)的強(qiáng)度會(huì)比較強(qiáng)。根據(jù)實(shí)驗(yàn)分析，建立在室內(nèi)環(huán)境下RFID信號(hào)衰減與距離的傳播模型[10]：

公式中d為讀寫(xiě)器到電子標(biāo)簽之間的距離，n為環(huán)境影響因子，Xσ是指標(biāo)準(zhǔn)差為σ的零均值正態(tài)分布的隨機(jī)變量，Pd0是相距為d0處RFID信號(hào)節(jié)點(diǎn)接收到無(wú)線信號(hào)強(qiáng)度的值。根據(jù)文獻(xiàn)[11]可知，在室內(nèi)環(huán)境下，通過(guò)做實(shí)驗(yàn)測(cè)得當(dāng)d0=1時(shí)，n=2.1082，Pd0=-64.25。

根據(jù)傳播模型式(8)所示，可以計(jì)算出RFID信號(hào)強(qiáng)度對(duì)應(yīng)的距離；在實(shí)驗(yàn)環(huán)境下，可以實(shí)際測(cè)量RFID信號(hào)強(qiáng)度對(duì)應(yīng)的距離。統(tǒng)計(jì)分析得出無(wú)線信號(hào)功率與距離的關(guān)系如表1所示。

表1 實(shí)際距離與計(jì)算距離的關(guān)系

在實(shí)驗(yàn)環(huán)境中測(cè)量的數(shù)據(jù)是離散的，對(duì)表中的數(shù)據(jù)分析可知，實(shí)際距離和計(jì)算距離近似為二次函數(shù)，選擇實(shí)際距離為1.6、2.2、2.8時(shí)的三組數(shù)據(jù)進(jìn)行插值，可以得到一個(gè)連續(xù)的二次插值多項(xiàng)式：

根據(jù)式(12)、式(13)所示，我們初步估計(jì)待定位的電子標(biāo)簽到4個(gè)RFID讀寫(xiě)器的距離C1、C2、C3、C4為2.0901、2.1710、2.3313、2.3762。在改進(jìn)花朵授粉算法中，設(shè)當(dāng)前坐標(biāo)Q到4個(gè)RFID讀寫(xiě)器之間的距離Ei。

由表1可知，實(shí)際距離和計(jì)算距離有誤差，當(dāng)我們?cè)趯?shí)驗(yàn)環(huán)境得到計(jì)算距離后，可以先估算誤差大小，選擇計(jì)算距離的三組數(shù)據(jù)進(jìn)行插值，可以近似得到一個(gè)關(guān)于誤差的連續(xù)的二次插值多項(xiàng)式：

根據(jù)式(15)估計(jì)計(jì)算距離C1、C2、C3、C4的誤差為0.0901、0.1018、0.1313和0.1412。通過(guò)下面的函數(shù)可以表示這樣的關(guān)系衡量什么是“離待定位電子標(biāo)簽最近”，式中根據(jù)誤差的大小加以比重因子。

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

3.2 用改進(jìn)花朵授粉算法求解

1）參數(shù)設(shè)定

分別設(shè)定花粉配子種群規(guī)模n=20、基本花朵授粉最大迭代次數(shù)4000、改進(jìn)花朵授粉最大迭代次數(shù)1500。計(jì)算隨機(jī)產(chǎn)生的花粉配子對(duì)應(yīng)的目標(biāo)函數(shù)值，得到當(dāng)前最優(yōu)值g*及其對(duì)應(yīng)的狀態(tài)fit。然后開(kāi)始迭代計(jì)算。

2）計(jì)算分析

為了得到盡可能精確的最優(yōu)解，迭代次數(shù)選的很大，在程序運(yùn)行時(shí)發(fā)現(xiàn)，在迭代達(dá)到一定次數(shù)時(shí)，計(jì)算結(jié)果不再發(fā)生變化，基本花朵授粉算法得到的最優(yōu)解為（1.4544,1.3434），改進(jìn)花朵授粉算法得到的最優(yōu)解為（1.4544,1.3434）。

為分析改進(jìn)花朵授粉算法的有效性，分別采用改進(jìn)花朵授粉算法、基本花朵授粉算法、三邊測(cè)量法和多邊質(zhì)心法進(jìn)行驗(yàn)證分析。本定位模型是由三邊測(cè)量法的思想改進(jìn)而來(lái)，三邊測(cè)量法得到的待定位坐標(biāo)為（1.4524,1.3324）。多邊質(zhì)心法是以初步估計(jì)的計(jì)算距離為半徑，對(duì)應(yīng)的讀寫(xiě)器坐標(biāo)為圓心，以兩兩個(gè)相交的圓的交點(diǎn)組成的多邊形的質(zhì)心為待定位的坐標(biāo)。經(jīng)過(guò)計(jì)算可知，四個(gè)交點(diǎn)坐標(biāo)為M1（1.6187,1.3223）、M2（1.4425,1.5112）、M3（1.4648,1.1863）、M4（1.2954,1.3445）。所以得到的待定位坐標(biāo)為（1.4553,1.3411）[10]。Y由已設(shè)定的參數(shù)可知，實(shí)際坐標(biāo)為（1.4664,1.3600），AGV不同的定位方法對(duì)比結(jié)果如表2所示。

表2 不同算法結(jié)果對(duì)比

改進(jìn)花朵授粉算法和基本花朵授粉算法迭代過(guò)程對(duì)比如表3和圖2所示。

表3 迭代次數(shù)和迭代時(shí)間的對(duì)比

圖2 算法距離誤差對(duì)比圖

由表2可知，三種方法得到的橫縱坐標(biāo)的精度都達(dá)到了厘米級(jí)別，滿足AGV的使用要求，而本文設(shè)計(jì)改進(jìn)花朵授粉算法和基本花朵授粉算法精度更高。由表3和圖2可知，改進(jìn)花朵授粉算法收斂速度更快，所需的迭代次數(shù)更少。（由于算法中有取隨機(jī)數(shù)的步驟，迭代初期距離誤差不唯一，迭代后期結(jié)果唯一，此為其中一次較穩(wěn)定的數(shù)據(jù)）。因此，本文提出的改進(jìn)花朵授粉算法是有效的，能應(yīng)用于AGV的定位問(wèn)題中。

4 結(jié)語(yǔ)

通過(guò)對(duì)AGV現(xiàn)有的定位方式的分析，結(jié)合RFID技術(shù)，為用于生產(chǎn)車間的AGV提出了一種新型定位方法。本文首先分析了現(xiàn)有的AGV定位方式，闡述了現(xiàn)有定位算法的不足；然后結(jié)合RFID技術(shù)，提供了一種用于生產(chǎn)車間的AGV定位模型，并采用改進(jìn)花朵授粉算法對(duì)模型進(jìn)行優(yōu)化解算。最后通過(guò)案例對(duì)改進(jìn)花朵授粉算法和基本花朵授粉進(jìn)行了分析和比較，驗(yàn)證了算法設(shè)計(jì)的可行性和有效性。需要注意的是，采用RFID技術(shù)進(jìn)行AGV定位時(shí)，需要根據(jù)AGV精度定位要求選擇合理的RFID讀寫(xiě)器和電子標(biāo)簽。這是下一步的研究方向。