徐 力，劉云華，王啟富

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

1 引言

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

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

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

2 問題描述及空間建模

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

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

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

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

圖1 路徑規(guī)劃空間建模

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

3 改進自適應(yīng)遺傳算法

3.1 生成初始種群

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

3.2 適應(yīng)度函數(shù)

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

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

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

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

結(jié)合修正后路徑長度和路徑相關(guān)的懲罰函數(shù)，機器人路徑規(guī)劃的適應(yīng)度函數(shù)表示如下：

3.3 改進遺傳算子

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

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

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

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

3.4 自適應(yīng)策略

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

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

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

圖2 自適應(yīng)交叉及變異概率

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

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

3.5 改進自適應(yīng)遺傳算法實現(xiàn)步驟

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

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

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

步驟3計算當(dāng)代交叉概率，執(zhí)行交叉操作，產(chǎn)生新種群。

步驟4計算當(dāng)代變異概率，執(zhí)行變異操作，產(chǎn)生變異后種群。

步驟5將種群中個體代入適應(yīng)度函數(shù)計算適應(yīng)度值。

步驟6判斷是否滿足適應(yīng)度偏差條件，若滿足逆轉(zhuǎn)條件，則執(zhí)行逆轉(zhuǎn)操作，若不滿足轉(zhuǎn)步驟7。

步驟7判斷是否滿足終止條件，若滿足則輸出結(jié)果，否則轉(zhuǎn)步驟3，繼續(xù)執(zhí)行算法直至相鄰迭代種群最優(yōu)適應(yīng)度偏差小于閾值或達到指定迭代次數(shù)。

算法流程圖如圖3所示。

圖3 自適應(yīng)遺傳算法流程圖

4 算法驗證

4.1 MATLAB算法驗證

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

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

表1顯示，改進自適應(yīng)遺傳算法規(guī)劃出的路徑比傳統(tǒng)遺傳算法規(guī)劃出的路徑長度縮短了11.1%，比改進遺傳算法規(guī)劃出的路徑長度縮短1.9%。改進自適應(yīng)遺傳算法以更少代數(shù)和更短時間規(guī)劃出最優(yōu)路徑。

圖4 柵格地圖算例

圖5 圖4（a）算例規(guī)劃路徑對比

圖6 圖4（a）算例適應(yīng)度值與迭代次數(shù)關(guān)系對比

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

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

圖7 圖4（b）算例規(guī)劃路徑對比

圖8 圖4（b）算例適應(yīng)度值與迭代次數(shù)關(guān)系對比

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

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

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

4.2 系統(tǒng)應(yīng)用驗證

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

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

Inte3D 系統(tǒng)中對于機器人所在空間進行環(huán)境建模及柵格編碼，計算障礙物信息，給定AGV機器人的起止柵格編號，設(shè)定改進自適應(yīng)遺傳算法初始參數(shù)，調(diào)用路徑規(guī)劃算法進行計算，圖10為在某制造車間AGV路徑規(guī)劃實例。

圖10 規(guī)劃路徑

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

5 結(jié)束語

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