基于節(jié)點擴張的遺傳算法在機器人路徑規(guī)劃中的應用

摘要：將一種新型的遺傳算法應用于移動機器人路徑規(guī)劃。提出了基于障礙節(jié)點擴張法的無障礙連通路徑初始種群的產生算法，以及基于待變異節(jié)點擴張的變異操作算法，同時在交叉、變異操作之后進行局部優(yōu)化，簡化了編程，提高了適用性。仿真結果表明同普通的 算法相比較，該路徑規(guī)劃算法具有尋優(yōu)質量高、規(guī)劃路徑更為平滑的特點。

關鍵詞：機器人；遺傳算法；路徑規(guī)劃；節(jié)點擴張

中圖分類號：TP18 文獻標識碼：A

Application of genetic algorithm with node expanding method to path planning of robots

LI Guang，PENG Li-hui

( Hunan University of Technology， Zhuzhou Hunan 412008，China)

Abstract：A new genetic algorithm was applied to path planning of robots. A generating approach for obstacle free and continuous paths based on obstacle-nodes expending strategy was developed for initial population formation， a pro-mutating nodes expending methodalso used for mutation operation， and local optimum program was also introduced to crossover and mutation operations as well. The simulation results demonstrate that， comparing with algorithm， the proposed algorithm has following advantages such as higher searcher quality， more smooth path， simplified programming method and better adaptability compared to the basic algorithm.

Keywords: robots; genetic algorithm; path planning; node expanding

1 引言

路徑規(guī)劃是移動機器人導航的最基本環(huán)節(jié)之一，它是某一個或某一些優(yōu)化準則（如工作代價最小、行走路線最短等），在其工作環(huán)境中找出一條從起點到終點的能避開障礙物的最優(yōu)行走路線[1]。近年來，相對于傳統(tǒng)的C-空間法、人工勢場法、柵格法等，遺傳算法以其易于編程和應用的簡單性，適合于任何形式的搜索空間的魯棒性，基于并行運算的有效性，運用全局信息的全局優(yōu)化性，已經被廣泛應用于移動機器人路徑規(guī)劃的研究中[2，3]。

本文對現有的基于遺傳算法的路徑規(guī)劃研究，在初始種群生成及變異操作算法中，分別采用了基于障礙節(jié)點擴張的無障礙連通路徑生成法，和基于待變異節(jié)點擴張的變異操作算法，同時在交叉和變異操作之后進行局部尋優(yōu)，在使得編程更為直接、更為簡單，通用性也更強。

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文