基于鯨優(yōu)化算法的自導航機器人路徑規(guī)劃研究

朱誠

摘 ?要：自導航機器人（Automated Guided Vehicle，AGV）是現(xiàn)代產(chǎn)業(yè)不可或缺的重要組成部分。本文對AGV路徑規(guī)劃算法進行研究和設(shè)計。首先，采用柵格法對AGV運行環(huán)境建模，并制定約束規(guī)則以解決多AGV的沖突問題。其次，引入雙非線性收斂因子和強制驅(qū)散機制對經(jīng)典WOA進行改進。再次，定義適應(yīng)度函數(shù)，并將改進的WOA應(yīng)用于路徑規(guī)劃算法。仿真和實驗結(jié)果表明，基于改進WOA的規(guī)劃算法能夠有效簡化路徑復(fù)雜度、降低機器人控制難度。

關(guān)鍵詞：群智能算法;鯨優(yōu)化算法;自導航機器人;路徑規(guī)劃

中圖分類號：TP391 ? ? 文獻標識碼：A

Abstract： Automated Guided Vehicle （AGV） is an indispensable part of modern industry. This paper considers the AGV path planning algorithm. First， the grid method is used to model the AGV operating environment， and constraint rules are formulated to solve the conflict problem of multiple AGVs. Secondly， dual nonlinear convergence factors and forced dispersal mechanism are introduced to improve the classic Whale Optimization Algorithm （WOA）. Third， we define the fitness function and apply the improved WOA to the path planning algorithm. Simulation and experimental results show that the planning algorithm based on improved WOA can effectively simplify the path complexity and reduce the difficulty of robot control.

Keywords： swarm intelligence algorithm; whale optimization algorithm; automatic guided vehicle; path planning

1 ? 引言（Introduction）

隨著智能倉儲和自動生產(chǎn)線的不斷發(fā)展，自導航機器人（Automated Guided Vehicle，AGV）成為現(xiàn)代產(chǎn)業(yè)不可或缺的重要組成部分[1]。路徑規(guī)劃則成為AGV研究領(lǐng)域中最根本、最關(guān)鍵的內(nèi)容之一，機器人需要完成避障和自主路徑規(guī)劃等功能到達目標點[2]。其本質(zhì)上是依據(jù)代價最小、路線最短或時間最短等優(yōu)化準則，在工作空間中找一條從起點到終點的、避開障礙的最優(yōu)路徑[3]。

許多學者針對AGV的路徑規(guī)劃做出了大量的研究。丁承君等人提出基于粒子群優(yōu)化算法優(yōu)化AGV路徑規(guī)劃[4]。黨宏社等人采用遺傳算法進行AGV路徑規(guī)劃，并驗證了算法具有較好的收斂能力和全局搜索能力[5]。李悝提出一種改進的混沌粒子群優(yōu)化算法，采用基于Bezier曲線的路徑規(guī)劃模型，通過調(diào)整Bezier曲線的控制點數(shù)量，顯著改善AGV軌跡路線的長度和平滑度[6]。湯紅杰等人針對工廠內(nèi)物流運輸AGV的路徑規(guī)劃效率等問題，提出一種將Dijkstra算法存儲方式變更為鄰接表，實現(xiàn)了數(shù)據(jù)結(jié)構(gòu)上對鄰接結(jié)點搜索的優(yōu)化[7]。

元啟發(fā)式算法被廣泛應(yīng)用于模式識別、系統(tǒng)控制、信號處理等領(lǐng)域。鯨優(yōu)化算法（Whale Optimization Algorithm，WOA）是Seyedali Mirjalili于2016年提出的一種新型群智能優(yōu)化算法[8]。與其他群智能算法相比，WOA結(jié)構(gòu)簡單，易于理解，參數(shù)少，搜索能力強，全局收斂性好[9]。然而，標準WOA仍然存在收斂速度慢以及無法找到全局最優(yōu)解的問題。本文在規(guī)定多AGV沖突檢測規(guī)則和優(yōu)先級設(shè)定的基礎(chǔ)上，在路徑規(guī)劃中引入改進的鯨優(yōu)化算法，有效提高算法收斂速度，使算法能夠更迅速尋找全局最優(yōu)解，借助轉(zhuǎn)彎懲罰因子，有效降低路徑復(fù)雜性。

2 ? AGV運行環(huán)境建模（Modeling of AGV running environment）

為了便于對AGV所處位置進行描述和儲存，本文首先對空間環(huán)境進行柵格化處理，即將整個場景劃分為尺寸相同的柵格。柵格按照自左至右，自下至上的原則，橫坐標為，縱坐標為，場景中的全部柵格可以表示為，對不滿一個柵格的區(qū)域按照一個柵格處理。如圖1所示，有障礙物柵格用黑色表示，沒有障礙物為白色，代表可以自由通過的區(qū)域。

以上數(shù)學模型適用于靜態(tài)地圖中點對點循跡，但在多AGV的環(huán)境中，每一臺AGV只有同時避開靜態(tài)障礙物及運行中的其他AGV才能安全到達目標點。為了處理多AGV運行可能導致的路線規(guī)劃沖突問題，首先做如下假設(shè)：

（1）每個柵格在某一時點僅允許通過一臺AGV。

（2）機器人直線運動速度相同。

（3）滿載AGV優(yōu)先級高于空載AGV。

（4）對相同負載狀態(tài)AGV，編號越小，優(yōu)先級較高。

（5）更改路徑規(guī)劃的優(yōu)先級高于停車等待。

（6）當無法通過低優(yōu)先級AGV的狀態(tài)改變而避免沖突時，通過高優(yōu)先級AGV進行策略變化。

若當前AGV所處柵格在前進方向上的下一柵格的左側(cè)或者右側(cè)柵格的障礙權(quán)重w=1時，即當前AGV處于十字路口或丁字路口，則AGV通過網(wǎng)絡(luò)向控制中心請求沖突檢測，判斷運行至前方柵格是否會與其他AGV產(chǎn)生沖突。具體描述如圖2所示。

圖2描述了某臺AGV縱向和橫向移動的情況，左圖為縱向，右圖為橫向。紅色柵格為AGV所處的當前位置，紅點為部分移動軌跡。綠色柵格為移動方向上的下一個柵格。對比圖（1）可知，藍色柵格為可通行柵格。此時，需要判斷在藍色柵格上是否有其他AGV向綠色柵格移動。如果有，則需要按照優(yōu)先級規(guī)則進行判優(yōu)，以決定當前AGV是繼續(xù)前進、重新進行路徑規(guī)劃或停車等待。若重新規(guī)劃路徑，令當前柵格坐標Cur∈G作為新的路徑起點S。

3 ? 改進的鯨優(yōu)化算法（Improved WOA）

3.1 ? 原始鯨優(yōu)化算法

鯨優(yōu)化算法是受駝背鯨的獵食行為的啟發(fā)而產(chǎn)生的一種群智能優(yōu)化算法。本節(jié)簡單闡述算法的基本原理和數(shù)學模型。整個獵食過程分為三個階段：搜索獵物、包圍獵物、氣泡攻擊。

（1）搜索獵物

3.2 ? 改進的鯨優(yōu)化算法

（1）雙非線性收斂因子

原始經(jīng)典WOA利用公式（4）中的系數(shù)來確定全局探索和局部開發(fā)的時機，收斂因子在迭代過程中以固定的下降率從2下降到0。但是，固定的變化模式無法適應(yīng)搜索過程中的實際情況，使得搜索有可能陷入局部最優(yōu)。本文提出雙非線性收斂因子。它由和兩個收斂因子組成，具有不同的非線性特征曲線和變化規(guī)律，公式如下：

如圖3所示，經(jīng)過500次迭代，與WOA原始的適度性相比，和對不同的收斂趨勢更具有針對性。虛線為公式（10），實線為公式（11），從形狀來看，是著眼于全局搜索，重視局部開發(fā)。

（2）強制驅(qū)散

“驅(qū)散”是細菌覓食算法（Bacterial Foraging Optimization，BFO）中的概念，將其引入的目的是為了克服原始WOA算法在經(jīng)過多次迭代容易陷入局部最優(yōu)的缺點。通過擺脫的控制，強行將鯨魚定位到一個新的位置，從而嘗試脫離局部最優(yōu)。對于不同的收斂狀態(tài)采用不同的策略，當收斂狀態(tài)比較緩和時：

公式（12）中的系數(shù)6能夠有效擴大移動范圍，使鯨魚移動更遠的距離。當收斂狀態(tài)接近或已經(jīng)成水平線時，此時采取強制驅(qū)散機制，如公式（14）所示：

LB和UB分別為變量的下限和上限，為種群的初始化位置，為隨機調(diào)整因子。強制驅(qū)散機制將鯨魚重新定位到初始位置和邊界之間的位置，如圖4所示。

3.3 ? 適應(yīng)度函數(shù)

在AGV路徑規(guī)劃中，本文以路徑的距離作為判斷路徑優(yōu)劣的標準。從機械移動和控制的角度考慮，AGV在每次轉(zhuǎn)彎時必定要首先減速，這樣就增加了在途時間和姿態(tài)、方向的控制難度，因此引入轉(zhuǎn)彎懲罰因子。目標函數(shù)定義如下：

l為路徑包含的柵格數(shù)量，由公式（1）和可知，若路徑上的柵格包含了“障礙”，則適應(yīng)度函數(shù)值將以的整數(shù)次倍增加，必定被排除在外。這樣做的優(yōu)點是無須在路徑規(guī)劃前期判斷“障礙”。目標函數(shù)中雖然沒有包含與時間和速度相關(guān)的系數(shù)，但是轉(zhuǎn)彎懲罰因子的存在，相當于在轉(zhuǎn)彎處人為的延長了行進距離，按照S=v×t的基本規(guī)則，實際將時間因素包含其中，降低了目標函數(shù)的復(fù)雜性。保證一條路徑轉(zhuǎn)彎次數(shù)越少，則其目標函數(shù)值越小，適應(yīng)度函數(shù)值就越小。轉(zhuǎn)彎判斷規(guī)則如公式（16）所示：

公式（16）說明在轉(zhuǎn)彎的柵格，障礙權(quán)重會乘以系數(shù)1.2，從而從數(shù)據(jù)上增加了AGV的移動距離。

3.4 ? 算法步驟

（1）場景柵格化，初始化。

（2）計算每個柵格的障礙權(quán)重w。

（3）確定起點S和終點T的坐標。

（4）確定鯨群規(guī)模和迭代次數(shù)。

（5）AGV是否處于路口，若是，根據(jù)優(yōu)先級設(shè)定，判斷是否需要重新設(shè)定起點S并進行新的路徑規(guī)劃。

（6）根據(jù)公式（15）的目標函數(shù)計算適應(yīng)度。

（7）通過改進的WOA在迭代過程中確定最優(yōu)路徑。

4 ? WOA算法仿真（Simulation of WOA）

為了驗證優(yōu)化后的WOA算法性能，本文在MATLAB平臺進行仿真，實驗中設(shè)置種群規(guī)模為30，最大迭代次數(shù)為500次。測試結(jié)果如表1和圖5所示。

如表1和圖5所示，改進的WOA在收斂速度和收斂精度上全面優(yōu)于原始WOA。同時為了測試改進的WOA算法應(yīng)用在路徑規(guī)劃上的性能，起始點位置S=（2，1），目標點T=（18，20），AGV轉(zhuǎn)彎懲罰因子為1.2，仿真結(jié)果如圖6所示。

圖6中左圖為通過原始WOA規(guī)劃出的最優(yōu)路徑，右圖為本文改進的WOA規(guī)劃出的最優(yōu)路徑。二者雖然在總移動步數(shù)方面數(shù)量相同，均為移動36步。左圖轉(zhuǎn)彎4次，目標函數(shù)

f左=32+4×1.2=36.8，右圖轉(zhuǎn)彎3次，f右=32+4×1.2=36.6。右圖為了減少轉(zhuǎn)彎次數(shù)而采取改變初始行進方向的方式，雖然總的移動距離相近，但是在轉(zhuǎn)彎懲罰因子Tr的作用下，節(jié)省了時間。同時該算法能夠找到的最優(yōu)路徑更加合理，在實際現(xiàn)場更加便于AGV加速前進。尤其對于有負載的AGV，更加有利于姿態(tài)控制，并減少誤判和沖突檢測的難度。

如圖7所示，藍色AGV與紅色AGV的路徑規(guī)劃相同，但是方向相反。設(shè)定藍色優(yōu)先級高于紅色，所以當藍色和紅色出現(xiàn)沖突后，藍色AGV保持路徑不變，而紅色在沖突柵格處重新設(shè)定路徑起點并重新規(guī)劃了路線以避開。

5 ? 結(jié)論（Conclusion）

本文首先借助柵格化對自導行機器人的運行環(huán)境進行建模，并完成了路徑規(guī)劃目標函數(shù)的設(shè)計，通過制定諸項假設(shè)和約束條件提高了算法的穩(wěn)定性。對原始鯨優(yōu)化算法進行優(yōu)化和改進，提高了算法的收斂速度和收斂精度。仿真實驗表明優(yōu)化后的鯨優(yōu)化算法能夠有效簡化路徑復(fù)雜度，提高路徑在實際現(xiàn)場的實用性，改善AGV控制難度，同時沖突檢測機制能夠有效避免多AGV場景中的導航?jīng)_突，此算法應(yīng)用于多AGV路徑規(guī)劃具有可行性和有效性。

參考文獻（References）

[1] 陳明智，錢同惠，張仕臻，等.倉儲物流機器人集群避障及協(xié)同路徑規(guī)劃方法[J].現(xiàn)代電子技術(shù)，2019，42（22）：174-177;182.

[2] Bing Fu， Lin Chen， Yuntao Zhou， et al. An improved A* algorithm for the industrial robot path planning with high success rate and short length[J]. Robotics and Autonomous Systems， 2018，106：26-37.

[3] 宮孟孟.基于神經(jīng)網(wǎng)絡(luò)的移動機器人路徑規(guī)劃方法研究[D].哈爾濱：哈爾濱工業(yè)大學，2017.

[4] 丁承君，王鑫，馮玉伯，等.基于粒子群優(yōu)化算法的AGV路徑規(guī)劃[J].傳感器與微系統(tǒng)，2020（08）：123-126.

[5] 黨宏社，孫心妍.基于遺傳算法的工廠AGV路徑優(yōu)化研究[J].電子產(chǎn)品世界，2020（01）：48-51.

[6]李悝.基于混沌粒子群優(yōu)化算法的AGV路徑規(guī)劃研究[J].包裝工程，2018（23）：32-37.

[7] 湯紅杰，王鼎，皇攀凌，等.優(yōu)化Dijkstra算法在工廠內(nèi)物流AGV路徑規(guī)劃的研究[J].機械設(shè)計與制造，2018（S1）：117-120.

[8] Seyedali Mirjalili， Andrew Lewis. The whale optimization algorithm[J]. Advances in Engineering Software， 2016（01）：51-67.

[9] 何慶，魏康園，徐欽帥.基于混合策略改進的鯨魚優(yōu)化算法[J].計算機應(yīng)用研究，2019（12）：3647-3651;3665.

[10] 黃元春，張凌波.改進的鯨魚優(yōu)化算法及其應(yīng)用[J].計算機工程與應(yīng)用，2019，55（21）：220-226.

作者簡介：

朱 ? 誠（1981-），男，碩士，實驗師.研究領(lǐng)域：傳感器，嵌入式開發(fā).