自適應遺傳算法在機器人路徑規劃的應用

徐 力，劉云華，王啟富

華中科技大學 機械科學與工程學院，武漢 430074

1 引言

隨著智能制造技術的應用與推廣，在港口及倉儲等方面的自動化需求日益旺盛，AGV 機器人技術得到越來越廣泛的應用。路徑規劃是AGV機器人技術的重要組成部分，研究高效可靠的路徑規劃算法，規劃出AGV機器人從起始位置運動到目標位置的最優路徑，對保障機器人工作穩定性，提高港口或倉庫的運行效率起著至關重要的作用。

路徑規劃問題約束關系復雜，屬于NP 困難問題。國內外針對AGV 機器人路徑規劃進行了大量的研究，主要的方法有幾何法、隨機采樣方法、智能規劃方法。幾何法中主要包括可視圖法[1]、柵格法[2]、輪廓法[3]、A*算法[4]、D*算法[5]、Dijkstra算法[6]等。隨機采樣方法主要包括概率路徑圖法和快速擴展隨機樹法等。智能規劃方法主要包括BP 神經網絡[7]、蟻群算法[8]、粒子群算法[9]、遺傳算法[10]等。幾何法需要對環境進行預處理，對于復雜的環境進行描述和計算較困難，較為適用于解決低維空間低自由度問題。隨機采樣方法作為增量式算法，是漸進最優的，收斂速度慢[11]。智能規劃方法是建立在生物智能或者物理現象基礎上的隨機搜索算法，遺傳算法是智能規劃方法主要算法之一，相比于其他搜索算法而言，遺傳算法在適應度函數對個體的評價下不斷進化，使種群的適應度不斷提高，進行有方向性的自適應搜索，適合求解路徑規劃問題。近年來部分學者基于遺傳算法求解路徑規劃問題的研究取得了可喜的進展，田欣等[12]提出新的遺傳參數自適應調整方式以提高自適應遺傳算法的尋優效率；雷永鋒等[13]提出正弦式自適應遺傳算法以避免種群進化停滯和陷入局部最優等現象；胡赤兵等[14]提出遺傳算子的自適應調整函數對遺傳算法進行改進，提高算法效率及有效性。

AGV 機器人路徑規劃中需要處理復雜的避障問題，現有遺傳算法在種群初始化、算法迭代等環節代價函數建模困難，路徑搜索效率低[15]，耗費較大的計算和存儲資源，尤其在求解復雜工程約束環境下的路徑規劃問題時效率低下，往往需要花費很長時間才能規劃出可行路徑，而且容易陷入局部最優問題[16]。針對這一問題，提出一種基于自適應遺傳算法的機器人路徑規劃方法，該方法引入逆轉算子，并添加插入算子和刪除算子，提出新的自適應策略調整交叉和變異算子，有效降低陷入局部最優概率。

2 問題描述及空間建模

車間AGV機器人路徑規劃是在障礙空間中計算待規劃機器人從初始位姿到最終位姿所經歷的一系列點和線所組成的無干涉無碰撞軌跡，且軌跡為滿足優化目標（如路徑最短，轉動角度最小等）的合理可行路徑。在路徑規劃算法中，考慮到AGV機器人外形尺寸影響，需對障礙物的尺寸向外擴展，以便將機器人表示為搜索空間中質點，由軌跡規劃算法計算出從起點到終點的一系列點和線所連成的軌跡路徑。

機器人路徑規劃過程本質上是在滿足約束條件的所有可行路徑中搜尋一條最優路徑或多條可行路徑，該過程可表示為：

式中，f(p)為路徑相關的目標函數，p為路徑，ps為起點，pt為終點，Γ(ps,pt)為從ps至pt的路徑集合。

為提高路徑規劃算法執行效率，通常需要進行路徑規劃空間建模。不妨以左下角為坐標原點，建立如圖1所示的二維直角坐標系，設規劃空間的像素坐標范圍為(Xmin,Xmax,Ymin,Ymax),X、Y軸的像素單位為px、py,X、Y軸的等分數為nx,ny,則有：

圖1 路徑規劃空間建模

將圖1規劃空間劃分為一系列柵格，每個柵格用點(xi,yi)表示，從原點起沿X、Y軸對柵格編號，編號為：

3 改進自適應遺傳算法

3.1 生成初始種群

現有遺傳算法求解路徑規劃問題時初始種群往往是隨機選取，易產生不可行路徑，影響規劃算法求解。為避免引入不可行初始路徑，需要利用機器人起止位置信息產生初始種群。其步驟為：將機器人初始位置作為起點加入路徑，在起點所在行中的搜尋所有可行柵格并隨機選取一點作為路徑下一點，依此方法逐行搜索并確定一個可行柵格加入路徑，直到終點所在行，并將機器人目標位置作為終點加入路徑。該方法確保初始路徑可行，避免了現有遺傳算法隨機產生初始種群可能導致初始路徑不可行的問題，提高規劃路徑搜索效率。

3.2 適應度函數

通常遺傳算法中采用適應度函數評價種群個體質量，用于確定該個體進入下一輪迭代的概率，對遺傳算法的收斂速度以及找到最優解的概率起著至關重要的作用。適應度函數與路徑距離相關，其路徑總長為：

上式只考慮路徑距離，未能考慮種群個體相鄰兩點間距離的影響，相鄰兩點距離較遠易導致可行路徑遺漏，需減少相鄰兩點距離較遠的個體數目，增加種群搜索范圍，為此在上式中增加路徑途經柵格數目修正項，修正后的L′為：

式中n為該路徑所通過的柵格數目總和。

為保證算法有效避障，采用路徑相關的懲罰函數增大種群中路徑包含障礙物較多個體的適應度，增加淘汰不良個體可能性。設pi、pi+1為相鄰兩個柵格點編號，pi pi+1表示相鄰兩點連線所涉及的柵格，f(pi pi+1)為pi pi+1中包含障礙物柵格的數量，則懲罰函數表示為：

結合修正后路徑長度和路徑相關的懲罰函數，機器人路徑規劃的適應度函數表示如下：

3.3 改進遺傳算子

現有遺傳算法的基因操作通常有選擇、交叉及變異等操作，但僅有以上操作難以有效避障，產生自交回路可能性高，易陷入局部最優等問題，導致難以搜尋可行路徑，為此加入刪除、插入和逆轉等操作算子，具體實現如下：

（1）刪除算子。路徑中可能會出現自交回路，增加了不必要的搜索路徑長度，浪費計算資源。通常自交回路在交點處存在相同的柵格編號，利用刪除算子判斷路徑中是否存在重復柵格編號及自交回路，若存在則刪除重復編號及自交回路。通過刪除算子對種群進行操作有助于消除自交回路，縮短路徑長度。

（2）插入算子。路徑中部分相鄰柵格可能存在距離較遠，跨域不同鄰域等問題，導致搜索路徑容易遺漏。引入插入算子判斷相鄰柵格是否處于同一鄰域，并將跨鄰域相鄰柵格的連線中點柵格編號插入路徑，依此方法對所有跨鄰域相鄰柵格插值直至滿足同一鄰域定義要求。

（3）逆轉算子。路徑規劃是復雜的迭代計算過程，其迭代求解過程中可能存在相鄰迭代種群最優適應度偏差過小，導致求解結果陷入局部最優。在相鄰迭代適應度偏差小于閾值時，引入逆轉算子對全局種群中每個個體除起點和終點外隨機確定兩個節點，將路徑中這兩個節點間隔的其余節點全部刪除并重新生成連續路徑，若新生成路徑適應度值更優則替換原先路徑參與迭代計算。逆轉算子較局部搜索的變異算子增強種群全局搜索及路徑變化可能性，減少陷入局部最優的概率。

3.4 自適應策略

現有遺傳算法中合理選擇交叉概率pc和變異概率pm是影響算法收斂性及求解最優路徑質量的關鍵因素。pc值過小，計算迭代過程中新個體難以產生，導致搜索過程緩慢，但過大的pc會破壞遺傳模式。pm過小不容易產生新個體，種群不能得到更新，pm過大不利于保留優良個體，導致搜索缺乏導向性。

由于pc和pm對算法性能和收斂性的巨大影響，所以不能人為隨意選取。為提高遺傳算法的收斂速度和性能，引入自適應交叉概率p′c和自適應變異概率p′m替換pc和pm，具體表達為：

式（8）和式（9）分別用于計算種群內個體交叉及變異概率，式中pc1、pc2為初始設定的交叉概率的最大值和最小值，pm1、pm2為初始設定的變異概率的最大值和最小值，f′為進行交叉操作的兩個個體間適應度的大者（簡稱為交叉個體適應度），favg為種群平均適應度，fmax為種群最大適應度，f為變異個體的適應度。按式（8）和式（9）計算的自適應交叉及變異概率隨種群內個體適應度值變化規律如圖2所示。

圖2 自適應交叉及變異概率

圖2（a）中交叉個體適應度f′接近平均適應度favg時其自適應交叉概率p′c較大，f′接近種群最大適應度fmax時p′c較小。圖2（b）中變異個體適應度f接近favg時其自適應變異概率p′m較大，f接近fmax時p′m較小。

自適應遺傳算法中采用自適應交叉概率p′c和自適應變異概率p′m進行交叉和變異操作，在路徑規劃迭代搜索前期階段，種群個體間適應度分布較為分散，隨迭代輪次增加，種群個體適應度分布逐漸趨于集中。種群個體間適應度分布對路徑規劃算法收斂性的影響分以下兩種情況討論。其一，算法迭代搜索前期，個體間適應度較為分散，自適應遺傳算法的交叉和變異概率比現有遺傳算法更小，保留種群內優良個體的概率更高。其二，迭代搜索后期，適應度越來越集中，自適應遺傳算法具有更大的交叉和變異概率，在保留優良個體的條件下可提高加入新個體的概率，從而有效降低陷入局部最優的可能性。

3.5 改進自適應遺傳算法實現步驟

基于現有遺傳算法的選擇、交叉、變異操作，改進自適應遺傳算法通過加入刪除、插入及逆轉算子，采用自適應策略對交叉和變異操作進行調整，獲得自適應交叉和變異概率，以此為基礎進行路徑迭代搜索，具體算法思路如下：

步驟1獲取AGV 機器人起點和終點信息，設置算法參數。

步驟2采用3.1節所述算法生成初始種群。

步驟3計算當代交叉概率，執行交叉操作，產生新種群。

步驟4計算當代變異概率，執行變異操作，產生變異后種群。

步驟5將種群中個體代入適應度函數計算適應度值。

步驟6判斷是否滿足適應度偏差條件，若滿足逆轉條件，則執行逆轉操作，若不滿足轉步驟7。

步驟7判斷是否滿足終止條件，若滿足則輸出結果，否則轉步驟3，繼續執行算法直至相鄰迭代種群最優適應度偏差小于閾值或達到指定迭代次數。

算法流程圖如圖3所示。

圖3 自適應遺傳算法流程圖

4 算法驗證

4.1 MATLAB算法驗證

基于上述算法，基于MATLAB R2016a進行算法驗證，分別使用傳統遺傳算法、文獻[17]提出的改進遺傳算法以及本文的改進自適應遺傳算法進行算法對比分析及驗證。三種算法驗證參數設定為：種群大小為80，進化代數為200 代，選擇概率為0.9，交叉概率為0.7，變異概率為0.01，改進自適應遺傳算法交叉概率最大值為0.8，最小值為0.6，變異概率最大值為0.1，最小值為0.01。為消除隨機性等偶然因素，在圖4（a）所示的20×20柵格地圖以及圖4（b）所示40×40 柵格地圖中分別重復運行三種算法100次。

使用傳統遺傳算法、改進遺傳算法、改進自適應遺傳算法對圖4（a）算例進行避障路徑規劃，規劃出的路徑如圖5所示，三種算法的適應度值與迭代次數關系對比如圖6所示，在100次重復運算中所求解的最短距離、相鄰迭代適應度偏差小于閾值的迭代代數及迭代收斂耗時作為評價指標。具體結果如表1所示。

表1顯示，改進自適應遺傳算法規劃出的路徑比傳統遺傳算法規劃出的路徑長度縮短了11.1%，比改進遺傳算法規劃出的路徑長度縮短1.9%。改進自適應遺傳算法以更少代數和更短時間規劃出最優路徑。

圖4 柵格地圖算例

圖5 圖4（a）算例規劃路徑對比

圖6 圖4（a）算例適應度值與迭代次數關系對比

表1 圖4（a）20×20柵格地圖算例對比

圖4（b）為40×40柵格地圖算例，該算例障礙分布較為密集，其初始參數設置與圖4（a）算例相同，規劃出的路徑如圖7所示，三種算法的適應度值與迭代次數關系對比如圖8所示，其計算結果如表2所示。

圖7 圖4（b）算例規劃路徑對比

圖8 圖4（b）算例適應度值與迭代次數關系對比

表2 圖4（b）40×40柵格地圖算例對比

表2顯示，在圖4（b）算例中改進自適應遺傳算法比傳統遺傳算法求解路徑長度縮短31.7%，比改進遺傳算法縮短9.4%。改進自適應遺傳算法在更少迭代代數能找到更優路徑。

上述驗證算例表明，改進自適應遺傳算法能以更少的迭代次數、更快的收斂速度得到更優路徑，且能有效避免陷入局部最優。

4.2 系統應用驗證

基于上述算法，采用面向對象的開發語言VC++11，研究開發了面向制造車間裝配工藝仿真的AGV機器人路徑規劃軟件模塊，該模塊在華中科技大學CAD 中心自主研發的三維工藝規劃與仿真系統——Inte3D 中得到應用，如圖9所示。在Inte3D系統中采用改進自適應遺傳算法對環境中的AGV 機器人進行路徑規劃，最終生成機器人的無碰撞運動軌跡，并用動畫仿真形式直觀展示AGV機器人在車間中運動場景。

圖9 Inte3D中AGV機器人路徑規劃軟件模塊

Inte3D 系統中對于機器人所在空間進行環境建模及柵格編碼，計算障礙物信息，給定AGV機器人的起止柵格編號，設定改進自適應遺傳算法初始參數，調用路徑規劃算法進行計算，圖10為在某制造車間AGV路徑規劃實例。

圖10 規劃路徑

該實例中制造車間共劃分為1 600 個柵格，單個柵格長為1 400，寬為700，計算出的最優路徑為65.36，耗時4.5 s，實例表明改進自適應遺傳算法能以較快的速度規劃出較短路徑。

5 結束語

針對現有遺傳算法求解路徑規劃問題時存在的收斂速度慢、易陷入局部最優等缺點，提出一種基于自適應遺傳算法的機器人路徑規劃方法。該方法引入逆轉算子，增加插入算子和刪除算子，采用自適應策略對交叉和變異概率進行調整，有效提高收斂速度，降低陷入局部最優可能性。算法分別在MATLAB和Inte3D系統中進行算例驗證，結果表明改進自適應遺傳算法相比傳統遺傳算法以及改進遺傳算法更為有效。考慮到實際工程中生產車間設備布局較為固定，通常AGV 機器人運動軌跡規劃是在工藝路線規劃仿真環節中完成，并利用數字孿生技術對仿真路徑與實際物理路徑進行對比分析，實現對AGV 機器人的調度監控。工程應用驗證表明改進自適應遺傳算法能滿足車間AGV機器人規劃仿真需求。