基于節(jié)點(diǎn)擴(kuò)張的遺傳算法在機(jī)器人路徑規(guī)劃中的應(yīng)用

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

關(guān)鍵詞：機(jī)器人；遺傳算法；路徑規(guī)劃；節(jié)點(diǎn)擴(kuò)張

中圖分類(lèi)號(hào)：TP18 文獻(xiàn)標(biāo)識(shí)碼：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ī)劃是移動(dòng)機(jī)器人導(dǎo)航的最基本環(huán)節(jié)之一，它是某一個(gè)或某一些優(yōu)化準(zhǔn)則（如工作代價(jià)最小、行走路線最短等），在其工作環(huán)境中找出一條從起點(diǎn)到終點(diǎn)的能避開(kāi)障礙物的最優(yōu)行走路線[1]。近年來(lái)，相對(duì)于傳統(tǒng)的C-空間法、人工勢(shì)場(chǎng)法、柵格法等，遺傳算法以其易于編程和應(yīng)用的簡(jiǎn)單性，適合于任何形式的搜索空間的魯棒性，基于并行運(yùn)算的有效性，運(yùn)用全局信息的全局優(yōu)化性，已經(jīng)被廣泛應(yīng)用于移動(dòng)機(jī)器人路徑規(guī)劃的研究中[2，3]。

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

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文