自動導引車路徑規(guī)劃問題建模與研究

摘要： 為提高自動導引車（AGV）的路徑規(guī)劃效率，以蟻群算法和迪杰斯特拉（Dijkstra）算法為研究基礎，以路徑長度為優(yōu)化目標，對單AGV進行路徑規(guī)劃。首先通過MAKLINK圖論將實際環(huán)境簡化為MAKLINK環(huán)境，然后通過Dijkstra算法求得起止點的最短路徑，最后通過蟻群算法優(yōu)化該路徑結果，得到最終選定的路徑，提高了AGV的運輸效率，降低了能量消耗。

關鍵詞：蟻群算法 Dijkstra算法 自動導引車 路徑規(guī)劃 MAKLINK圖論

中圖分類號：TP242；U468.2+2" "文獻標志碼：B" "DOI： 10.19710/J.cnki.1003-8817.20240194

Modeling and Research on Path Planning of Automated Guided Vehicles

Gong Xiangyang， Wan Chaoyi， Zhong Jiadong， Cheng Yu

（School of Automotive and Traffic Engineering， Jiangsu University of Technology， Changzhou 213001）

Abstract： In order to improve the path planning efficiency of Automated Guided Vehicles （AGVs）， the research is based on the Ant Colony Algorithm and Dijkstra’s Algorithm， taking the path length as the optimization objective， to conduct path planning for a single AGV. Firstly， the actual environment is simplified to MAKLINK environment by MAKLINK graph theory. Then， the shortest path of the starting point is obtained by Dijkstra algorithm. Finally， the path is optimized by ant colony algorithm to obtain the final selected path， which improves the transportation efficiency of AGV and reduces the energy consumption.

Key words： Ant colony algorithm， Dijkstra algorithm， AGV， Path planning， MAKLINK graph theory

1 前言

隨著數(shù)字化智能工廠等概念逐漸為大眾所熟知，自動導引車（Automated Guided Vehicle，AGV）在工廠的降本增效方面發(fā)揮了重要作用[1-2]。其中，AGV的路徑規(guī)劃問題已有相當廣泛的研究。為使AGV發(fā)揮更大的作用，除合理的AGV集散中心選址外，還需要規(guī)劃每個AGV的路徑，個體具備較好的功能和精確的執(zhí)行能力可降低AGV工作系統(tǒng)的故障率，提升工作效率。

2 AGV路徑規(guī)劃方法

根據(jù)AGV的數(shù)量，AGV的路徑規(guī)劃分為單AGV路徑規(guī)劃和多AGV路徑規(guī)劃[3]，按照問題解決模式，可分為靜態(tài)路徑規(guī)劃和動態(tài)路徑規(guī)劃[4]。單AGV路徑規(guī)劃方法較多，但應用范圍較為有限，不能很好貼合實際生產(chǎn)，多AGV路徑規(guī)劃模型較為復雜且故障率較高，但更貼合規(guī)模化的實際生產(chǎn)，在智能工廠無人生產(chǎn)車間的建設中處于核心地位。從解決模式角度來看，AGV靜態(tài)路徑規(guī)劃方法模型相對簡單，成本相對較低，可靠性更高，但對生產(chǎn)效率的提升較動態(tài)路徑規(guī)劃較為有限，動態(tài)路徑規(guī)劃模型較為復雜，對AGV個體的要求也更高，需要單體AGV提供更多的環(huán)境信息，但實用性更高，AGV個體成本更高。因此，AGV路徑規(guī)劃的算法研究十分重要。

迪杰斯特拉（Dijkstra）算法是Edsger Wybe Dijkstra[5]于1956年提出的一種用來尋找圖形中結點之間最短路徑的算法。Dijkstra算法采用一種貪心模式，能夠解決有向圖中任意節(jié)點到需要的另外一個節(jié)點最短路徑求解問題，A*算法能夠解決靜態(tài)路網(wǎng)中起點到終點的最短路徑問題，適用于全局路徑規(guī)劃。與Dijkstra算法相比，A*算法具有更好的方向性，由于將啟發(fā)式評價函數(shù)運用在搜索過程中，運算量大幅降低，搜索效率更高，但是A*算法并未評定全部路線，可能陷入局部最優(yōu)。遺傳算法以選擇、交叉、變異來重組群體，實現(xiàn)進化尋優(yōu)，通過染色體適應度可評價個體的優(yōu)劣，遺傳算法對求解問題無限制，不需要設定條件引導搜索方向，有十分高的泛用性。

MAKLINK圖論法由MKHabib等[6]于1991年研究AGV路徑規(guī)劃問題時提出，又被稱為自由空間法。其原理是根據(jù)AGV的大小，確定安全距離，在能夠安全通過路徑的情況下，對障礙物進行膨脹操作，將其轉(zhuǎn)化為規(guī)則幾何圖形，便于構建全局狀態(tài)連通圖。構造一個全局狀態(tài)連通圖，首先要將障礙空間與自由空間分開，然后連接障礙空間頂點，將頂點到環(huán)境邊界的垂線段的中點連接，得到全局狀態(tài)連通圖，其中，用來構造全局狀態(tài)連通圖的線段稱為MAKLINK線。

標注上述MAKLINK線的中點，依次標注為v1，v2，…，vn，然后用一條自由鏈接線連接上述各點，得到該MAKLINK圖形下的自由連接線。初始路徑規(guī)劃的無向網(wǎng)絡圖還需連接起點S與中點T，連接好的圖形如圖1所示。

MAKLINK線全部處于自由空間內(nèi)，路徑規(guī)劃的結果可首先表示為經(jīng)過的MAKLINK線，這樣一個序號集合即為路徑規(guī)劃結果。MATLAB中存儲的數(shù)據(jù)集即障礙空間與環(huán)境空間點坐標和各MAKLINK線中點的坐標。

3 蟻群算法解決路徑規(guī)劃基本原理

蟻群算法是Marco Dorigo[7]于1992年提出的一種用于尋找優(yōu)化路徑的隨機搜索算法，來源于對螞蟻尋找食物的問題研究。

螞蟻在尋找食物時，會在經(jīng)過的路徑上釋放一種生物信息素，該信息素能夠保留一段時間，使其他螞蟻能夠在距離信息素一定范圍內(nèi)覺察其存在。因此，信息素的濃度能體現(xiàn)出經(jīng)過該路段的螞蟻數(shù)量，間接反映路徑的長度，提高了后續(xù)螞蟻選擇此條路徑的概率。該路徑的信息素會不斷增強，向經(jīng)過的螞蟻提供正反饋，螞蟻選擇該路徑的概率不斷增大，從而獲得從巢穴前往該食物所在地的最優(yōu)路徑。

將螞蟻覓食過程應用于路徑規(guī)劃問題的解決思路為：將路徑優(yōu)化問題擬化為螞蟻覓食時的行走路徑選擇問題，即路徑選擇結果是路徑規(guī)劃問題的可行解，蟻群走過的所有路徑是待優(yōu)化問題的可行解空間。

圖2為螞蟻覓食過程，體現(xiàn)了螞蟻從巢穴出發(fā)，選擇路徑，留下信息素，到達食物所在地，蟻群確定最優(yōu)路徑的過程。如圖2a所示，螞蟻由A點到達D點僅有路徑BEC與路徑BFC，其中，路徑BEC和路徑BFC的路徑權值分別為2個長度單位和1個長度單位。起初，由于路徑的長度未知，也沒有信息素作為參考，初次選擇路徑BEC和路徑BFC的概率相等，如圖2b所示。經(jīng)過一段時間后，相同時間內(nèi)，路徑BFC通過的螞蟻數(shù)量遠多于路徑BEC，路徑BFC上的信息素濃度越來越高，遠高于路徑BEC，螞蟻選擇路徑BFC前進的概率就越來越高，如圖2c所示。

4 路徑規(guī)劃模型仿真試驗

4.1 模型假設

完成AGV在車間中的集散中心選址后，以AGV從選址方案中某一集散地點出發(fā)，到達某一具體物料需求點這一過程為例，進行AGV路徑的規(guī)劃。設集散中心作為出發(fā)點，物料需求點為終點。將這一路徑規(guī)劃過程設定于200×200的二維空間中，將車間視作二維空間，劃分為自由空間與非自由空間?？紤]到AGV尺寸，將車間中的障礙物進行膨脹化處理，保證在進行路徑規(guī)劃時，AGV在自由空間中的移動，不會受到任何障礙物的影響。完成以上自由空間與非自由空間的劃分后，二維空間中的障礙物被簡化為4個多邊形非自由空間，坐標如表1所示。

將鏈路端點以及自由鏈接線繪制于MAKLINK圖上，按照表2端點坐標以及表3自由鏈接線端點坐標鏈接自由鏈接線，鏈接結果如圖4所示。

4.2 算法流程及算法實現(xiàn)

蟻群算法的工作流程如圖5所示，首先建立空間模型，在獲取車間設備以及AGV不能自由行駛的區(qū)域后，將這些區(qū)域膨脹化處理，障礙空間由非自由空間變?yōu)椴灰?guī)則多邊形。然后用Dijkstra算法進行初始路徑規(guī)劃，得到一條初始路徑，按照求解目標初始化參數(shù)，根據(jù)螞蟻搜索到的路徑長度實時更新信息素和路徑信息素。

4.2.1 解的表示

4.2.2 節(jié)點選擇

4.2.3 信息素更新

4.3 Dijkstra規(guī)劃初始路徑

Dijkstra算法規(guī)劃初始路徑是先計算自由鏈接線上節(jié)點與節(jié)點之間的距離，然后依次計算各個點到出發(fā)點的最短距離，包含了集散中心點S、物料需求點T的可行路徑，如圖6所示。

5 結果評價

根據(jù)以上可行路徑，采用Dijkstra算法計算可得初始路徑規(guī)劃，如圖7所示。

根據(jù)Dijkstra算法得出的初始路徑，確定螞蟻經(jīng)過的自由鏈接線依次為L8、L7、L6、L12、L13、L11，計算初始路徑規(guī)劃得到的鏈路長度約為231 m，結合蟻群算法對該初始路徑進行優(yōu)化，將該初始鏈接線的各鏈路均等分為10份，設置蟻群算法相關參數(shù)，如表5所示。

迭代過程中適應度變化過程以及由算法規(guī)劃出的路徑線路如圖8、圖9所示，其中，最優(yōu)路徑為圖8中藍色實線。

初始路徑規(guī)劃得到的路徑長度約為231 m，經(jīng)過蟻群算法對路徑進行優(yōu)化后，得到的路徑總長度約為177 m，總體路徑優(yōu)化率約為23.4%，達到了縮短路徑的目的，在AGV轉(zhuǎn)彎次數(shù)不變的情況下，AGV的行駛時間得到大幅縮短。

6 結束語

本文對AGV的路徑規(guī)劃問題進行了較為全面的分類與介紹，包含典型單源最短路徑Dijkstra算法、靜態(tài)網(wǎng)絡中極其有效的A*算法、經(jīng)典的遺傳算法。在對環(huán)境建模的方法基礎上，先采用Dijkstra算法在MAKLINK圖上進行初步規(guī)劃，然后在初始路徑基礎上，采用蟻群算法進一步優(yōu)化路徑，優(yōu)化效果顯著，縮短了單AGV在同樣目的下的行駛路徑，提高了單AGV的運輸效率，降低了能耗。

在車間AGV路徑規(guī)劃的模型建立以及求解中，通過Dijkstra算法確定最初路徑，再用蟻群算法對最初路徑進行優(yōu)化，得到的路徑更短，更符合目標函數(shù)要求，但是從適應度函數(shù)的圖表可看出，目標函數(shù)結果并非完全隨著迭代次數(shù)收斂，存在一定的波動性，后續(xù)可針對蟻群算法進行改進，使目標函數(shù)收斂更為穩(wěn)定準確。

參考文獻：

[1] ZHOU J， LI P G， ZHOU Y H， et al. Toward New-Generation Intelligent Manufacturing[J]. Engineering， 2018， 4（1）： 28-47.

[2] MAKRIS S， MICHALOS G， KARAGIANNIS P. Digitalising Smart Factories[J]. International Journal of Computer Integrated Manufacturing， 2023， 36（1）： 1-2.

[3] 梁建剛. AGV系統(tǒng)路徑規(guī)劃與調(diào)度算法研究[D]. 北京： 北京郵電大學， 2018.

[4] 宋士剛， 李愛平， 徐立云. 可重組制造系統(tǒng)中物流運輸路徑規(guī)劃[J]. 同濟大學學報（自然科學版）， 2010， 38（1）： 113-117.

[5] DIJKSTRA E W. A Note on Two Problems in Connexion with Graphs[J]. Numerische Mathematik， 1959， 1（1）： 269-271．

[6] HABIB M K， ASAMA H. Efficient Method to Generate Collision Free Paths for an Autonomous Mobie Robot Based on New Free Space Structuring Approuch[C]// IEEE/RSJ International Workshop on Intelligent Robots and Systems， 1991： 563-567.

[7] DORIGO M. Optimization， Learning and Natural Algorithms[J]. Thesis Politecnico Di Milano Italy， 1992.