基于改進自適應遺傳算法的機器人路徑規(guī)劃

王 豪，趙學軍，袁修久

(空軍工程大學基礎部，西安 710000)

0 引言

路徑規(guī)劃問題是移動機器人的重要應用領域，一般是指在有障礙物的環(huán)境中，從起點到終點尋找一條避開障礙物的最優(yōu)路徑[1]。遺傳算法因其具備較好的通用性、魯棒性以及廣泛的可擴展性等特點，可作為研究機器人路徑規(guī)劃的主要算法。但該算法存在搜索速度較慢、局部搜索能力差等缺點，不能保證算法收斂的效率。應用于機器人路徑規(guī)劃時，遺傳算法得到的路徑長度往往較長且路徑拐點較多，移動中頻繁轉彎會對機器人的安全產(chǎn)生不利影響。隨著多種智能優(yōu)化算法的飛速發(fā)展，以及對于路徑規(guī)劃改進手段的增多，為通過改進的遺傳算法解決機器人路徑規(guī)劃問題提供了可靠且便捷的技術支撐。

傳統(tǒng)的移動機器人的路徑規(guī)劃主要有以下方法：基于搜索的路徑規(guī)劃(如Dijkstra[2]，A*[3]等算法)、基于概率的路徑規(guī)劃(如RRT系列算法[4])、基于智能算法的路徑規(guī)劃(如粒子群優(yōu)化算法[5]、蟻群算法[6]、遺傳算法[7]等)。Dijkstra算法空間復雜度和時間復雜度均較高，因此規(guī)劃速度較慢；A*算法引入了啟發(fā)式信息，待處理節(jié)點的數(shù)量得到了有效控制，因而算法的效率有了明顯的提高，但當存在多個最小值時，A*算法不能保證搜索的路徑最優(yōu)。基于概率的RRT系列算法極大地縮短了路徑規(guī)劃的時間，能夠快速得到一條無碰撞的路徑，但容易陷入“死區(qū)”，難以達到全局最優(yōu)。而基于自適應遺傳算法的路徑優(yōu)化不僅具有較好的收斂性，而且易于擴展。因此，選擇自適應遺傳算法進行改進，以期達到更好的路徑規(guī)劃效果。

目前，一些學者已經(jīng)針對機器人路徑規(guī)劃問題對遺傳算法進行了改進性研究。文獻[7]引入了插入算子和刪除算子，有效縮短了路徑的長度；文獻[8]引入了逆轉算子，有效避免了陷入局部最優(yōu)；文獻[9]采用人工勢場法對種群進行了初始化，提高了算法的收斂速度；文獻[10-11]在選擇個體時引入了模擬退火思想，提高了算法的全局搜索能力；文獻[12]結合了免疫克隆算子，提高了解的質(zhì)量。但是對于較為復雜的環(huán)境，以上算法的收斂性仍有提高空間。在此基礎上，提出了一種新的自適應遺傳算法，該算法設計了一種新的適應度函數(shù)，并且對遺傳操作加以改善，不僅結構簡單，而且易于實現(xiàn)。在經(jīng)過Matlab仿真后，發(fā)現(xiàn)該算法不僅能夠在復雜柵格環(huán)境下穩(wěn)定且快速地得到較優(yōu)解，而且得到的路徑相較于已有算法更短，路徑也更加平滑，從而提高了路徑規(guī)劃的效率。

1 路徑規(guī)劃模型

1.1 柵格法建模

構建移動機器人路徑規(guī)劃環(huán)境模型的方法通常有幾何特征圖法、可視化圖法、柵格圖法等[13]。由于柵格圖法構建的環(huán)境模型不僅能夠有效地表達環(huán)境中的各種信息，而且直觀、易于操作，因此，本文選擇柵格圖法構建環(huán)境模型。柵格圖法簡稱柵格法，首先產(chǎn)生一定數(shù)量均勻、規(guī)則的網(wǎng)格，然后通過賦予這些網(wǎng)格不同的數(shù)值以表示環(huán)境中不同的狀態(tài)信息。柵格的大小影響模擬的真實性和有效性，因此要合理地根據(jù)真實環(huán)境來設定。

為便于檢驗算法效率，將移動機器人當作運動的質(zhì)點考慮，且機器人運動過程中始終位于各柵格中心點及其連線上，環(huán)境中障礙物的位置已知且不發(fā)生變化。在建立柵格模型時，柵格面積的大小會對環(huán)境信息的表示、存儲空間以及算法運行的時間產(chǎn)生影響。本文柵格模型的大小為20×20，單位為m，將代表障礙物的柵格賦值為1，代表自由空間的柵格賦值為0[14]，在Matlab中建?？傻玫饺鐖D1所示的柵格模型。

圖1 柵格模型Fig.1 Grid model

圖中，黑色柵格為障礙物，白色柵格可自由通行。柵格中心坐標用(x,y)來表示。柵格編號范圍為1～400，起點位于區(qū)域左下角，編號為1，終點位于區(qū)域右上角，編號為400。令任一柵格編號為S，則柵格坐標(x,y)和編號S存在如下對應關系

(1)

式中，mod(·)為求余運算。

1.2 改進自適應遺傳算法介紹

本文在自適應遺傳算法思想的基礎上進行了改進。算法流程如圖2所示。

圖2 算法流程Fig.2 Flow chart of the algorithm

1.2.1 初始化種群

遺傳算法對于路徑的種群初始化要求隨機生成多個不與障礙物接觸的路徑，主要包括兩個步驟。

1)根據(jù)柵格環(huán)境選擇固定數(shù)量的柵格。機器人從起點到終點需要經(jīng)過每一行的柵格，因此每一行都至少有一個柵格在任意一條連續(xù)路徑中。所以初始化種群時首先在每一行隨機確定一個可自由通行的柵格，從而形成一條間斷的路徑。

2)將被選中的柵格連接為一條完整且連續(xù)的路徑。首先要判斷生成的相鄰柵格是否連續(xù)，判斷方法為

(2)

(3)

若新生成的柵格為障礙物柵格，則取其相鄰自由柵格進行替代，如果相鄰柵格均為障礙柵格,則重新生成新路徑。將生成的新柵格插入該路徑中，重復以上步驟，直到前后兩個柵格連續(xù)。當兩個柵格連續(xù)后，按照該方法依次連接生成后續(xù)節(jié)點，直到獲得連續(xù)可行的路徑。其中，路徑可表示為

P={p1,p2,…,pi-1,pi,pi+1,…,pn-1,pn}

(4)

式中：p1表示起點；pn表示終點；pi表示整條路徑中的第i個路徑節(jié)點；(pi,pi+1)表示第i段路徑。

為更好地模擬真實情況，增強初始種群的隨機性，將初始種群中該范圍的個體和采用隨機選擇路徑節(jié)點的個體以1∶1的比例進行設定。

1.2.2 適應度函數(shù)設計

為準確評判種群中個體的優(yōu)劣，設計一種適用于機器人路徑規(guī)劃的適應度函數(shù)對使用遺傳算法尋找最優(yōu)解的效率具有很大的影響。在傳統(tǒng)遺傳算法中，往往以路徑長度作為適應度函數(shù)[15]，這樣雖然函數(shù)結構簡單，但規(guī)劃出的路徑拐點數(shù)量較多，尤其是存在一些轉彎角度較小的拐點，不僅容易使機器人移動過程中產(chǎn)生安全問題，路徑規(guī)劃效率也會大大降低。針對傳統(tǒng)適應度函數(shù)存在的問題，提出了一種改進的適應度函數(shù)，該函數(shù)綜合評估了規(guī)劃中的路徑長度和拐點數(shù)量，改進的適應度函數(shù)如下

(5)

式中：L為規(guī)劃路徑的長度；N為路徑中節(jié)點的數(shù)量；T為路徑中的拐點數(shù)量，m，n分別為L和T的權值；參數(shù)r為常數(shù)。

參數(shù)r應根據(jù)環(huán)境尺度以及障礙柵格的數(shù)量和分布來設定。當環(huán)境尺度較大或障礙柵格較多且分布復雜時，應當選取更大的參數(shù)r，從而將種群中不同適應度的個體區(qū)分開來。參數(shù)m，n應根據(jù)環(huán)境復雜度和路徑特點進行設定，為使路徑長度與路徑拐點數(shù)量具有相同的比重，當環(huán)境較為復雜時，規(guī)劃所得路徑往往拐點較多，因此應適當增大m的取值，以平衡拐點數(shù)量對適應度評估的影響；當環(huán)境較為簡單時，路徑通常位于柵格模型對角線附近且拐點數(shù)量較少，此時應增大路徑拐點的權值n，以準確評判路徑適應度，為下一步遺傳操作奠定基礎。另外，m，n的大小要根據(jù)路徑實際特點進行設定。

1.2.3 遺傳操作

遺傳操作通常包括選擇、交叉和變異[16]。為了提高算法收斂速度，選擇初始種群中的個體時，在輪盤賭選擇法基礎上進行改進。根據(jù)每個個體適應度值占種群總適應度值的比例降序排列，將個體等分為“高適應度個體”、“中適應度個體”以及“低適應度個體”3類，然后按適應度大小將“高適應度個體”和“低適應度個體”從高到低進行一一對應。當采用輪盤賭法選擇到“高適應度個體”與“中適應度個體”時正常選擇，當選擇到“低適應度個體”時,選擇與其對應的“高適應度個體”。這樣可以使種群的適應度值很快達到較高水平，有利于路徑規(guī)劃算法的快速收斂，提高規(guī)劃速度。但這一步驟將降低種群多樣性，可能使群體陷入局部最優(yōu)。因此，可以通過自適應交叉算子和變異算子來跳出局部最優(yōu)，使種群整體保持高適應度的同時向更高適應度進化。

本文中的交叉操作選用單點交叉方法[17]。不同的路徑必然導致個體的長度和節(jié)點存在差異，因此被選中的兩個父代個體不一定存在相同的路徑節(jié)點。當兩個個體存在相同節(jié)點時，選取該節(jié)點作為交叉點，以確保交叉產(chǎn)生的子代個體代表的路徑仍然是連續(xù)的。若相同節(jié)點多于一個，則任意選擇其中一個相同節(jié)點進行交叉。若兩個體不存在相同節(jié)點，則取消交叉操作。交叉操作結束后，判斷其每個子代個體內(nèi)部是否包含相同節(jié)點，若有，則應刪除路徑的冗余部分。例如，假設兩個待交叉的父代個體為P1={1,21,105,…,269,289,310,…,376,379,400},P2={1,81,102,…,227,289,312,…,374,395,400}，選擇節(jié)點289進行交叉，交叉后所得的子代個體為P′1={1,21,105,…，269,289,312,…，374,395,400}，P′2={1,81,102,…，227,289,310,…，376,379,400}。

變異操作根據(jù)變異概率隨機選擇路徑中的兩個節(jié)點，而后刪除兩個節(jié)點的中間節(jié)點，將兩個節(jié)點直接相連。然后判斷該路徑是否經(jīng)過障礙物，如無障礙物則保留該路徑，如有障礙物則變異操作取消，保留原個體。這樣便能保證變異向著適應度提高的方向進行。

交叉概率和變異概率的取值對產(chǎn)生新個體的效率具有很大影響。傳統(tǒng)的遺傳算法通常采用固定的交叉概率和遺傳概率，雖能保證新個體的產(chǎn)生，但當種群進化到一定程度時，容易破壞適應度較高的個體[18]。為保留精英個體，引入Sigmoid函數(shù)，定義為

(6)

Sigmoid函數(shù)的圖形如圖3所示。

調(diào)整后的交叉概率Pc和變異概率Pm分別為

(7)

式中：Pc_max，Pc_min，Pm_max，Pm_min分別代表交叉概率的最大、最小值和變異概率的最大、最小值；fi代表第i代種群中個體的適應度；fiave代表第i代種群的平均適應度。

由圖3可知，當橫坐標fiave-fi的取值范圍為[-4，4]時，能夠較好地區(qū)分優(yōu)劣個體，從而賦予其不同的交叉、變異概率。

2 仿真實驗及結果分析

2.1 實驗環(huán)境及參數(shù)設置

在Matlab仿真環(huán)境下對本文改進算法進行實驗。實驗方法為：在20×20的柵格環(huán)境下(單位為m)設置障礙物，在該環(huán)境下，分別對本文改進算法、傳統(tǒng)遺傳算法以及文獻[12]改進遺傳算法進行仿真，比較3種算法所得最大適應度值、最短路徑的長度、拐點數(shù)量以及達到最短路徑的迭代次數(shù)，以檢驗該算法的優(yōu)化效果。

根據(jù)所設環(huán)境尺度及障礙柵格的數(shù)量和分布可知，路徑長度最短為26.87 m，即起點與終點相連的直線，長度一般不超過50 m，拐點數(shù)量通常為10～25。雖然路徑的拐點數(shù)量較多，但路徑長度初始設定值較大，為平衡兩者權重，適應度函數(shù)中參數(shù)n取值應為m的2～3倍，本文中，m為2，n為5，r為8000。

設置種群規(guī)模為300，最大進化代數(shù)為50。傳統(tǒng)遺傳算法的交叉概率為0.8，變異概率為0.2。文獻[12]改進遺傳算法和本文改進算法取相同的交叉、變異范圍，其中，Pc_max=0.8，Pc_min=0.08，Pm_max=0.2，Pm_min=0.02。

2.2 實驗結果及分析

設定實驗環(huán)境與實驗參數(shù)后，依次分別將3種算法在該環(huán)境下進行仿真實驗，得到如圖4所示的路徑規(guī)劃圖，以及如圖5所示的迭代曲線圖。

圖4 3種算法路徑規(guī)劃圖Fig.4 Path planning results of three genetic algorithms

圖5 3種算法迭代曲線圖Fig.5 Iterative curves of three genetic algorithms

從圖4可以明顯看出，在復雜的柵格環(huán)境中，傳統(tǒng)遺傳算法容易陷入“死區(qū)”，不宜達到較優(yōu)的結果。而文獻[12]改進遺傳算法有效克服了這一缺點，但規(guī)劃出的路徑仍不能達到最優(yōu)。通過本文中對自適應遺傳算法的改進，有效避免了傳統(tǒng)遺傳算法的缺點，同時優(yōu)化了路徑復雜度和平滑度，使規(guī)劃出的路徑長度進一步縮短，路徑的拐點數(shù)量也更少。

從圖5中可以看出，本文改進算法相較于其他兩種算法具有更快的收斂速度。經(jīng)對比可知，當算法迭代至第12次時，本文改進算法所得路徑適應度值達到了較高水平，說明了選擇操作的改進措施是行之有效的；在迭代過程中，傳統(tǒng)遺傳算法以及文獻[12]改進遺傳算法均出現(xiàn)了最優(yōu)個體被破壞，導致種群中最優(yōu)個體的適應度下降的現(xiàn)象，而本文改進算法迭代過程中，每一代種群的較優(yōu)個體由于交叉、變異概率較小，能夠得到很好的保留，而其余個體由于交叉、變異概率較大，能夠在不斷迭代中進化為更高適應度的個體，從而種群適應度能夠達到更高水平，驗證了自適應交叉、變異算子的優(yōu)化效果。在經(jīng)過50次仿真實驗后，對各指標求平均所得實驗數(shù)據(jù)如表1所示。

表1 仿真結果對比Table 1 Comparison of simulation results

從表1中的數(shù)據(jù)可以看出，本文改進算法相較于傳統(tǒng)遺傳算法和文獻[12]改進遺傳算法最大適應度值平均提高了28.93%和17.07%，路徑長度平均縮短了9.90%和5.37%。同時，本文改進算法仿真得到的最短路徑拐點數(shù)量和算法收斂迭代次數(shù)也相較于另外兩種算法更少。實驗數(shù)據(jù)說明，在障礙物數(shù)量較多以及環(huán)境復雜度較高時，算法的計算難度增大，但本文改進算法仍能夠得到較優(yōu)的結果。

上述實驗結果表明，本文改進算法優(yōu)化路徑長度的同時，提高了路徑平滑度和算法收斂速度，證明了本文提出的改進措施是有效的。

3 結束語

針對移動機器人的路徑規(guī)劃問題，提出了一種改進自適應遺傳算法，經(jīng)多次仿真實驗，改進后的算法在機器人路徑規(guī)劃問題中具備一定的可行性和有效性。算法具有以下特點：

1)針對適應度函數(shù)進行了改進，引入路徑拐點數(shù)量作為適應度評估標準之一，減少了機器人的轉彎次數(shù)，有利于提升安全性；

2)改進了輪盤賭選擇法，避免了適應度值較低的個體被選中，使種群能夠很快地達到較高的適應度值水平；

3)針對柵格模型下的路徑規(guī)劃設計了交叉和變異方法，使得算法更易于產(chǎn)生差異性較大的優(yōu)良個體；

4)設計了自適應交叉算子和變異算子，保留較優(yōu)個體的同時使種群進一步向更優(yōu)的方向發(fā)展。