一種基于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讀寫器和電子標簽。這是下一步的研究方向。