基于遺傳算法改進的AGV 路徑規劃研究

馮 舒，劉 明

（云南民族大學 電氣信息工程學院，云南 昆明 650504）

0 引言

隨著人們環保意識的增強，節能減排在路徑規劃中的應用被越來越多的研究者所關注，越來越多的學者開始關注物流體系中的碳排放問題[1]。尋找一條自動引導搬運車（Automated Guided Vehicle,AGV）綠色節能路徑的研究課題受到極大重視。

目前，針對AGV 路徑規劃這一領域，已有很多學者進行研究。如：李健康等提出通過優化狀態轉移概率以及信息素更新的方法對蟻群算法進行改進，再應用于AGV 路徑規劃，獲得更短路徑[2]；熬國鑫等提出一種改進的BI?RRT 算法，引入可變權重實現目標導向，再對生成路徑作剪枝優化，最后進行平滑處理，得到更加平滑且較短的路徑[3]。

隨著各行各業對于節能減排的需求越來越迫切，學者們開始考慮AGV 路徑規劃的能耗問題，并且AGV 能耗指標已得到工業界以及學術界的重視。為了實現節能減排與AGV 物流運輸協同進行，一些學者開展了相關的探索和研究。例如：郭亞銘等對結合AGV 的轉向和直行兩種模式下的運動進行分析，建立單AGV 節能模型，利用Dijkstra 算法實現路徑規劃，得到距離短、能耗低的路徑；李俊蘭等提出一種結合改進Dijkstra 算法和非支配排序遺傳法建立的AGV 節能模型來規劃路徑。但這些方法都存在一定程度的復雜性，并且很少考慮轉角數目以及拐彎角度的大小，而這些因素對于AGV 的運動能耗影響很大[4]。

本文提出一種改進的遺傳算法。首先對地圖中的障礙物進行規則化處理，忽略不必要的冗余角點，降低計算復雜度以提高算法效率；其次，以路徑長度為優化目標，且對遺傳算法中的變異算子進行改進，使得路徑總向對目標有利的方向進行變異，尋找到一條最短、轉彎節點最少的路徑。

1 相關算法

遺傳算法是一種模擬生物遺傳進化規律的原理來進行尋優的算法。它融合了“適者生存”“物競天擇”的擇優方式以及遺傳基因交叉變異的特點，將需要求解的問題通過編碼形成染色體，模擬生物進化的過程，再通過種群迭代和選擇、交叉、變異等步驟，并多次迭代和循環，篩選出最優秀的染色體，最優染色體對應的解就是該問題的最優解[5]。標準遺傳算法流程如圖1 所示。

2 算法描述

基于遺傳算法對AGV 路徑規劃進行改進。首先本文對地圖中的障礙物進行簡化處理，改善角點過多的問題；再通過改進的遺傳算法進行路徑規劃，得到最優路徑。

2.1 障礙物規則化處理

該文將障礙物分為三類，分別為1×n（n∈R）的矩形障礙物、b×m（b，m∈R）的矩形障礙物以及不規則多邊形障礙物。對于1×n的矩形障礙物，因寬度只為一個柵格，因此只在其尺寸為1 的柵格兩側旁各取一個角點即可，如圖2 所示，淺灰色部分為角點柵格。針對b×m的矩形障礙物，以其4 個凸角點為柵格角點，如圖3 所示。對于不規則多邊形障礙物，將其填補為多邊形的最小外接矩形，如圖4 所示，灰色部分為填充部分，淺灰色部分為角點柵格。對障礙物簡化后，在一定程度上減少了冗余節點，可為后續路徑搜索做準備，有效提高搜索效率。

圖2 1×n 矩形障礙物取點

圖3 b×m 矩形障礙物取點

圖4 不規則障礙物取點

2.2 算法描述及其實現過程

首先，根據連通性矩陣可知角點ai與哪幾個角點連通，設從起始點ai到終點an之間，與ai連通的點有aj、ak、al、am，按角點順序連通，比如aj的順序排第一，則形成路徑a1→aj。

若a1與終點an有直接連通性，則跳過所有中間連通角點直接與終點連接。若在連通過程中出現與之前已連通過的角點重復的角點，為避免路徑出現死循環，則將兩角點之間的連通性斷開。

在連通過程中，如果某角點的所有連通角點在之前全部重復，則將連通關系全部取消，該角點無法到達終點。為了區別到達終點與未到達終點的路徑，設置懲罰函數將兩者區分，公式如下：

式中：Dall表示總路程長度；Df為已走完的路徑；Ddnf為未走的路徑；W為懲罰權重。本文將懲罰權重W設為5，將到達終點與未到達終點的路徑明顯區分開。

改進遺傳算法的過程如下：

1）對角點種群進行初始化處理，種群數目大小為popsize，個體的基因長度為poplength，并對初始種群采用輪盤賭的方式進行選擇，確定每個個體被選擇的次數。

2）進行交叉操作，本文采用前一個種群個體與后一個種群個體進行交叉。

3）對種群個體進行變異操作，產生隨機數rand，當隨機數rand 小于變異概率Pm時，隨機確定變異位置并對基因進行變異。

4）計算每個個體適應度值并按大小排序。

5）判斷是否達到迭代次數最大值，達到則輸出排名前10 的個體；如果不滿足則返回步驟1）繼續進行。

對于交叉變異，本文采用改進策略。首先，要找到合適的變異概率，一般會取一個很小的值。但是變異概率不宜很小也不宜過大，因為過大會破壞種群中的優良個體，過小則會使得種群過早收斂，這是由于在變異的過程中既會產生優良個體也會產生劣質個體[6]。本文針對這一問題對變異算子進行改進，過程如下：

1）設路徑為：

2）若變異點的位置與其前后基因位置滿足以下關系：當Nn+1-Nn-1=10 且Nn+1-Nn-1=1 時，則Nn-1、Nn、Nn+1形成45°角，此時，把基因Nn刪除，形成新的路徑。

3）若變異點的位置與其前后基因位置滿足以下關系：當Nn+1-Nn-1=11 時，Nn-1、Nn、Nn+1形成90°角，則把基因Nn刪除，形成新路徑。

4）如果變異點基因的位置與其前后基因位置滿足以下關系：當Nn+1-Nn-1=12，Nn+1-Nn-1=21 時，Nn-1、Nn、Nn+1形成135°角，就把基因Nn刪除。此時新形成的路徑為：

新形成的路徑相較于改進前長度更短，拐彎數量更少，因此，變異概率選較大一些。本文取變異概率Pm=0.3。

3 實驗仿真及分析

為檢驗改進算法的可靠性，將改進算法與遺傳算法從搜索時間、路徑長度、拐彎節點數、穿墻次數以及尋到的角點數等方面進行分析對比。本文的仿真在Matlab上進行驗證。

首先對柵格圖中的障礙物進行分類處理，用多邊形障礙物變換為最小外接矩形等一系列方法來減少搜索角點數，再對各角點之間的連通關系進行判斷；其次，為減少穿墻次數，改進算法將坐標數值改為柵格中心點的位置。這種方法相較于原先的常規數值坐標以柵格交點為中心點來說安全性更高，可以有效減少穿墻次數。坐標位置圖如圖5所示。圖6為實際角點中心點連接圖。

圖5 坐標位置圖

圖6 角點中心點連接圖

實驗在100×100 的柵格中進行，圖7 為改進后尋到的角點圖，明顯可以看出，改進后的角點相較于改進前角點數減少了很多，這為后續階段的計算提高了效率，減少了計算量。圖8 為所有角點的連通路徑。

圖7 改進角點圖

圖8 角點連接圖

圖9 為遺傳算法與改進算法在同一地圖中的路徑圖，具體實驗數據如表1 所示。由實驗數據分析可看出：改進算法尋到的角點數目相較于普通遺傳算法來說減少了68.8%，所用時間也略小于普通遺傳算法；并且改進算法在速度方面能夠更快地得到最佳路徑，找到的路徑長度也比普通遺傳算法更短。改進算法全程無穿墻事件發生，安全性更高，且拐彎角點也更少，有益于降低能耗。

表1 兩種算法實驗數據對比

圖9 100×100 柵格地圖兩種算法路徑

圖10 為迭代次數與距離的收斂曲線。由圖10 可知，迭代次數為50 次，隨著迭代次數的增加，曲線收斂越快，尋找到的路徑距離更短，最終找到相對最優的一條路徑。

圖10 迭代次數與距離的收斂曲線

4 結語

針對AGV 在自動化生產線工作的過程中存在的拐彎節點過多，以及穿墻現象導致與障礙物摩擦的問題，本文通過簡化障礙物減少搜索角點，達到簡化計算、提高搜索效率的目的；并且改善了柵格地圖的坐標系，在一定程度上減少了運用遺傳算法時造成的穿墻事件，提高了AGV 的安全性。其次，本文的遺傳算法以路徑最短為優化目標，且對遺傳算法的變異算子進行了改進，并對種群個體進行選擇、交叉、變異等操作，不僅找到的路徑更短，還能減少路徑的拐點數目，使得找到的路徑更加順滑，取得一系列優化效果。

由仿真實驗結果可看出：改進算法相對于普通遺傳算法來說不僅在一定程度減少了搜索時間，縮短了路徑長度，還減少了穿墻次數，有效提高了路徑的安全系數；并且通過對變異算子的改進，拐彎角點也有所減少，因此改進算法使規劃的路徑更加合理有效。但是也存在一些不足，如拐彎處的路徑不夠圓滑，且無法直觀看到耗能量，因此在后續工作會加入節能模型來使算法更加完善。