雷艷敏，王 帥

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

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

雷艷敏，王 帥

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

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

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

0 引言

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

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

遺傳算法首先要隨機生成初始種群，然后用事先設(shè)定的評價標準適應(yīng)度函數(shù)去篩選出優(yōu)秀個體，之后優(yōu)秀個體通過交叉、變異形成新的種群去優(yōu)化目標函數(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īng)過的點或路徑在障礙物內(nèi)或邊緣，防止陷入局部最優(yōu)解。

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

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

1.2.1 最短路徑

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

(1)

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

(2)

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

(3)

1.2.2 安全性能

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

(4)

1.2.3 平滑度

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

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

(5)

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

(6)

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

(7)

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

sumi=a2+b2-c2。

(8)

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

(9)

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

(10)

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

fit=w1fit1+w2fit2+w3fit3。

(11)

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

2 仿真實驗

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

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

首先，建立環(huán)境模型，邊界X軸Y軸都為20cm；設(shè)置障礙物個數(shù)為m=6；設(shè)定起始點坐標[0,0],目標點坐標[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時，最優(yōu)、平均函數(shù)值變化趨勢如圖1所示。從圖中可以看出，在不斷的迭代過程中，最優(yōu)適應(yīng)度函數(shù)值變化趨勢趨于平穩(wěn)，而平均適應(yīng)度函數(shù)值始終保持不變。隨著迭代次數(shù)的不斷增加，最優(yōu)適應(yīng)度函數(shù)值不斷地接近平均適應(yīng)度函數(shù)值。當最優(yōu)適應(yīng)度函數(shù)值和平均適應(yīng)度函數(shù)值相接近時，才能規(guī)劃出理想中的路徑。

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

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

2.2.2 路徑規(guī)劃實驗結(jié)果

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

(1)fit=fit1

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

(2)fit=fit1+fit2

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

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

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

(3)fit=fit1+fit2+fit3

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

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

(4)fit=w1fit1+w2fit2+w3fit3

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

4 結(jié)論

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

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

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

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

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

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

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

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

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

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

責任編輯：程艷艷

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-)，女(滿族)，黑龍江五常人，副教授，博士，主要從事機器人智能控制及自動化控制方面的研究。

TP24

A

1009-3907(2017)04-0001-03