雷艷敏，王 帥

(長春大學(xué) 電子信息工程學(xué)院，長春 130022)

基于遺傳算法的機(jī)器人路徑規(guī)劃的仿真研究

雷艷敏，王 帥

(長春大學(xué) 電子信息工程學(xué)院，長春 130022)

鑒于其他傳統(tǒng)機(jī)器人路徑規(guī)劃算法(如柵格法、人工勢場法、A*算法等)存在搜索效率低、易于陷入局部最優(yōu)解的問題，提出一種新的遺傳算法。本文中將最短路徑、避免碰撞(安全性能)和平滑度三者相結(jié)合作為新的適應(yīng)度函數(shù)進(jìn)行遺傳優(yōu)化，并給三個(gè)要素分配一定的權(quán)值。仿真結(jié)果表明：該算法搜索效率更高且能獲得更好的路徑規(guī)劃結(jié)果。

遺傳算法；適應(yīng)度函數(shù)；路徑規(guī)劃

0 引言

在機(jī)器人研究領(lǐng)域中，路徑規(guī)劃是至關(guān)重要的。路徑規(guī)劃就是在有障礙物的環(huán)境中，按照某一性能指標(biāo)(行走時(shí)間最短、路徑最短或能量消耗最少等)，為移動(dòng)機(jī)器人規(guī)劃出一條從起始點(diǎn)到目標(biāo)點(diǎn)的最優(yōu)或者近似最優(yōu)的無碰撞路徑[1]。機(jī)器人路徑規(guī)劃分為兩種：一種是靜態(tài)環(huán)境下的全局路徑規(guī)劃；另一種是動(dòng)態(tài)環(huán)境下的局部路徑規(guī)劃。

機(jī)器人的路徑規(guī)劃有許多方法：如A*算法[2]、柵格法[3]、滾動(dòng)窗口規(guī)劃方法[4]、人工勢場法[5]、神經(jīng)網(wǎng)絡(luò)法[6]和遺傳算法等。每一種算法都有各自的優(yōu)缺點(diǎn)，缺點(diǎn)主要有計(jì)算量大、搜索效率低、易陷入局部最優(yōu)解等。為了提高算法的性能，對算法進(jìn)行改進(jìn)，主要包括算法本身的改進(jìn)，或者把幾種算法進(jìn)行組合[7]。其中，遺傳算法是一種全局尋優(yōu)算法。由于具有魯棒性、適應(yīng)能力強(qiáng)的優(yōu)點(diǎn)而得到了廣泛的應(yīng)用。為了提高遺傳算法進(jìn)行路徑規(guī)劃的安全性，并使規(guī)劃的路徑最短，本文提出一種新的適應(yīng)度函數(shù)，該函數(shù)包含了最短路徑、安全性和平滑度三個(gè)要素。最后通過仿真實(shí)驗(yàn)證明了該算法的可行性和有效性。

遺傳算法首先要隨機(jī)生成初始種群，然后用事先設(shè)定的評價(jià)標(biāo)準(zhǔn)適應(yīng)度函數(shù)去篩選出優(yōu)秀個(gè)體，之后優(yōu)秀個(gè)體通過交叉、變異形成新的種群去優(yōu)化目標(biāo)函數(shù)，經(jīng)過不斷的迭代直到滿足設(shè)定的算法終止條件為止，最終得到最優(yōu)解[8]。

1 基于遺傳算法的路徑規(guī)劃

1.1 環(huán)境建模

本文設(shè)定環(huán)境模型為二維結(jié)構(gòu)化空間，障礙物在環(huán)境中的位置為Oi(xobs,i,yobs,i)，將環(huán)境中設(shè)定的障礙物引入到初始種群的生成中。設(shè)置了檢查裝置，避免機(jī)器人經(jīng)過的點(diǎn)或路徑在障礙物內(nèi)或邊緣，防止陷入局部最優(yōu)解。

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

適應(yīng)度函數(shù)能有效地評價(jià)每條路徑的優(yōu)劣。適應(yīng)度值的大小與路徑的優(yōu)劣成正比，因此，對遺傳算法的收斂性和穩(wěn)定性有著重要影響[9]。機(jī)器人路徑規(guī)劃的目的是使機(jī)器人從初始點(diǎn)到達(dá)目標(biāo)點(diǎn)的運(yùn)行路徑最短并在行走的過程中無碰撞。因此，路徑規(guī)劃適應(yīng)度函數(shù)的設(shè)計(jì)要滿足三要素：機(jī)器人運(yùn)行軌跡最短、運(yùn)行過程中避開障礙物以及確保路徑的平滑度。不與障礙物發(fā)生碰撞，是機(jī)器人在工作空間內(nèi)行走的必要和基本條件。避免碰撞包括：任意路徑點(diǎn)不能落在任何一個(gè)障礙物區(qū)域內(nèi)及相鄰兩個(gè)路徑點(diǎn)的連線與障礙物不相交。

1.2.1 最短路徑

適應(yīng)度函數(shù)的選取對于遺傳算法來說很重要，適應(yīng)度函數(shù)要能夠快速計(jì)算每條路徑長度。用公式(1)表示相鄰兩個(gè)路徑點(diǎn)的長度：

(1)

公式(1) 中，(xi,yi)表示機(jī)器人的當(dāng)前位置坐標(biāo)，(xi-1,yi-1)表示機(jī)器人前一位置的坐標(biāo)。則整條路徑的長度可用公式(2)來計(jì)算：

(2)

公式(2)中，n為機(jī)器人的步數(shù)，因此，表示最短路徑的適應(yīng)度函數(shù)fit1為：

(3)

1.2.2 安全性能

對于遺傳算法適應(yīng)度函數(shù)的選取，除了要保證路徑最短外，還要確保規(guī)劃的機(jī)器人路徑能安全行走(即無碰撞)，則安全性能適應(yīng)度函數(shù)fit2為：

(4)

1.2.3 平滑度

機(jī)器人路徑規(guī)劃不僅要考慮到路徑最短、避免碰撞，還要考慮到平滑度。本文利用余弦定理來解決平滑度問題，假設(shè)每個(gè)種群中每個(gè)線段的直線參數(shù)a、b、c(函數(shù)ax+by+c=0)。

公式(5)表示計(jì)算直線參數(shù)a：

(5)

公式(6)表示計(jì)算直線參數(shù)b：

(6)

公式(7)表示計(jì)算直線參數(shù)c：

(7)

公式(8)表示計(jì)算和值：

sumi=a2+b2-c2。

(8)

公式(9)表示計(jì)算總值：

(9)

則表示平滑度的適應(yīng)度函數(shù)fit3為：

(10)

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

fit=w1fit1+w2fit2+w3fit3。

(11)

其中w1、w2和w3分別為最短路徑、安全性能和平滑度三個(gè)要素的加權(quán)系數(shù)。

2 仿真實(shí)驗(yàn)

Matlab是MathWorks公司的產(chǎn)品，是一個(gè)功能強(qiáng)大的數(shù)學(xué)軟件，其優(yōu)秀的數(shù)值計(jì)算能力使其在工業(yè)界和學(xué)術(shù)界的使用率非常高，所以，利用Matlab來編寫遺傳算法程序有著巨大優(yōu)勢。

2.1 設(shè)定初始數(shù)據(jù)

首先，建立環(huán)境模型，邊界X軸Y軸都為20cm；設(shè)置障礙物個(gè)數(shù)為m=6；設(shè)定起始點(diǎn)坐標(biāo)[0,0],目標(biāo)點(diǎn)坐標(biāo)[20，20]；設(shè)定遺傳算法種群規(guī)模為100；染色體長度為30；最大迭代次數(shù)為20代；種群變異率為0.01；種群交叉率為0.9。

2.2 仿真結(jié)果

2.2.1 最優(yōu)適應(yīng)度函數(shù)和平均適應(yīng)度函數(shù)值變化趨勢對比

在變異率pm=0.01，交叉率pc=0.9時(shí)，最優(yōu)、平均函數(shù)值變化趨勢如圖1所示。從圖中可以看出，在不斷的迭代過程中，最優(yōu)適應(yīng)度函數(shù)值變化趨勢趨于平穩(wěn)，而平均適應(yīng)度函數(shù)值始終保持不變。隨著迭代次數(shù)的不斷增加，最優(yōu)適應(yīng)度函數(shù)值不斷地接近平均適應(yīng)度函數(shù)值。當(dāng)最優(yōu)適應(yīng)度函數(shù)值和平均適應(yīng)度函數(shù)值相接近時(shí)，才能規(guī)劃出理想中的路徑。

圖1 最優(yōu)和平均適應(yīng)度函數(shù)值變化趨勢

圖2 只考慮最短路徑的路徑規(guī)劃結(jié)果

2.2.2 路徑規(guī)劃實(shí)驗(yàn)結(jié)果

為了分析遺傳算法中不同的適應(yīng)度函數(shù)值對路徑規(guī)劃結(jié)果的影響，下面將分別對以下幾種情況進(jìn)行仿真。

(1)fit=fit1

fit=fit1，即只考慮機(jī)器人最短距離情況下路徑規(guī)劃，仿真結(jié)果如圖2所示。從圖中可以看出，只考慮最短距離的情況下，得到的并非是最優(yōu)解，且如圖中橢圓所標(biāo)記的路徑都無限地接近障礙物。因此，適應(yīng)度函數(shù)只考慮路徑最短是不全面的。

(2)fit=fit1+fit2

fit=fit1+fit2，即同時(shí)考慮最短距離與安全性能時(shí)的路徑規(guī)劃，仿真結(jié)果如圖3所示。從圖中可以看出，考慮到路徑的安全性問題后，機(jī)器人在行進(jìn)過程中明顯避免了與障礙物發(fā)生碰撞的可能，但路徑平滑度太差了。因此，在機(jī)器人路徑規(guī)劃中考慮最短距離與安全性能也是不全面的。

圖3 考慮最短路徑和安全性的路徑規(guī)劃結(jié)果

圖4 考慮最短路徑、安全性和平滑度的路徑規(guī)劃結(jié)果

(3)fit=fit1+fit2+fit3

fit=fit1+fit2+fit3，即綜合考慮機(jī)器人最短距離、安全性能和平滑度情況下的路徑規(guī)劃，仿真結(jié)果如圖4所示。從圖中可以看出，綜合考慮最短距離、安全性能和平滑度三個(gè)要素后基本上能夠得到最優(yōu)解，但規(guī)劃出的路徑并非完美。

圖5 改變適應(yīng)度函數(shù)值時(shí)的路徑規(guī)劃結(jié)果

(4)fit=w1fit1+w2fit2+w3fit3

fit=w1fit1+w2fit2+w3fit3，即給最短路徑、安全性和平滑度分配了一定的權(quán)值，使w1+w2+w3=1，加入權(quán)系數(shù)后可以得到完美的機(jī)器人路徑，經(jīng)過不斷地實(shí)驗(yàn)驗(yàn)證得到當(dāng)w1=0.4，w2=0.4，w3=0.2時(shí)規(guī)劃的路徑結(jié)果最好。

4 結(jié)論

本文在機(jī)器人路徑規(guī)劃問題的研究中，提出一種新的遺傳算法。將最短路徑、安全性能和平滑度三要素加入到適應(yīng)度函數(shù)中，在存在障礙物的靜態(tài)環(huán)境中，用該方法獲得了最優(yōu)路徑。經(jīng)過實(shí)驗(yàn)證明，通過多次迭代，最優(yōu)適應(yīng)度函數(shù)值變化趨于穩(wěn)定，而且最優(yōu)適應(yīng)度函數(shù)值變化越小，尋找到的路徑就越平滑。在適應(yīng)度函數(shù)中加入權(quán)系數(shù)后，能獲得更好的規(guī)劃路徑。但是，本文中適應(yīng)度函數(shù)值中的權(quán)值是人為進(jìn)行設(shè)置的，下一步將對權(quán)值的自尋優(yōu)確定進(jìn)行研究。

[1] 張毅,代恩燦,羅元. 基于改進(jìn)遺傳算法的移動(dòng)機(jī)器人路徑規(guī)劃[J]. 計(jì)算機(jī)測量與控制,2016(1):313-316.

[2] 顧新艷,金世俊. 基于A*算法的移動(dòng)機(jī)器人路徑規(guī)劃[J]. 科技信息(科學(xué)教研),2007(34):36-37+79.

[3] 王娟娟,曹凱. 基于柵格法的機(jī)器人路徑規(guī)劃[J]. 農(nóng)業(yè)裝備與車輛工程,2009(4):14-17.

[4] 孫斌,韓大鵬,韋慶. 基于滾動(dòng)窗口算法的機(jī)器人路徑規(guī)劃應(yīng)用研究[J]. 計(jì)算機(jī)仿真,2006(6):159-162.

[5] 趙榮齊. 基于人工勢場法的機(jī)器人路徑規(guī)劃研究[D].濟(jì)南：山東大學(xué),2008.

[6] 黃磊. 基于神經(jīng)網(wǎng)絡(luò)的移動(dòng)機(jī)器人路徑規(guī)劃研究[D].武漢：武漢理工大學(xué),2008.

[7] 雷艷敏，馮志彬. 改進(jìn)的勢場柵格法在機(jī)器人路徑規(guī)劃中的應(yīng)用[J]. 長春大學(xué)學(xué)報(bào)，2009,19(1)：38-42.

[8] 鞏敦衛(wèi)，孫曉燕.協(xié)同進(jìn)化遺傳算法理論及應(yīng)用[M].北京：科學(xué)出版社，2009.

[9] 石鐵峰. 改進(jìn)遺傳算法在移動(dòng)機(jī)器人路徑規(guī)劃中的應(yīng)用[J]. 計(jì)算機(jī)仿真,2011(4):193-195+303.

責(zé)任編輯：程艷艷

SimulationStudyofRobotPathPlanningBasedonGeneticAlgorithm

LEIYanmin，WANGShuai

(CollegeofElectronicInformationEngineering,ChangchunUniversity,Changchun130022，Chine)

In view of the problems in other traditional robot path planning algorithms (such as grid method, artificial potential field method and A* algorithm etc.), including that the search efficiency is low and it is easy to fall into local optimal solution, this paper presents a new genetic algorithm, which makes a genetic optimization by combining the shortest path, avoidance of collision (safety performance) and smoothness as a new fitness function, and allocates a certain weight for the three elements. Simulation results show that the proposed algorithm is more efficient and can obtain better path planning results.

genetic algorithm; fitness function; path planning

2017-02-10

雷艷敏(1976-)，女(滿族)，黑龍江五常人，副教授，博士，主要從事機(jī)器人智能控制及自動(dòng)化控制方面的研究。

TP24

A

1009-3907(2017)04-0001-03