基于禁忌搜索的多AGV系統(tǒng)路徑優(yōu)化算法

陳 展，公建寧，劉媛媛，徐京邦

機械科學研究總院 機科發(fā)展科技股份有限公司，北京100044

自動導引車（Automated Guided Vehicles，AGV）定義為配置導航定位功能的自動導引裝置，能夠沿系統(tǒng)規(guī)劃的路徑行駛，具有安全保護且能完成各種裝卸作業(yè)的自動設備[1]。在現(xiàn)代化輸送系統(tǒng)的自動化和智能化中起著不可或缺的重要作用，日益廣泛應用在制造業(yè)、航空航天、物流服務等行業(yè)。

多AGV 系統(tǒng)的路徑規(guī)劃技術包括作業(yè)任務的分派、最短路徑搜索和交通管理的相互配合，不僅需要保證作業(yè)的安全性，同時還要保持系統(tǒng)的高效運轉。其中AGV 的路徑搜索需要在復雜的現(xiàn)場環(huán)境下，依據(jù)工藝地圖路線，按照作業(yè)時間最短、系統(tǒng)運行成本最低和全局作業(yè)流暢的評價標準，規(guī)劃一條從起始點到目標點的行駛路徑[2]。

多AGV 系統(tǒng)的路徑搜索是一個涉及約束條件、附加條件和現(xiàn)實條件的復雜非確定性多項式（Nondeterministic Polynomial，NP）問題。相比于傳統(tǒng)經(jīng)典算法，智能優(yōu)化算法能夠更有效地解決路徑規(guī)劃的多約束問題，通過將尋找最優(yōu)路徑轉化為尋找函數(shù)最優(yōu)值，從而實現(xiàn)多AGV 系統(tǒng)路徑規(guī)劃中的最短路徑搜索[3]。本文在保證合理任務分配機制和穩(wěn)定交通管理策略的前提下，對比經(jīng)典尋路算法，提出基于鄰域搜索的禁忌路徑搜索算法，通過仿真實驗證明該方法的優(yōu)越性和必要性。

1 介紹

隨著AGV系統(tǒng)應用的日益廣泛和作業(yè)任務的日益復雜，AGV集群之間的相互配合與協(xié)作，成為系統(tǒng)項目中不可避免的重要問題，而多AGV 的路徑規(guī)劃技術就是AGV 系統(tǒng)的核心技術之一，可分為環(huán)境信息完全已知的全局路徑規(guī)劃和環(huán)境信息完全未知或部分未知的局部路徑規(guī)劃[4]。

在多AGV 系統(tǒng)的環(huán)境信息已知的全局路徑規(guī)劃中，任務調度算法、路徑搜索方法和交通管理的性能直接決定系統(tǒng)的整體效率。本文通過對路徑規(guī)劃技術中的路徑搜索算法在同等耦合條件任務分配和交通管理策略下進行設計優(yōu)化，完成基于特定的環(huán)境模型，搜索出一條能耗低、用時少，盡量避免阻塞障礙的AGV作業(yè)路徑。

全局路徑規(guī)劃下的路徑搜索算法發(fā)展歷程如圖1所示，從傳統(tǒng)的Dijkstra 和啟發(fā)式的A*等經(jīng)典算法，經(jīng)過基于采樣和圖論的隨機路標圖法（Probabilistic Road-Μaps，PRΜ）、快速搜索樹法（Rapid-exploration Random Tree，RRT）等，發(fā)展到日益成熟的智能仿生優(yōu)化算法和強化學習[5]。但實際應用過程中的任何路徑搜索算法都存在局限性，在具體的應用方向上，進行針對性的優(yōu)化改善，或是融合優(yōu)化多種算法，可以快速有效提升算法性能[6]。

圖1 路徑搜索算法發(fā)展歷程

在多AGV 系統(tǒng)下的路徑規(guī)劃中，當中央控制系統(tǒng)派發(fā)任務時，首先按照就近原則進行約束排序，來選擇匹配一輛移動機器人進行任務分配。這樣的規(guī)劃方法在一定程度上利用多移動機器人系統(tǒng)的優(yōu)勢，節(jié)約了AGV 電量和車體磨損等物流成本資源[7]。采用基于路徑資源分配機制以排除交通管理的調度策略對路徑規(guī)劃性能的影響，依此設計基于禁忌算法求解多AGV 系統(tǒng)的全局路徑搜索。

本文的主要內(nèi)容包括：

（1）構建地圖模型拓撲結構生成XΜL 文件存儲包含信息。

（2）設計禁忌搜索算法原理步驟，基于目標函數(shù)求解最優(yōu)路徑。

（3）進行不同規(guī)模算例下的分組實驗，驗證禁忌搜索算法對路徑能耗屬性、時間屬性和路徑負載均衡目標參數(shù)的優(yōu)化效果。

2 方法

為系統(tǒng)構建環(huán)境模型是AGV路徑規(guī)劃過程的重要組成部分，是將實際工廠作業(yè)環(huán)境的物理空間抽象模擬為算法可處理的數(shù)據(jù)環(huán)境，具體實現(xiàn)物理空間和數(shù)據(jù)環(huán)境的相互映射。

環(huán)境信息已知的多AGV 路徑規(guī)劃，路徑規(guī)劃流程為上位機依據(jù)任務分配準則匹配相對應的AGV，分配準則為固定的均衡任務分配順序，順序依據(jù)為先到先得，訂單就近原則匹配起始點最近的AGV，上位機調度系統(tǒng)進行最短路徑搜索并逐段下發(fā)可行駛的路徑資源。之后AGV 再向調度系統(tǒng)申請下一路徑資源，調度系統(tǒng)對競爭路徑資源的AGV的集合進行優(yōu)先級排序和判斷阻塞區(qū)域類型，進行交通管理。通行方向相同的AGV或者是只允許單輛AGV通行該區(qū)域，將線段或是阻塞區(qū)域等路徑資源分配給優(yōu)先級最高的AGV，其他AGV 排隊等候。AGV 每駛離占用的路徑資源，便上行報告上位機，上位機調度系統(tǒng)釋放該資源。進入循環(huán)流程，直到所有分配訂單的AGV完成作業(yè)，自動泊車。

2.1 模型構建

AGV任務的規(guī)劃決策建立在已知環(huán)境信息的基礎上，地圖的構建就是對環(huán)境信息的描述過程，地圖建模方法直接決定著環(huán)境信息表達的精確性和復雜度，影響著路徑搜索的效果與效率。常用的方法有幾何建模法、柵格建模法和拓撲建模法。幾何建模法就是將環(huán)境信息抽象為多點折線或圓弧等幾何特征對地圖進行描述，從而簡化地圖的表示，適用于小尺度或靜態(tài)環(huán)境下的應用；柵格建模法是將環(huán)境空間均勻地劃分為若干大小相等且固定不變的柵格，每個柵格具有唯一的位置信息，但信息分辨率較低，數(shù)據(jù)結構復雜；拓撲建模法是將關鍵站位的狀態(tài)和位置信息抽象為節(jié)點形式，相鄰節(jié)點用有向線段連接，表征連通狀態(tài)，從而形成點線相連的關系網(wǎng)[8]。不同建模方式均存在各自的優(yōu)勢與不足，如表1所示，需根據(jù)具體應用場景選擇適應系統(tǒng)方案的建模方法。

表1 常用建模方法

針對倉儲環(huán)境站位密集布置的應用場景，拓撲建模法優(yōu)勢明顯，具有計算效率高、內(nèi)存空間小和構造過程簡潔的特點，尤其適用于關鍵站點的多聯(lián)通狀態(tài)，地圖表達更加緊湊。同時考慮系統(tǒng)實現(xiàn)訂單規(guī)劃決策、AGV位姿監(jiān)控、可視化地圖管理等功能，采用拓撲地圖法進行系統(tǒng)模型的構建，將作業(yè)環(huán)境下的AGV 導航定位構建的復雜電子地圖和現(xiàn)場物理空間抽象建立拓撲結構，拓撲結構節(jié)點組成如表2 所示。拓撲地圖在搜索計算最短路徑時的復雜度取決于環(huán)境中可通行的節(jié)點的數(shù)量，系列節(jié)點和連接節(jié)點依次表示功能站點和行駛路徑節(jié)點，連線節(jié)點線段的權值表示具體的路徑代價。

表2 拓撲結構節(jié)點

結合實際的生產(chǎn)車間環(huán)境，將作業(yè)環(huán)境下的AGV導航定位構建的復雜電子地圖和現(xiàn)場物理空間抽象建立拓撲結構模型，繪制行駛節(jié)點和各個功能站點組成的強連通性的有向帶權圖。在構建系統(tǒng)拓撲結構時，考慮AGV 轉彎角度限制，利用二次貝塞爾曲線函數(shù)對設計的曲線路徑做平滑處理，使得AGV 在規(guī)劃的可行路徑上平穩(wěn)自然運動。模型地圖信息存儲為xml文件，包含路徑搜索需要的節(jié)點、站點、路徑線段信息、阻塞信息，如圖2所示。

圖2 地圖存儲信息

拓撲模型有向帶權圖表示為F(xl)＜F(xbestl)，如圖3所示，其中P={1,2,…,n,n+1} 表示節(jié)點和站點集合，Point集合表示中繼、交叉的行駛路徑節(jié)點，節(jié)點坐標為(x,y)；Location 集合表示工作站，站臺屬性為(x,y,m)，(x,y)表示該點在地圖中的空間位置坐標，m 表示在該點AGV 所要完成取卸貨和充電的功能動作；將路徑描述為有向帶權線段E，箭頭表示有向路徑的方向，路徑權值采用cost(Length,Maxvelocity)的形式，表示AGV行駛路徑線段的時間成本，其中Length 表示路徑節(jié)點間的實際距離，Maxvelocity 表示路徑設置的速度閾值。

多AGV系統(tǒng)的路徑優(yōu)化問題的基礎約束保證系統(tǒng)狀態(tài)正常及功能完備。容量約束為每一個作業(yè)訂單只對應一輛AGV。工作時長約束為AGV 從起始點出發(fā)到完成作業(yè)訂單的時長不能超過設置閾值[9]。

2.2 禁忌搜索算法

2.2.1 算法介紹

傳統(tǒng)的經(jīng)典算法Dijkstra 算法于1959 年由荷蘭科學家Dijkstra提出，該算法是單源路徑算法，用來求解一個頂點到其余各頂點的最短路徑問題，它以起始點為中心向外層層擴展，直至擴展到終點為止，計算得到最短路徑。Dijkstra 算法能夠簡潔有效地找到最優(yōu)解，但不足之處在于O(n2)的計算復雜度，當數(shù)據(jù)節(jié)點龐大時所需的節(jié)點繁多，效率隨著數(shù)據(jù)節(jié)點的增加而下降，耗費大量內(nèi)存空間與計算時間，并不能很好地滿足多AGV動態(tài)路徑規(guī)劃的系統(tǒng)需求[10]。

傳統(tǒng)的啟發(fā)式的A*算法搜索速度快且效率高，能在一定程度上克服搜索過程中的早熟現(xiàn)象，在機器人路徑規(guī)劃中得到了廣泛應用。但A*算法同樣存在限制，在路徑搜索過程中，隨著地圖面積的增大其搜索空間會產(chǎn)生多余的搜索節(jié)點，導致算法效率降低，耗費大量內(nèi)存空間與計算時間。相對而言，智能優(yōu)化算法可以更為有效地解決路徑規(guī)劃的多約束問題，通過將搜索路徑轉化為尋找函數(shù)最優(yōu)值，從而實現(xiàn)多AGV 系統(tǒng)路徑規(guī)劃中的最短路徑搜索[11]。

圖3 地圖模型

1986年，禁忌搜索（Tabu Search，TS）算法由Glover教授正式提出。其通過引入一個靈活的存儲結構和與之對應的禁忌準則，并通過藐視準則赦免一些被禁忌的優(yōu)良狀態(tài)，借此保證多樣化的有效搜索來實現(xiàn)最終的全局優(yōu)化[12]。其最主要的特點就是采用了禁忌技術和特赦規(guī)則，使得算法可以跳出局部最優(yōu)解，進行有效的計算，最終實現(xiàn)全局的優(yōu)化。禁忌搜索算法的搜索結果依賴于初始解和鄰域的映射關系，計算靈活，收斂速度快，能夠有效提高搜索速度和解的質量。尤其是在問題規(guī)模較為龐大、傳統(tǒng)搜索方法不能在較短時間內(nèi)求得問題的最優(yōu)解，禁忌搜索算法的優(yōu)勢更加明顯，是適應求解多AGV系統(tǒng)路徑搜索的理想算法。

逐步尋優(yōu)的路徑搜索算法一般采用貪婪思想對當前解的鄰域進行搜索，這樣的搜索方式使得鄰域的結構和初始解的選取決定了其搜索速度性能和解質量的優(yōu)劣，且無法保證求解算法的全局最優(yōu)。在禁忌搜索算法中，將已經(jīng)實現(xiàn)過的局部最短方案保存至禁忌表，在后續(xù)檢索相似路徑時避過禁忌列表中的點，避免局部最短路徑作為最優(yōu)解出現(xiàn)，當局部最短路徑成為全局最短路徑時，再特赦為算法最優(yōu)解[13]。

2.2.2 算法結構設計

（1）構造初始解

從起始頂點SID出發(fā)，依據(jù)地圖聯(lián)通信息，將各節(jié)點加入到路徑列表中，直到搜索終點DID加入，即得到SID到DID的初始解路徑。逐步尋優(yōu)的路徑搜索算法一般采用貪婪思想對當前解的鄰域進行搜索，這樣的搜索方式使得鄰域的結構和初始解的選取決定了其搜索速度性能和解質量的優(yōu)劣，且無法保證求解算法的全局最優(yōu)。在禁忌搜索算法中，將已經(jīng)實現(xiàn)過的局部最短方案保存至禁忌表，在后續(xù)檢索相似路徑時避過禁忌列表中的點，避免局部最短路徑作為最優(yōu)解出現(xiàn)，當局部最短路徑成為全局最短路徑時，再特赦為算法最優(yōu)解。

（2）鄰域解迭代

基于當前解在鄰域中迭代搜索，鄰域滿足拓撲結構聯(lián)通屬性，計算路徑搜索當前解的邊屬性總權重，邊屬性權重為AGV 理想行駛時間，用拓撲地圖節(jié)點間邊長和最大速度閾值作商取值。隨著鄰域解的迭代，基于目標函數(shù)評判所迭代鄰域解對求解路徑時間屬性、能耗屬性和系統(tǒng)運行穩(wěn)定程度的積極性。

（3）目標函數(shù)

定義節(jié)點集合P（point）和線段集合S（segment）的路徑邊屬性總權重值的時間評價函數(shù)d(m)為：

目標函數(shù)表達式定義為：

目標函數(shù)對于迭代鄰域解的評判基于求解路徑的時間屬性、能耗屬性和系統(tǒng)運行穩(wěn)定程度。能耗屬性參考依據(jù)為AGV 作業(yè)所行駛的物理距離，求解出的行駛物理距離越大，AGV 車體和使用電量等能耗越高。計算求解的AGV 理想行駛時間越長，路徑邊屬性總權重值的評價函數(shù)d(x)越大，則對應目標函數(shù)值越大，積極性越小。路徑網(wǎng)絡負載分布集中程度的系數(shù)項中，隨著普通節(jié)點數(shù)量的減少和交叉節(jié)點的增多，反映系統(tǒng)對交叉節(jié)點資源的競爭使用程度，負載集中系數(shù)項越大，則AGV 作業(yè)路徑阻塞障礙更為普遍。綜上，系統(tǒng)的高效穩(wěn)定性能取決于目標函數(shù)的各個組成，且最優(yōu)路徑將具有最小的目標函數(shù)值。

（4）禁忌、終止和特赦規(guī)則

禁忌對象：基于連通性的搜索路徑作為禁忌對象，禁忌表中收納該局部最優(yōu)解。

禁忌規(guī)則：在候選解中選出適應值最好的候選解，將其與當前最優(yōu)解進行比較，目標函數(shù)如果優(yōu)于當前最優(yōu)解，則更新替換，并且作為下一個迭代的當前最優(yōu)解，然后將對應的操作加入禁忌表；如果目標函數(shù)不優(yōu)于當前最優(yōu)解，就從所有候選解中選出不在禁忌狀態(tài)下的最好解作為新的當前最優(yōu)解，并將對應操作加入禁忌表。

禁忌長度：設置禁忌長度，限制被禁忌的對象需要進行對比的步數(shù)，其值可以根據(jù)問題的規(guī)模大小，取常數(shù)。

候選集合的確定：將從當前解的鄰域中選擇交換算子生成新搜索路徑作為候選集合。

終止準則：最大迭代步數(shù)作為算法的終止準則。

特赦規(guī)則：在算法迭代產(chǎn)生當前最優(yōu)解的同時，記錄判斷該解的評價函數(shù)值，當該解優(yōu)于當前問題的最優(yōu)解時，將其從禁忌表中特赦。

2.2.3 算法步驟流程

算法流程圖如圖4所示。

圖4 算法流程圖

算法步驟如下：

（1）初始化模塊參數(shù)，禁忌列表List_T 置空，就近優(yōu)先逐節(jié)點加入路徑，生成最短路徑初始解xl；

（2）在xl的鄰域L(List_T,xl)中選出滿足禁忌要求的候選集Cand_L(xl)；

2.3 算法實現(xiàn)

本文用Java語言實現(xiàn)禁忌搜索算法，代碼結構分為main（）、ReadIn_and_Initialization（）、Construction（）、Calculation（）、Tabu_Search（）、Check（）和Output（）函數(shù)模塊。其中main（）函數(shù)構建算法的主體框架；ReadIn_and_Initialization（）的功能是讀取存儲xml 地圖文件并初始化所有變量；Construction（）、Calculation（）、Tabu_Search（）分別實現(xiàn)禁忌搜索算法中的初始解構建、對應解的適應值計算和對定義鄰域進行搜索并對應標準選擇禁忌；Check（）函數(shù)的功能是用來檢驗解是否滿足對應的所有約束；Output（）函數(shù)輸出結果。

3 實驗

本文將通過仿真實驗對這幾種常用路徑規(guī)劃算法進行比較，并且結合機器人實際運行情況對幾種算法進行分析。

運輸訂單的生命周期如圖5所示。

圖5 訂單生命周期

創(chuàng)建運輸訂單后，其初始狀態(tài)為RAW；設置運輸訂單參數(shù)，激活狀態(tài)為ACTIVE；可匹配AGV 狀態(tài)轉換為DISPATCHABLE；UNROUTABLE 則不進行任何處理；AGV執(zhí)行移動指令任務訂單狀態(tài)為BEING_PROCESSED。AGV 的處理運輸訂單失敗，則將其標記為FAILED。如果AGV 成功處理了整個運輸訂單，則將其標記為FINISHED。AGV 總能耗用AGV 該批序列訂單完成過程中的總充電次數(shù)衡量定義。任務完成時間取決于最后一個任務的結束時間，用來衡量同批序列任務從生成到全部完成的總大時間開銷，任務完成時間越小則系統(tǒng)效率越高。

改變總節(jié)點個數(shù)、路徑邊數(shù)建立不同規(guī)模地圖模型，做分組實驗驗證禁忌搜索算法性能。實驗仿真觸發(fā)200個任務訂單，跟蹤監(jiān)測系統(tǒng)總能耗、任務完成時間、死鎖情況出現(xiàn)概率和任務完成比率，來對標路徑優(yōu)化算法在能耗屬性、時間屬性和系統(tǒng)運行負載均衡屬性上的優(yōu)越性，測試用例執(zhí)行狀態(tài)跟蹤表如表3～表5所示。

表3 40節(jié)點地圖模型中路徑搜索算法對比

表4 100節(jié)點地圖模型中路徑搜索算法對比

禁忌搜索算法的核心是在循環(huán)中構建一個禁忌循環(huán)列表，采用動態(tài)更新的方法來實現(xiàn)短期循環(huán)記憶，以避免搜索出現(xiàn)相同的解。經(jīng)實驗驗證，在一般情況下，禁忌搜索算法在處理時間、系統(tǒng)能耗和任務完成比率上相差不大，但在項目規(guī)模較大的情況下，禁忌搜索算法相比于傳統(tǒng)經(jīng)典算法Dijkstra的計算時長優(yōu)越性顯著體現(xiàn)，相對于啟發(fā)式A*算法的系統(tǒng)運行流暢度顯著提升。隨著系統(tǒng)規(guī)模的增大，求解路徑能耗更低，用時更少，可以有效地均衡全局路徑的資源使用，充分體現(xiàn)基于禁忌搜索的多AGV路徑優(yōu)化算法的必要性和優(yōu)越性。

表5 1 000節(jié)點地圖模型中路徑搜索算法對比

4 結束語

隨著5G時代和工業(yè)4.0的到來，企業(yè)智能制造的不斷改造升級，AGV移動機器人扮演著相當重要的角色，而對AGV路徑規(guī)劃技術的依賴要求也日益增高[14]。多AGV系統(tǒng)的路徑規(guī)劃，要求其按照一定的參數(shù)指標，在任務區(qū)域求解出滿足要求的優(yōu)化可行路徑。禁忌搜索算法在一定程度上而言，算法方案較為復雜，解的要素偏多，運算工作量較大，且智能優(yōu)化算法的收斂速度和收斂效果存在一定限制。

多AGV系統(tǒng)的路徑規(guī)劃問題屬于NP問題，約束條件復雜，問題規(guī)模和求解難度大，本研究有重要的學術意義，有助于Agent路徑問題及相關優(yōu)化問題的發(fā)展[15]。在未來的研究方向中，基于本文集中式AGV 控制系統(tǒng)模式的全局路徑規(guī)劃，結合分布式AGV 控制系統(tǒng)的局部路徑規(guī)劃，可以完善AGV的避障功能，提高系統(tǒng)的穩(wěn)定性和抗干擾性。