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

張　毅，代恩燦，羅　元

(重慶郵電大學(xué) 國家信息無障礙研發(fā)中心，重慶　400065)

?

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

張毅，代恩燦，羅元

(重慶郵電大學(xué) 國家信息無障礙研發(fā)中心，重慶400065)

針對傳統(tǒng)遺傳算法存在的搜索效率低、易于陷入局部最優(yōu)解的問題，提出了一種改進的遺傳算法；采用簡單的一維編碼替代復(fù)雜的二維編碼，節(jié)約了存儲空間；在遺傳算子的設(shè)計中，重新定義了交叉算子和變異算子，避免了陷入局部最優(yōu)；最后將最短路徑和免碰撞相結(jié)合作為適應(yīng)度函數(shù)進行遺傳優(yōu)化；在種群的各項參數(shù)均相同的情況下，分別對改進遺傳算法和傳統(tǒng)遺傳算法進行了100次實驗；其中，改進遺傳算法搜索到最優(yōu)路徑的次數(shù)為95次，最短路徑長度為20.970 6，平均搜索用時217 ms；傳統(tǒng)遺傳算法搜索到最優(yōu)路徑的次數(shù)為62次,最短路徑長度為25.071 1，平均搜索用時345 ms；實驗結(jié)果表明，相比于傳統(tǒng)遺傳算法，改進遺傳算法搜索效率更高且能獲得更好的解。

遺傳算法；移動機器人；路徑規(guī)劃；交叉算子；變異算子

0　引言

導(dǎo)航技術(shù)是移動機器人研究領(lǐng)域的關(guān)鍵技術(shù)，其中，路徑規(guī)劃又是導(dǎo)航中最重要的任務(wù)之一。所謂路徑規(guī)劃，就是指在一個含有障礙物的環(huán)境中，按照某一性能指標(可以是行走時間最短、路徑最短或能量消耗最少等)，為移動機器人規(guī)劃出一條從起始節(jié)點到目標節(jié)點的最優(yōu)或者近似最優(yōu)的無碰路徑。移動機器人路徑規(guī)劃可分為兩種類型：一種是基于環(huán)境先驗信息的全局路徑規(guī)劃；另一種是基于傳感器信息的局部路徑規(guī)劃，后者環(huán)境信息是未知或者局部未知的，即需要傳感器來實時獲取障礙物的位置、尺寸、形狀等信息。全局路徑規(guī)劃是根據(jù)已有的環(huán)境地圖搜索一條從起始節(jié)點到目標節(jié)點的最優(yōu)或近似最優(yōu)的免碰撞路徑，全局路徑規(guī)劃涉及的主要問題是環(huán)境信息的表示以及搜索策略的選擇。全局路徑規(guī)劃通常應(yīng)用在障礙物為靜態(tài)障礙物、環(huán)境信息已知的環(huán)境中，當(dāng)障礙物不斷運動變化時，全局路徑規(guī)劃不再奏效，需要采用依賴傳感器信息的局部路徑規(guī)劃方法。

國內(nèi)外研究人員已經(jīng)花了很長時間在移動機器人路徑規(guī)劃方面，也產(chǎn)生了許多方法[1-2]。目前在路徑規(guī)劃領(lǐng)域應(yīng)用較多的方法有：滾動窗口規(guī)劃方法、人工勢場法、神經(jīng)網(wǎng)絡(luò)法、蟻群算法、Dijkstra算法、A*算法等。每一種算法都有各自的思想，并且都在不同的方面表現(xiàn)出了優(yōu)勢。但總的來看，上述方法都存在著某一或者某些方面的不足。如算法計算量大、搜索效率低、缺乏靈活性、易于陷入局部最優(yōu)解、全局路徑規(guī)劃的質(zhì)量不高以及自適應(yīng)能力差等方面。而遺傳算法作為一種優(yōu)化算法具有魯棒、靈活、適應(yīng)能力強等優(yōu)點，因此被廣泛應(yīng)用于許多優(yōu)化問題中并取得了不錯的效果。近十幾年來，遺傳算法在解決移動機器人路徑規(guī)劃問題方面也得到了廣泛的應(yīng)用。隨著研究的不斷深入，應(yīng)用遺傳算法進行移動機器人路徑規(guī)劃的不足逐漸被人們發(fā)現(xiàn)[3-6]，如存在著種群規(guī)模大、搜索空間大、收斂速度慢、易于陷入局部極小點等問題。針對這些問題，提出了一種改進的遺傳算法，編碼方式上摒棄復(fù)雜的二維編碼方式采用簡單的一維編碼，減小了編碼長度節(jié)約了存儲空間，重新定義了傳統(tǒng)遺傳算法中的交叉、變異等遺傳算子，加速了進化過程。并把免碰撞要求和最短路徑要求融合成一個適應(yīng)度函數(shù)，選取適應(yīng)度更高的個體，提高了種群的適應(yīng)能力。最后通過實驗驗證了改進遺傳算法的可行性和有效性。

1　遺傳算法的基本原理

遺傳算法是一種并行搜索算法[5-8]，它從一個隨機生成的初始解開始，操作過程中按照一定的規(guī)則，如選擇，復(fù)制，交叉，變異，不斷迭代計算，以獲得下一代種群中的個體。用適者生存優(yōu)勝劣汰的原則來指導(dǎo)搜索過程，使適應(yīng)度更強的個體不斷保留下來，并逐漸演變成更多更好的近似解，最終收斂到全局滿意解。

下面是遺傳算法的基本步驟。

Step1:由N個隨機生成的個體組成初始種群。

Step2:通過適應(yīng)度函數(shù)計算出當(dāng)前種群中每一個個體的適應(yīng)度函數(shù)值

Step3:判斷算法是否滿足終止條件，如果滿足終止條件則轉(zhuǎn)Step8。

Step4:按照個體適應(yīng)度值的大小進行選擇操作。

Step5:根據(jù)交叉概率進行交叉操作。

Step6:根據(jù)變異概率進行變異操作。

Step7:如果由N個新個體組成的新一代群體已經(jīng)產(chǎn)生，則轉(zhuǎn)Step2；否則，轉(zhuǎn)Step4。

Step8:輸出搜索結(jié)果，算法終止。

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

本部分的主要目的是提出一種用于解決移動機器人路徑規(guī)劃問題的改進遺傳算法。主要改進點有以下幾個方面：把復(fù)雜的二維編碼方式簡化為一維編碼，適應(yīng)度函數(shù)融合了最短路徑要求和免碰撞要求；在選擇操作過程中，將輪盤賭選擇和精英選擇進行了結(jié)合；優(yōu)化了遺傳操作中的交叉算子和變異算子；增加了新的遺傳算子——插入算子和刪除算子。有效防止了遺傳算法在進行路徑規(guī)劃時易于陷入局部最優(yōu)的情況。改進遺傳算法主要包括以下三個方面。

2.1環(huán)境建模及路徑編碼

本文運用柵格法來描述機器人的環(huán)境模型[3]，如圖1所示，二維平面上的柵格區(qū)域E即為機器人的運行空間。在此環(huán)境中存在著一定數(shù)量的障礙物。將柵格區(qū)域E的左下角設(shè)為坐標原點，水平向右為X軸，豎直向上為Y軸，每一個柵格區(qū)間代表一個坐標軸上的單位長度，把柵格區(qū)域E劃分成m×n個大小相同的方形柵格。按照從左到右，從下到上的順序，從柵格區(qū)域左下角第一個柵格開始給每一個柵格編號i(從零開始計)，則柵格編號i與坐標(xi，yi)互為映射關(guān)系，對應(yīng)關(guān)系如公式(1)所示。

(1)

其中:mod為取余運算，int為取整運算，N為每行的柵格數(shù)。

對機器人工作空間E和機器人本體作如下假設(shè)：

(1)機器人的工作空間為二維結(jié)構(gòu)化空間，機器人的高度不予考慮。

(2)環(huán)境中的障礙物位置信息利用其占據(jù)的柵格號來表示，障礙物的形狀、大小、位置已知且不發(fā)生變化。

(3)規(guī)劃過程中，將機器人作為質(zhì)點處理。

(4)規(guī)劃過程中，機器人速度大小不發(fā)生變化。

機器人路徑由多條線段組成，這些線段將移動機器人的起始節(jié)點、中間節(jié)點和目標節(jié)點相連。路徑被編碼成固定長度。圖1對移動機器人的工作空間和運行路徑進行了描述。

圖1　直角坐標法和序號法建立的柵格模型

路徑編碼策略的選擇對適應(yīng)度函數(shù)以及遺傳算子(尤其是交叉算子和變異算子)的設(shè)計具有重要影響。路徑編碼策略主要有實數(shù)編碼、二進制編碼、自適應(yīng)編碼和樹編碼等。下述討論中，將實數(shù)編碼中的序號法與坐標法結(jié)合使用[4]，采用序號法表示機器人運動路徑，因為這樣的表示簡單直觀，可以節(jié)約存儲空間，并且便于遺傳算子的操作。在評估路徑的適應(yīng)度時，則將序號轉(zhuǎn)換成坐標形式，因為坐標法更便于表示柵格的相對位置，更易于計算路徑長度和檢驗路徑可行性。

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

適應(yīng)度函數(shù)可以有效的評價每條路徑的優(yōu)劣，通常適應(yīng)度值的大小與路徑的優(yōu)劣成正比，它對遺傳算法的收斂性和穩(wěn)定性有著重要的影響。進行移動機器人路徑規(guī)劃的目的是使機器人以最短的時間順利到達目標點[5]。因此，在進行路徑規(guī)劃時，適應(yīng)度函數(shù)的設(shè)計應(yīng)該主要滿足兩個條件[7-10]：機器人運行軌跡長度最短及在行進過程中可以有效的避開障礙物。與障礙物不發(fā)生碰撞是移動機器人路徑規(guī)劃的基本條件，是機器人在工作空間內(nèi)安全行駛的必要條件。免碰撞要滿足兩個條件：第一，任意路徑點不能落在任何一個障礙物區(qū)域內(nèi)；第二，相鄰兩個路徑點的連線與障礙物不相交。

(1)任意路徑點(用pi表示)不能落在任何一個障礙物區(qū)域，用集合W表示障礙物的集合，則路徑點不落在障礙物區(qū)域內(nèi)的適應(yīng)度函數(shù)可表示為

(2)

式中，pi代表工作空間中路徑上的點，n為柵格數(shù)。公式(2)表明，路徑點不在障礙物區(qū)域內(nèi)時，適應(yīng)度為1，否則為0。

(2)設(shè)pipi+1為機器人相鄰兩個路徑點的連線，則其與各個障礙物區(qū)域沒有交點的適應(yīng)度函數(shù)為

(3)

由公式(1)、(2)可知，機器人在路徑規(guī)劃過程中，可有效避免碰撞的適應(yīng)度函數(shù)為

(4)

適應(yīng)度函數(shù)的選取對于遺傳算法來說至關(guān)重要，除了在運動過程中能夠有效避開障礙物，適應(yīng)度函數(shù)還要能夠快速計算每條路徑的長度。用公式(5)表示相鄰兩條路徑點的長度

(5)

公式(5)中，(xi,yi)表示機器人的當(dāng)前位置坐標，(xi-1,yi-1)則代表機器人前一位置的坐標。綜上，整條路徑的長度可以用公式(6)來計算：

(6)

因此，表示最短路徑的適應(yīng)度函數(shù)fit2為：

(7)

由公式(4)和公式(7)可知，用于表示移動機器人路徑規(guī)劃的最優(yōu)適應(yīng)度函數(shù)是：

(8)

公式(8)中，Cmax的取值與地圖的復(fù)雜程度以及起始點和目標點之間的直線距離有關(guān)，α為懲罰系數(shù)，把公式(8)作為移動機器人路徑規(guī)劃的適應(yīng)度函數(shù)，既可以有效避免碰撞又可以使得路徑最短。

2.3遺傳算子

2.3.1選擇算子

執(zhí)行選擇操作的主要目的是使得群體中適應(yīng)度大的個體被復(fù)制下來，去除適應(yīng)度小的個體，并且在這一過程中群體的規(guī)模保持不變。然后，將執(zhí)行選擇操作選出來的個體再進行交叉和變異操作從而產(chǎn)生新的后代。選擇策略是確保機器人以最佳適應(yīng)度存活下來的根本原因。本文采用輪盤賭和精英保留策略相結(jié)合的方法來執(zhí)行選擇操作[11-12]。

2.3.2交叉算子

交叉操作是遺傳算法中基因重新排列的基本機制，在遺傳算法中它被應(yīng)用于選擇操作之后。在進行遺傳操作的時候，交叉點的選擇是隨機的，可以采用單點交叉也可以采用多點交叉的方式。在兩個解決方案之間交換部分基因片段從而產(chǎn)生新的基因組合，進而創(chuàng)造出新的解決方案。本文采用單點交叉的方式執(zhí)行交叉操作[9]。分為兩種情況。

(1)共有節(jié)點處一點交叉：

共有節(jié)點處一點交叉是指兩個待交叉的個體存在相同的節(jié)點(不包括起始點和目標點)，并且兩個個體在該節(jié)點之前(或之后)的基因不同。則將此節(jié)點作為交叉節(jié)點進行交叉。舉一個例子來說明該交叉操作的過程。假設(shè)兩個待交叉的父代個體為V1和V2，其中，父代個體V1(0,2,52,53,93,99);父代個體V2(0,33,53,64,66,99)。

可以看出，兩個父代個體V1和V2中存在共有節(jié)點53，而且兩個父代個體在該節(jié)點之前和之后的基因均不相同。因此，可以采用共有節(jié)點一點交叉的方式進行交叉。交叉之后所得的子代個體為：

子代個體V1’(0,2,52,53,64,66,99)

子代個體V2’(0,33,53,93,99)

(2)潛在節(jié)點處一點交叉：

所謂潛在節(jié)點是指在一個待交叉的父代個體中出現(xiàn)的節(jié)點，在另一個待交叉的父代個體中沒有出現(xiàn)，但是另一父代個體中存在兩個相鄰節(jié)點的連線經(jīng)過此節(jié)點。只需要將其插入到另一個父代個體中連線能夠經(jīng)過此節(jié)點的相鄰節(jié)點之間，便可采用共有節(jié)點一點交叉的方法進行交叉。

假設(shè)父代個體V1和V2分別為：

父代個體V1(0,2,52,53,93,99)

父代個體V2(,0,33,63,66,99)。

可以看出，節(jié)點53在父代個體V1中出現(xiàn)，而沒有在父代個體V2中出現(xiàn)，但是父代個體V2中存在兩個相鄰節(jié)點(節(jié)點33和節(jié)點63)的連線經(jīng)過節(jié)點53，因此，節(jié)點53可以作為潛在節(jié)點進行交叉。首先，將節(jié)點53插入到父代個體V2中，此時父代個體V2變?yōu)?0,33,53,63,66,99)。然后，按照共有節(jié)點處一點交叉的方法進行交叉，得到的子代個體分別為：

子代個體V1’(0,2,52,53,63,66,99);

子代個體V2’(0,33,53,93,99)。

2.3.3變異算子

基因突變是一個過程，它是指應(yīng)用一些隨機的變化方式使得染色體上的位發(fā)生小的改變，從而產(chǎn)生新的基因片段。這一操作對維持種群的多樣性是非常必要的。本文對交叉后產(chǎn)生的子代個體基因按小概率pm擾動進行變異,通常取很小的值，一般為0.001～0.4，這里取0.01。

2.3.4插入算子

引入插入算子的作用是使自由柵格將間斷路徑轉(zhuǎn)化為連續(xù)路徑。判斷兩個相鄰序號的路徑點pk,pk+1是否連續(xù)，可用如下方法：

(9)

若Δ=1，則pk與pk+1連續(xù)，否則，不連續(xù)。如果不連續(xù)則按中值法插入候補點。

(10)

重復(fù)執(zhí)行上述插入過程，直至將間斷路徑轉(zhuǎn)化為連續(xù)路徑或因找不到新的候補插入點而舍棄該個體。

2.3.5刪除算子

增加刪除算子的目的是刪除同一路徑中出現(xiàn)的相同序號以及相同序號之間可能存在的冗余序號，以簡化機器人的行走路徑。

3　實驗結(jié)果及分析

3.1實驗結(jié)果

本部分證明了改進的遺傳算法在移動機器人路徑規(guī)劃問題上的實現(xiàn)。描述了實驗所需要的軟硬件環(huán)境。設(shè)定了遺傳進化過程中種群的各項參數(shù)，并對產(chǎn)生的實驗結(jié)果進行了分析。本文的實驗是在1.7 GHz，酷睿i5處理器的計算機平臺上，由MATLAB2012b 64Bit編制完成的。

在實驗過程中，種群的各項參數(shù)如下：種群規(guī)模M=60，交叉操作的概率pc=0.6，變異操作的概率為pm=0.01，最大進化代數(shù)T=100。移動機器人的工作空間由15×15的柵格地圖構(gòu)成。移動機器人的起始點和目標點分別用S和G表示。實驗結(jié)果如圖2和圖3所示，其中，實線是由遺傳算法計算出的最優(yōu)路徑。

從圖2和圖3能夠看出，改進的遺傳算法相比于傳統(tǒng)的遺傳算法能夠搜索到更短的最優(yōu)路徑。改進的遺傳算法產(chǎn)生最優(yōu)路徑的適應(yīng)度函數(shù)值和收斂代數(shù)分別為：F1=10.074，N1=21;傳統(tǒng)遺傳算法產(chǎn)生最優(yōu)路徑的適應(yīng)度值和收斂代數(shù)分別為：F2=10.068，N2=57。

圖2　改進遺傳算法實驗結(jié)果

圖3　傳統(tǒng)遺傳算法實驗結(jié)果

3.2算法對比分析

在與傳統(tǒng)遺傳算法的對比過程中，移動機器人的工作空間如圖2或圖3所示，在實驗的過程中，兩種算法的控制參數(shù)相同，包括種群規(guī)模的大小、發(fā)生交叉和變異的概率、最大遺傳代數(shù)等。圖4為兩種算法對比的實驗結(jié)果，從圖中可以看到，改進的遺傳算法能夠更快的收斂到全局最優(yōu)解，而且在收斂的過程中能夠有效克服傳統(tǒng)遺傳算法易于陷入局部最優(yōu)的問題。此外，還對路徑規(guī)劃的時間、所獲取的最短路徑的長度以及產(chǎn)生最優(yōu)路徑的比例進行了比較，結(jié)果如表1所示。從表中可以看到，改進遺傳算法比傳統(tǒng)遺傳算法所獲得的路徑更短，而且運行時間少于后者。此外，在獲得最優(yōu)路徑比例方面，改進遺傳算法遠遠高于傳統(tǒng)遺傳算法。當(dāng)移動機器人路徑規(guī)劃的環(huán)境變得復(fù)雜時，更能顯現(xiàn)改進遺傳算法的優(yōu)點。因此，所提出的改進遺傳算法在搜索效率及獲取最優(yōu)解方面都優(yōu)于傳統(tǒng)遺傳算法。

圖4　改進遺傳算法與傳統(tǒng)遺傳算法最優(yōu)適應(yīng)度和收斂代數(shù)比較

最短路徑長度搜索時間/ms最優(yōu)路徑比例/(%)改進遺傳算法20.970621795傳統(tǒng)遺傳算法25.071134562

4　結(jié)束語

本文提出了一種改進的遺傳算法，并采用該算法對移動機器人路徑規(guī)劃問題進行了研究。在存在障礙物的柵格環(huán)境中，使用改進的遺傳算法進行路徑規(guī)劃，并且獲得了最優(yōu)路徑。正如實驗部分所證明的那樣，改進的遺傳算法相比與傳統(tǒng)遺傳算法在路徑規(guī)劃方面具有明顯優(yōu)勢，具體表現(xiàn)在搜索的效率更高、規(guī)劃的最優(yōu)路徑更短。采用序號編碼的方法，縮短了染色體的長度，簡化了計算過程，提高了搜索效率。特殊的交叉算子的使用則利于尋找到最短的可行路徑。

[1] 張捍東，鄭睿，岑豫皖.移動機器人路徑規(guī)劃技術(shù)的現(xiàn)狀與展望[J].系統(tǒng)仿真學(xué)報，2005,17(2)：439-443.

[2] 朱大奇，顏明重.移動機器人路徑規(guī)劃技術(shù)綜述[J].控制與決策，2010,25(7)：962-967.

[3] 周蘭鳳，洪炳熔.用基于知識的遺傳算法實現(xiàn)移動機器人路徑規(guī)劃[J].電子學(xué)報，2006，34(5):911-914.

[4] 陳曦，譚冠政，江斌. 基于免疫遺傳算法的移動機器人實時最優(yōu)路徑規(guī)劃[J]. 中南大學(xué)學(xué)報(自然科學(xué)版)，2008,39(3)：577-583.

[5] Kala Rahul.Multi-robot path planning using co-evolutionary genetic programming[J].Expert Systems with Applications, 2012, 39(3): 3817-3831.

[6] 陳華華，杜歆，顧偉康.基于遺傳算法的靜態(tài)環(huán)境全局路徑規(guī)劃[J].浙江大學(xué)學(xué)報(理學(xué)版)，2005,32(1)：49-53,61.

[7] Hsu-Chih Huang, Ching-Chih Tsai.Global path planning for autonomous robot navigation using hybid metaheuristic GA-PSO algorithm[A].SICE Annual Conference 2011[C], 2011:1338-1343.

[8] 郝博，秦麗娟，姜明洋. 基于改進遺傳算法的移動機器人路徑規(guī)劃方法研究[J]. 計算機工程與科學(xué)，2010,32(7)：104-107.

[9] Hu Y R, Simon X.Yang, Li Z X.A knowledge based genetic algorithm for pathing in unstructured mobile robot environments[A].Proceedings of the 2004IEEE International Conference on Robotics and Biomimetics[C],2004:767-772.

[10] 唐國新，陳雄，袁楊. 基于改進遺傳算法的機器人路徑規(guī)劃[J].計算機工程與設(shè)計，2007,28(18)：4446-4449.

[11] 盧瑾.基于遺傳算法的移動機器人路徑規(guī)劃研究[D].杭州：浙江工業(yè)大學(xué)，2005.

[12] Masoud Samadi, Mohd Fauzi Othman.Global path planning for autonomous mobile robot using genetic algorithm[A].2013International Conference on Signal-Image Technology&Internet-Based Systems[C],2013:726-730.

Mobile Robot Path Planning Based on Improved Genetic Algorithm

Zhang Yi, Dai Encan, Luo Yuan

(National Engineering Research and Development Center for Information Accessibility, Chongqing University of Posts and Telecommunication, Chongqing400065, China)

In order to solve the problems of low search efficiency and easily falling into the local optimal solution in traditional genetic algorithm, an improved genetic algorithm is proposed in this paper. It adopts the simple one-dimensional code to replace the complex two-dimensional coding, which can save storage space. In the design of genetic operators, many operations such as crossover and mutation are redefined to avoid getting into the local optimum. Then the two fitness functions-collision-free path and the shortest distance- are fused into one for the following genetic optimization. In the case of the same population parameters, 100 trials are respectively developed with the method of improved genetic algorithm and traditional genetic algorithm. Among them, the improved genetic algorithm to search the optimal path gets to 95 times, and the shortest path is 20.970 6. Besides, the average searching time takes up 217 ms. While the number of traditional method to search for the optimal path reaches up to 62 times, the shortest path can be 25.071 1, and the average searching time needs 345 ms. So compared to the tests results referred above, the improved genetic algorithm is more efficient and can get a better solution than the traditional genetic algorithm.

genetic algorithm; mobile robot; path planning; crossover operator; mutation operator

2015-08-04；

2015-11-11。

國家自然科學(xué)基金資助項目(51075420)。

張毅(1966-)，男，博士，教授，主要從事機器人導(dǎo)航技術(shù)、數(shù)據(jù)融合、信息無障礙技術(shù)方向的研究。

羅元(1972-)，女，博士，教授，主要從事信號與信息處理、數(shù)字圖像處理方向的研究。

1671-4598(2016)01-0313-04

10.16526/j.cnki.11-4762/tp.2016.01.087

TP242

A