基于鯨優化算法的自導航機器人路徑規劃研究

朱誠

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

關鍵詞：群智能算法;鯨優化算法;自導航機器人;路徑規劃

中圖分類號：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）

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

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

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

2 ? AGV運行環境建模（Modeling of AGV running environment）

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

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

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

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

（3）滿載AGV優先級高于空載AGV。

（4）對相同負載狀態AGV，編號越小，優先級較高。

（5）更改路徑規劃的優先級高于停車等待。

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

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

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

3 ? 改進的鯨優化算法（Improved WOA）

3.1 ? 原始鯨優化算法

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

（1）搜索獵物

3.2 ? 改進的鯨優化算法

（1）雙非線性收斂因子

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

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

（2）強制驅散

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

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

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

3.3 ? 適應度函數

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

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

公式（16）說明在轉彎的柵格，障礙權重會乘以系數1.2，從而從數據上增加了AGV的移動距離。

3.4 ? 算法步驟

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

（2）計算每個柵格的障礙權重w。

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

（4）確定鯨群規模和迭代次數。

（5）AGV是否處于路口，若是，根據優先級設定，判斷是否需要重新設定起點S并進行新的路徑規劃。

（6）根據公式（15）的目標函數計算適應度。

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

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

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

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

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

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

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

5 ? 結論（Conclusion）

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

參考文獻（References）

[1] 陳明智，錢同惠，張仕臻，等.倉儲物流機器人集群避障及協同路徑規劃方法[J].現代電子技術，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] 宮孟孟.基于神經網絡的移動機器人路徑規劃方法研究[D].哈爾濱：哈爾濱工業大學，2017.

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

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

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

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

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

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

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

作者簡介：

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