張　毅，代恩燦，羅　元

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

?

基于改進(jìn)遺傳算法的移動(dòng)機(jī)器人路徑規(guī)劃

張毅，代恩燦，羅元

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

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

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

0　引言

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

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

1　遺傳算法的基本原理

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

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

Step1:由N個(gè)隨機(jī)生成的個(gè)體組成初始種群。

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

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

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

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

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

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

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

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

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

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

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

(1)

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

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

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

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

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

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

機(jī)器人路徑由多條線段組成，這些線段將移動(dòng)機(jī)器人的起始節(jié)點(diǎn)、中間節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)相連。路徑被編碼成固定長(zhǎng)度。圖1對(duì)移動(dòng)機(jī)器人的工作空間和運(yùn)行路徑進(jìn)行了描述。

圖1　直角坐標(biāo)法和序號(hào)法建立的柵格模型

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

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

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

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

(2)

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

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

(3)

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

(4)

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

(5)

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

(6)

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

(7)

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

(8)

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

2.3遺傳算子

2.3.1選擇算子

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

2.3.2交叉算子

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3.3變異算子

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

2.3.4插入算子

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

(9)

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

(10)

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

2.3.5刪除算子

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

3　實(shí)驗(yàn)結(jié)果及分析

3.1實(shí)驗(yàn)結(jié)果

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

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

從圖2和圖3能夠看出，改進(jìn)的遺傳算法相比于傳統(tǒng)的遺傳算法能夠搜索到更短的最優(yōu)路徑。改進(jìn)的遺傳算法產(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　改進(jìn)遺傳算法實(shí)驗(yàn)結(jié)果

圖3　傳統(tǒng)遺傳算法實(shí)驗(yàn)結(jié)果

3.2算法對(duì)比分析

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

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

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

4　結(jié)束語(yǔ)

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

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

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

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

[4] 陳曦，譚冠政，江斌. 基于免疫遺傳算法的移動(dòng)機(jī)器人實(shí)時(shí)最優(yōu)路徑規(guī)劃[J]. 中南大學(xué)學(xué)報(bào)(自然科學(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é)報(bào)(理學(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] 郝博，秦麗娟，姜明洋. 基于改進(jìn)遺傳算法的移動(dòng)機(jī)器人路徑規(guī)劃方法研究[J]. 計(jì)算機(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ìn)遺傳算法的機(jī)器人路徑規(guī)劃[J].計(jì)算機(jī)工程與設(shè)計(jì)，2007,28(18)：4446-4449.

[11] 盧瑾.基于遺傳算法的移動(dòng)機(jī)器人路徑規(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。

國(guó)家自然科學(xué)基金資助項(xiàng)目(51075420)。

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

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

1671-4598(2016)01-0313-04

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

TP242

A