楊 勇

（西安航空學院，西安710077）

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

楊 勇

（西安航空學院，西安710077）

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

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

1 引 言

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

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

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

圖1 環(huán)境地圖

3 遺傳算法

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

3.1 染色體表示

用柵格序號表示一條染色體，采用基于柵格序號的、不定長十進制編碼機制，以提高算法效率和靈活性［2］。

3.2 適應度函數(shù)

適應度函數(shù)衡量有兩個標準：躲避障礙物和行進路徑最短［3］。設計適應度函數(shù)如下：

圖2 遺傳算法框圖

3.3 遺傳操作

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

1）復制算子：采用輪盤賭（roulette wheel）方式，對種群進行選擇，個體選擇概率計算如下：

2）交叉算子：通過引入自適應交叉概率來對種群的染色體交叉進行調節(jié)。對于高于種群平均適應值的個體，采取較低的交叉概率；而低于平均值的個體則交叉概率的取值較高［4］。具體計算方法如下：

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

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

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

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

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

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

3.4 遺傳操作的改進

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

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

2）設置了兩個變異算子p1，p2，其中p1表示在對種群進行遺傳操作之前首先進行變異操作，取值為0.5；p2通過自適應進行調節(jié)，具體算法如下：

4 仿真結果

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

表1 環(huán)境1仿真運行結果

表2 環(huán)境2仿真運行結果

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

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

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

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

5 結束語

結合傳統(tǒng)的柵格法和遺傳算法進行移動機器人路徑規(guī)劃，并對遺傳算法的操作算子進行了改進。通過對兩種不同環(huá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］ 朱大奇，顏明重.移動機器人路徑規(guī)劃技術綜述［J］.控制與決策，2010，6（5）：34－36.

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

［4］ 鄧志燕，陳熾坤.基于改進遺傳算法的移動機器人路徑規(guī)劃研究［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］ 李擎，馮金玲.自適應遺傳算法在移動機器人路徑規(guī)劃中的應用［J］.北京科技大學學報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

陜西省自然科學基金資助項目（2011K09－16）

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

2014－04－22