楊 勇

（西安航空學(xué)院，西安710077）

基于混合算法的移動(dòng)機(jī)器人路徑規(guī)劃研究?

楊 勇

（西安航空學(xué)院，西安710077）

路徑規(guī)劃技術(shù)是移動(dòng)機(jī)器人導(dǎo)航技術(shù)的重要組成部分。針對(duì)靜態(tài)已知環(huán)境的移動(dòng)機(jī)器人進(jìn)行路徑規(guī)劃，結(jié)合柵格法和遺傳算法，并對(duì)傳統(tǒng)的遺傳算法進(jìn)行改進(jìn)，建立兩種不同的環(huán)境，通過(guò)仿真實(shí)驗(yàn)顯示其改進(jìn)后的優(yōu)越性。

移動(dòng)機(jī)器人；路徑規(guī)劃；柵格法；遺傳算法

1 引 言

路徑規(guī)劃技術(shù)是移動(dòng)機(jī)器人導(dǎo)航技術(shù)的重要組成部分，也是當(dāng)下研究的重要課題之一。常用的路徑規(guī)劃方法有可視圖法、柵格法、神經(jīng)網(wǎng)絡(luò)法和遺傳算法等，并且各有利弊［1］。將柵格法和遺傳算法進(jìn)行結(jié)合，并對(duì)遺傳算法進(jìn)行改進(jìn)，來(lái)研究移動(dòng)機(jī)器人處于靜態(tài)環(huán)境下二維平面空間的路徑規(guī)劃。

2 柵格法建立環(huán)境信息

設(shè)計(jì)了兩種不同環(huán)境，進(jìn)行仿真對(duì)比，如圖1所示。

圖1 環(huán)境地圖

3 遺傳算法

遺傳算法框圖如圖2所示。

3.1 染色體表示

用柵格序號(hào)表示一條染色體，采用基于柵格序號(hào)的、不定長(zhǎng)十進(jìn)制編碼機(jī)制，以提高算法效率和靈活性［2］。

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

適應(yīng)度函數(shù)衡量有兩個(gè)標(biāo)準(zhǔn)：躲避障礙物和行進(jìn)路徑最短［3］。設(shè)計(jì)適應(yīng)度函數(shù)如下：

圖2 遺傳算法框圖

3.3 遺傳操作

使用了復(fù)制、交叉、變異、插入、優(yōu)化這五種遺傳操作算子。

1）復(fù)制算子：采用輪盤賭（roulette wheel）方式，對(duì)種群進(jìn)行選擇，個(gè)體選擇概率計(jì)算如下：

2）交叉算子：通過(guò)引入自適應(yīng)交叉概率來(lái)對(duì)種群的染色體交叉進(jìn)行調(diào)節(jié)。對(duì)于高于種群平均適應(yīng)值的個(gè)體，采取較低的交叉概率；而低于平均值的個(gè)體則交叉概率的取值較高［4］。具體計(jì)算方法如下：

設(shè)種群中個(gè)體數(shù)目為s，個(gè)體的交叉概率為：

3）變異算子：變異概率通常取值很小，一般取0.0001～0.1。常用的有均勻性變異、非一致性變異和自適應(yīng)變異這三種方法。

4）插入算子：執(zhí)行變異操作可能產(chǎn)生間斷路徑，因此提出一種插入算子，使路徑出現(xiàn)間斷時(shí)，通過(guò)使用自由柵格的辦法使其轉(zhuǎn)變成連續(xù)路徑。首先通過(guò)以下辦法判斷路徑是否連續(xù)：

其中，xk，yk，xk＋1，yk＋1分別為該柵格對(duì)應(yīng)的直角坐標(biāo)；max表示取最大值；abs表示取絕對(duì)值操作。當(dāng)D＝1時(shí)，則該路徑為連續(xù)路徑，否則為間斷路徑。當(dāng)路徑間斷時(shí)，按照下式計(jì)算：

若pk為自由柵格，可直接執(zhí)行插入算子；若pk存在障礙物，則需選擇一個(gè)與其距離最近的自由柵格，作為替代插入點(diǎn)。如果沒(méi)有新的替代插入點(diǎn)，則舍去該個(gè)體，進(jìn)行新的插入計(jì)算。

5）優(yōu)化算子：進(jìn)行機(jī)器人路徑規(guī)劃的時(shí)候，可能在遺傳操作過(guò)程中會(huì)出現(xiàn)子代中最優(yōu)個(gè)體的適應(yīng)度低于父代中最優(yōu)個(gè)體適應(yīng)度的情況［5］。為了防止丟失優(yōu)良的父代個(gè)體，采用了保留最優(yōu)個(gè)體的方法，即將父代和子代種群中個(gè)體適應(yīng)度函數(shù)值進(jìn)行比較，然后將最優(yōu)個(gè)體保存的辦法。

3.4 遺傳操作的改進(jìn)

為了防止遺傳算法過(guò)程中出現(xiàn)早熟現(xiàn)象而陷入局部最優(yōu)解，提出了一種改進(jìn)方法－雙層變異法，具體如下：

1）將父代和子代種群進(jìn)行融合，形成新的種群［6］。

2）設(shè)置了兩個(gè)變異算子p1，p2，其中p1表示在對(duì)種群進(jìn)行遺傳操作之前首先進(jìn)行變異操作，取值為0.5；p2通過(guò)自適應(yīng)進(jìn)行調(diào)節(jié)，具體算法如下：

4 仿真結(jié)果

對(duì)兩種環(huán)境分別進(jìn)行仿真，具體仿真結(jié)果如表1和表2所示。

表1 環(huán)境1仿真運(yùn)行結(jié)果

表2 環(huán)境2仿真運(yùn)行結(jié)果

表中對(duì)改進(jìn)前后的兩種方法分別進(jìn)行對(duì)比，可以看出改進(jìn)后的遺傳算法運(yùn)行時(shí)間短并且行進(jìn)路徑短，體現(xiàn)出其優(yōu)越性，如圖3和圖4所示。

圖3 環(huán)境1和2仿真圖

圖4 環(huán)境1和2迭代過(guò)程圖

可以看出，相比之下，兩種算法對(duì)于小規(guī)模種群的仿真運(yùn)行結(jié)果沒(méi)有巨大差異，但隨著種群規(guī)模的增大，改進(jìn)后的算法具有明顯優(yōu)越性。

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

結(jié)合傳統(tǒng)的柵格法和遺傳算法進(jìn)行移動(dòng)機(jī)器人路徑規(guī)劃，并對(duì)遺傳算法的操作算子進(jìn)行了改進(jìn)。通過(guò)對(duì)兩種不同環(huán)境的仿真實(shí)驗(yàn)，顯示出其優(yōu)越性。

［1］ D TamilselvI，Sr.Od.Lecturer.Dynamic Programming Agent for Mobile Robot Navigation with Moving Obstacles［J］.lAMA 2009，7（21）：256－260.

［2］ 朱大奇，顏明重.移動(dòng)機(jī)器人路徑規(guī)劃技術(shù)綜述［J］.控制與決策，2010，6（5）：34－36.

［3］ 周明，孫樹(shù)棟.遺傳算法原理及應(yīng)用［M］.北京：國(guó)防工業(yè)出版社，1999.

［4］ 鄧志燕，陳熾坤.基于改進(jìn)遺傳算法的移動(dòng)機(jī)器人路徑規(guī)劃研究［J］.機(jī)械設(shè)計(jì)與制造，2010，10（31）：221－225.

［5］ Clément Pêtrès，Yan Pailhas.Path Planning for Autonomous Underwater Vehicles［J］.IEEE Transaction on Robotics，2007，4（23）：41－45.

［6］ 李擎，馮金玲.自適應(yīng)遺傳算法在移動(dòng)機(jī)器人路徑規(guī)劃中的應(yīng)用［J］.北京科技大學(xué)學(xué)報(bào)2008，10（4）：121－124.

Research on Path Planning of Mobile Robot Based on Hybrid Algorithm

Yang Yong
（Xi’an Aeronautical University，Xi’an 710077，China）

The path planning technology is an important part of the mobile robot navigation technology.The mobile robot path planning in the static known environment，combined with the grid method and traditional genetic algorithm，is improved in the paper.Two different environments are set up，and simulation test results show that it has superiority after being improved.

Mobile robot；Path planning；Grid method；Genetic algorithm

10.3969/j.issn.1002－2279.2015.01.013

TP393

A

1002－2279（2015）01－0044－03

陜西省自然科學(xué)基金資助項(xiàng)目（2011K09－16）

楊勇（1964－），男，西安人，教授，碩士研究生，主研方向：電力電子自動(dòng)化和系統(tǒng)控制仿真。

2014－04－22