基于拓撲柵格建模的AGV路徑規劃算法優化

徐 晗，金 隼+，羅 磊,2，劉 順

(1.上海交通大學 機械與動力工程學院，上海 200240； 2.上海交大智邦科技有限公司 研發部，上海 201306)

0 引 言

AGV在智能制造車間中主要應用于重物搬運、刀具更換和生產清潔等作業場景，其在具有較優路徑規劃能力的前提下，能夠在一定程度上實現作業過程的全自動化。因此，對AGV的路徑規劃方法進行研究具有切實的工程應用意義，并且高效的路徑規劃方法也是后續研究中實現多AGV調度的關鍵技術基礎。

目前路徑規劃的研究方法主要有三大類：隨機采樣類、圖搜索類及群體智能優化類[1]。隨機采樣類算法具有較強的搜索能力，能夠有效解決高維空間及復雜約束問題[2]，但其運算成本過高，而且隨機性強。圖搜索類方法中比較具有代表性的是Dijkstra算法和A*算法[3]，但兩者都有較大的搜索量，相較Dijkstra算法而言，A*算法通過啟發式搜索的方式在一定程度上提高了計算效率[4]，并且成為了目前路徑規劃領域廣泛使用的算法[5]，但在地圖的規劃范圍過大時，其計算效率依舊不高。群體智能優化類的算法則代表了當今路徑規劃算法的發展方向，主要有煙火、粒子群、模擬退火及遺傳算法等[6]，綜合而言，遺傳算法在處理智能制造車間中的AGV路徑規劃時優勢明顯，其計算時間少，收斂性良好，適用于求解復雜的優化問題，且魯棒性好[7]。因此本課題將結合實際的智能制造車間作業環境，對遺傳算法進行改進，完成AGV路徑規劃的優化。

近些年遺傳算法在許多領域實現了廣泛應用，但在智能制造車間中AGV路徑規劃的相關應用研究卻較少，并且相關研究的對象主要集中于有規則布局的倉庫、碼頭等作業環境，對于有復雜布局的智能制造車間沒有高效可靠的解決方案。Nouri等[8]用調度程序代理將基于領域的遺傳算法應用于移動機器人的全局搜索空間，這樣能夠使其動態規劃更加簡單，但過程消耗時間長。Zabihzadeh等[9]則提出了一種具有雙信息素的遺傳、蟻群混合算法，可以提高機器人的作業速度，縮短工件的轉移時間，進而一定程度上解決耗時過長的問題。徐力等[10]對一種自適應的遺傳算法進行了應用，該方法通過改進遺傳操作算子，提出新的變異交叉自適應策略，也可以在一定程度上提高算法尋優的效率。以上研究只是針對簡單作業環境應用遺傳算法，并沒有對模型進行有效解析進而實現高效的路徑規劃，本文將以此為切入點，結合拓撲建模和柵格建模，提出一種不規則布局智能制造車間的AGV路徑規劃方法。

1 路徑規劃區域模型

1.1 智能制造車間環境描述

本文以上海交大智邦科技有限公司“轎車動力總成關鍵零部件國產加工裝備與工藝集成驗證平臺”的智能制造車間為研究對象，其車間環境如圖1所示，AGV運動路徑地圖如圖2所示。

該驗證平臺的作業AGV有3輛，分屬于3個不同的作業種類：上下料AGV、抽檢AGV和換產AGV。不同種類的AGV有不同的作業點位，如換產AGV的作業點位包括充電樁、夾具庫、OP30、OP50、OP90、OP110、OP130，各種類AGV的作業點位之間互不沖突。此處將考慮對換產AGV的作業路徑進行示例分析。從圖2中可以看出，該AGV的相鄰作業點位之間的距離差距較大，如Z1與Z2區中的作業點位排布緊密，而Z1與Z2區相互之間的距離以及二者與充電樁和夾具庫的距離又較遠，這就要求路徑規劃時需依據作業點位的疏密程度對不同區域應用不同的環境建模方法。

圖1 轎車動力總成關鍵零部件國產加工裝備與工藝集成驗證平臺

圖2 AGV運動路徑

1.2 模型建立

本文采用拓撲建模和柵格建模法實現環境建模。拓撲建模法是將路徑交叉點和作業點位視為節點，將行駛路徑視為邊，通過有序的節點集合描述AGV的路徑及其方向，該方法結構緊湊，尤其適用于多節點關聯場景，但在如Z1或Z2區這樣的作業環境下，其路徑規劃準確度卻較低；柵格建模法是將環境離散化為基礎柵格，通過對柵格的描述來獲取環境信息，該方法可以對復雜作業環境進行精確細致的描述，路徑規劃準確度高，但其計算復雜程度高，且運算量隨柵格數量的增加呈指數增加。目前的AGV路徑規劃建模方法都是采用單一的建模方式，但這樣的建模方式并不適用于如圖2所示的不規則作業車間。因此，針對不規則作業車間的環境建模需求，設計雙層建模方法，首先采用拓撲建模法建立總體結構模型，然后采用柵格建模法建立作業緊密區域的描述模型，即，拓撲建模時將Z1、Z2區視為節點(圖3)，柵格建模時將Z1、Z2區域用柵格分解。其中，C1、C2為該AGV必經的路口節點，如圖2標示。

圖3 換產AGV路徑拓撲

在對Z1、Z2類型區域進行柵格建模時，設定柵格單元長度為AGV外形尺寸最大值，柵格地圖大小為20*20，其中黑色柵格屬性值為1，表示障礙物所在區域，白色柵格屬性值為0，表示AGV可行區域，如圖4所示?；疑珫鸥癖硎镜氖钦系K物的膨脹區域，在實際環境中AGV不能視為質點，設置膨脹區域可以使得路徑規劃不經過障礙物邊界。左下角和右上角柵格分別代表路徑規劃的起點和終點。

圖4 區域柵格建模

以下將前文所述遺傳算法應用于區域柵格環境，并在此基礎上對算法進行優化。

2 區域內遺傳算法應用及優化

遺傳算法是一種模擬生物進化過程的計算模型，其通過模擬自然進化過程來搜索最優解。遺傳算法以種群中的所有個體為對象，并利用隨機化原理對一個編碼后的參數空間進行高效搜索。其中，編碼、初始種群設定、適應度函數設計、遺傳操作、控制參數設定這5個方面是遺傳算法的基本內容?；玖鞒倘鐖D5所示。

圖5 遺傳算法基本流程

2.1 編 碼

在構建如圖4所示的柵格地圖時，需要對每一個柵格進行編碼。在圖4中建立直角坐系，柵格的坐標值為 {x，y}。 對每一行中的柵格從左到右進行編碼，并逐行從下到上進行編碼，編碼方式為十進制。柵格坐標與編號的轉換公式為

(1)

其中，N為柵格的十進制編碼值，起始值為0，Sraw為每一行的柵格數量，[x]為高斯取整函數，%表示取余數函數。

2.2 種群初始化

路徑規劃的種群初始化就是按一定規則生成多條初始路徑，并判斷各路徑的連續性，并將間斷的路徑連接成連續的路徑。路徑的起點和終點分別設定為AGV的起始點和目標點，并在每一行中隨機選取一個柵格，構成路徑節點集合，按照圖6所示種群初始化流程完成路徑的初始化。

圖6 路徑種群初始化流程

其中，柵格j與柵格j+1是否連續的判別方法為

d=max{|xj+1-xj|,|yj+1-yj|}

(2)

當d=1時，柵格j和柵格j+1連續，否則不連續。

在對兩個不連續柵格選取中間柵格時，其坐標的計算方法為

(3)

2.3 適應度函數設計

適應度函數是衡量種群質量的唯一標準，適應度函數的設定取決于系統要優化什么樣的目標。在AGV的路徑規劃中，通常需要優化的首要目標就是路徑的長度。在傳統的路徑規劃遺傳算法中，適應度函數的表達式為[7]

(4)

其中，ng為所通過的柵格數，D為路徑的總長度，表達式為

(5)

通過f0衡量種群個體的適應度可以淘汰路徑長度較大的個體，但這種傳統適應度函數的問題在于，其并未結合AGV的實際運動過程來考慮路徑的平滑度。在實際的運動過程中，如果AGV轉向次數過多，不僅會增加運動時間，還會造成車輛機械結構的快速磨損，其運動的累積誤差也會隨轉向次數的增多而增大，因此這里需要對生成路徑的平滑度(非數學意義上的平滑)進行考量。

根據三角形的幾何關系，相鄰三點之間的距離關系可以表征路徑的平滑度。3個相鄰柵格之間的距離表達式如下

(6)

(7)

(8)

(9)

(10)

綜合考慮路徑的長度以及平滑度，改進后的適應度函數表達式如下

f=f0+f1

(11)

2.4 遺傳操作

2.4.1 選擇

傳統遺傳算法中通常采用輪盤賭的方式來選擇個體，即計算個體適應度占總體的適應度和的比例[7]

(12)

此方法雖然簡單有效，但極易使算法陷入局部最優。通過對照模擬退火算法的特性，本課題考慮使用其來對種群進行選擇。模擬退火算法思路來源于晶體冷卻過程：從某一較高的初溫出發，伴隨著溫度的不斷下降，結合概率突跳特性在解空間中隨機尋找目標函數的全局最優解，即在局部最優解能概率性地跳出并最終趨于全局最優。由于此處的最優解應為適應度最大值，故應對所有f(x)進行相反數化，因此適用于此處的模擬退火的接受概率公式為[11]

(13)

Δf=f(x0)-f(x)

(14)

(15)

其中，f(x0)、f(x) 分別為進化前后的適應度函數值；T為當前的溫度值；T0為系統初始溫度；α為系統溫度衰減率，為確保有較大搜索空間，通常取0.7≤α≤1.0；k為迭代次數；M為待反演參數的個數，通常取1。

模擬退火方法進行種群選擇的流程如圖7所示。

圖7 模擬退火種群選擇流程

2.4.2 交叉

交叉操作是指兩個個體之間的片段交換。將每一個個體(路徑)視為一條染色體，將每一個個體中的柵格節點看作染色體上的基因，交叉操作就是要找出兩條染色體上相同的基因，隨機選取其中一個，將此基因之后的片段相互進行交換。

設定交叉概率Pc，并隨機產生一個0-1之間的數Rc，將其與Pc比較，若Rc

2.4.3 變異

變異操作通過重新設定染色體中的片段，保證了種群的多樣性。變異操作需要隨機選取染色體(路徑)中除起點和終點外的兩個基因節點，并去除這兩個節點中間的柵格，利用前述種群初始化中路徑連續化的方法，生成連續的路徑片段。

設定變異概率Pm，并隨機產生一個0-1之間的數Rm，將其與Pm比較，若Rm

3 區域內改進遺傳算法仿真實驗

本節通過對上述區域內改進算法進行編程，并基于MATLAB R2018a平臺對算法的有效性進行仿真實驗驗證。本節將對改進后的適應度函數和種群選擇方法進行分別驗證，并考慮障礙物在柵格空間中的不同占比大小對算法有效性的影響。

3.1 改進適應度函數有效性驗證

由2.3節中式(4)～式(11)可知，f0是系統優化目標只考慮路徑長度的適應度函數，而f是優化目標考慮路徑長度以及路徑平滑度的適應度函數。本小節將對f0和f進行仿真實驗對比研究，以此來驗證附加考慮路徑平滑度的適應度函數設計是否有效。

在對適應度函數進行驗證時，種群選擇的方式選用式(12)輪盤賭方法。系統參數設定如下：地圖柵格總數為400，種群數量Np為200，遺傳算法的進化代數為70，交叉概率Pc為0.8，變異概率Pm為0.2。

分別對適應度函數為f0和f的模型進行計算，其AGV運動路徑如圖8和圖9所示。對兩種模型分別計算10組，得出每一個實驗組的最優路徑長度和兩種適應度函數模型各自的平均值，以及各實驗組AGV轉向角度的絕對值之和和兩種模型各自的平均值，見表1。

圖8 適應度函數為f0的AGV運動路徑

圖9 適應度函數為f的AGV運動路徑

兩條路徑對比可以看出，適應度函數為f0的運動路徑轉向次數較適應度函數為f的多，且根據表1可知，平均地，應用f的模型轉向角度絕對值之和相較于傳統模型少26%,這對于重型搬運AGV有顯著的積極影響。進一步地，通過對兩種模型路徑長度平均值的對比，發現對路徑平滑度進行附加考慮并不影響路徑的長度。由此可見，改進后的適應度函數應用于復雜作業環境中是十分有效的。

3.2 模擬退火選擇法有效性驗證

本小節將基于適應度函數為f的模型對模擬退火種群選擇法和傳統輪盤賭選擇法進行比較驗證。

模擬退火參數設定如下：系統初始溫度T0為10 000 K；為了保證有較大的搜索空間，系統溫度衰減率α設為0.9；依據式(15)，設定系統最終溫度為1 K，則迭代次數為87次。

對使用模擬退火選擇法的模型進行計算，其AGV運動路徑如圖10所示，圖11表征了每一代解的平均值與最優解的收斂關系。對該模型分別計算10組，得出每一個實驗組的最優路徑長度和樣本總體的平均值與方差，見表2。

表1 應用兩種模型的多實驗組路徑長度與轉向角度對比

圖10 模擬退火選擇法模型的運動路徑

從圖10和表2中多組實驗數據可知，模擬退火法選擇出的路徑平滑，且路徑長度也較短，更為核心的是，應用模擬退火選擇法的模型在多數情況下都能搜索到系統的最短路徑(29.80)，且總體方差小，而應用輪盤賭選擇法的模型卻十分容易陷入局部最優而得不到全局最優解。仿真實驗結果表明，應用模擬退火種群選擇法的模型有效避免了傳統遺傳算法易陷入局部最優的缺陷。

圖11 路徑長度優化曲線

3.3 障礙物數量對算法有效性的影響

本小節將對改進算法在不同障礙物空間中的有效性進行仿真實驗分析。

表2 兩種選擇法多實驗組路徑長度

在對不同障礙物占比的柵格環境進行設置時，發現當障礙物柵格占比接近50%時，傳統的遺傳算法和改進后的遺傳算法都難以解算出最優解，其可行路徑只有兩條，即圖12中的虛線和點線。由于該算法采用的柵格連續化方法(圖6)，當空間障礙物過多時，通過隨機方法選取的柵格之間難以形成連續的無障礙物的不間斷路徑，因此生成的路徑被不斷舍棄，使得程序極易陷入死鎖而無法解算出最優路徑。因此，當障礙物柵格占比接近或超過50%時，該算法就失去了有效性。

以下將對不同障礙物柵格占比分別為10%、20%、30%、40%的環境進行解算分析，其障礙物布置如圖13所示。通過設置不同的障礙物環境，并對不同模型各進行10組仿真實驗，各實驗組的最優路徑長度和AGV轉向角度絕對值之和見表3。其中，d為模型解算出的最優路徑長度，As為最優路徑的AGV轉向角度絕對值之和，T表示傳統遺傳算法模型，M表示改進后的算法模型。

圖12 障礙物柵格占比為50%的解算路徑

圖13 不同障礙物柵格占比

從表3中的數據對比可以發現，對于最優路徑長度和最少轉向度數兩個優化目標，改進后的算法在障礙物柵格占比越多的空間中越有效。在障礙物少、環境較為簡單的空間中，模型對路徑平滑度的考量表現出了良好的優越性，但模型采用的模擬退火方法卻失去了優越性，可能原因是當障礙物較少時，種群生成的初始路徑趨于連續化、同質化，因此傳統的輪盤賭選擇方法也能大概率搜索到最優解。

由上述仿真實驗驗證得出，對不同障礙物柵格占比的環境來說，改進后的復雜子區域路徑規劃算法的有效區間為障礙物占比小于等于40%，在此范圍內，障礙物占比越高，算法有效性越好。

4 拓撲節點間路徑規劃方法

在對Z1、Z2類型復雜子區域完成路徑規劃后，需要依照圖3對AGV的全區域路徑進行規劃。其實根據圖2可以看出，圖3各拓撲節點之間路徑平直，且無障礙物，在這種情況下，將節點之間的AGV運動路徑固定是最為簡單有效的方法，固定路徑的具體設置由工程師根據工廠的環境進行判斷，對于圖2的環境，其固定路徑如圖中粗虛線所示。

預設的固定路徑行駛可以通過簡單運動控制來實現。AGV通過里程計來獲取運動的里程信息和轉向角度信息，里程計信息來源于車身驅動輪光電編碼器和慣性測量單元記錄的相對位姿變化。在此基礎上，AGV的激光雷達實時測量其與車間固定參照物(如貼在墻體上的激光反射條，圖14)的距離，由此解算出AGV的實時位置姿態信息，進而實現固定路徑行駛。

因此，當AGV行駛在非復雜環境路段時，采用預設固定路徑的方法簡單高效，避免了全局柵格建模計算資源占用，系統反應慢的問題。

表3 各模型路徑長度及轉向角度對比

圖14 激光反射條

5 結束語

研究基于不規則布局的智能制造車間，提出了一種拓撲柵格混合建模的方法，并對復雜子區域的路徑規劃算法進行了優化改進。

(1)對整個AGV運動區域進行拓撲建模，視復雜子區域為節點，對節點間的路徑規劃采用預設固定路徑的方法。

(2)對復雜子區域進行柵格建模，模擬多障礙物的環境，應用遺傳算法對路徑進行規劃。

(3)改進了傳統遺傳算法的適應度函數，綜合考慮路徑長度和平滑度(非數學意義上的平滑)對路徑規劃的影響，有效改良了路徑的平滑度；提出了不同于傳統種群選擇方法的模擬退火種群選擇法，有效避免了傳統方法易陷入局部最優的缺陷，并通過MATLAB仿真實驗完成了驗證。

(4)仿真實驗驗證了改進算法的有效性區間，當障礙物柵格占全環境比小于等于40%時，算法有效，且在此范圍內，障礙物占比越高，其有效性越好。

對于實際的智能制造車間，改進后的路徑規劃方法可以應用到車間AGV調度系統中，并結合一定的調度策略，實現多臺AGV的有效調度。