基于融合算法的移動機器人路徑規(guī)劃技術(shù)

魏先勇,馬 黎

(商丘職業(yè)技術(shù)學(xué)院,河南 商丘 476000)

基于融合算法的移動機器人路徑規(guī)劃技術(shù)

魏先勇,馬 黎

(商丘職業(yè)技術(shù)學(xué)院,河南 商丘 476000)

為了解決障礙物附近目標(biāo)不可到達(dá)目的地問題,提出了一種融合算法用于移動機器人路徑規(guī)劃. 融合算法對人工勢場進行了改進,構(gòu)造了新斥力勢場函數(shù),引入了指數(shù)因子, 平衡了障礙物的斥力,從而消除了奇異值點,使機器人到達(dá)了目標(biāo)點. 然后利用量子遺傳算法對最優(yōu)或次優(yōu)個體進行選擇,為最優(yōu)或次優(yōu)個體進入下一代移動機器人提供了保障,提高了安全性、實現(xiàn)了路徑的優(yōu)化. 仿真結(jié)果表明,融合算法能有效地提高路徑規(guī)劃的性能.

勢場法; 路徑規(guī)劃; 移動機器人; 量子遺傳算法

移動機器人路徑規(guī)劃技術(shù)是人工智能學(xué)和機器人相結(jié)合的產(chǎn)物，而移動機器人路徑規(guī)劃技術(shù)是一種帶約束條件比較復(fù)雜的優(yōu)化問題[1]110-120. 國內(nèi)外許多著名的學(xué)者都在這方面進行過深入的研究, 提出了許多合理有效的方法, 比如StentzA的D*算法、遺傳算法、滾動路徑規(guī)劃法、人工勢場法等[2]90-98. Ko N Y等人[3]1296-1303提出了一種改進的人工勢場法,對斥力勢函數(shù)進行改造,引入了障礙物的速度參量, 取得了良好的效果.但是,該算法的兩個假設(shè)與實際的動態(tài)環(huán)境有所不同, 對于動態(tài)環(huán)境中的路徑規(guī)劃問題, 機器人避障相關(guān)的主要問題是移動機器人與障礙物之間的相對位置和相對速度, 而非絕對位置和絕對速度. 對此, Gess等人[4]615-620對一般的人工勢場函數(shù)進行了改進, 在引力函數(shù)勢場中引用移動機器人與目標(biāo)點的相對位置和相對速度, 在斥力場函數(shù)中引入機器人與障礙物的相對位置和相對速度, 找出在動態(tài)環(huán)境下移動機器人的路徑規(guī)劃算法, 得出較優(yōu)的仿真與實驗結(jié)果.

1 改進的人工勢場法

人工勢場法將機器人看作質(zhì)點,并且使機器人同時受到斥力和引力的作用. 機器人距離障礙物越近斥力越大;相反,引力場函數(shù)與目標(biāo)點的位置有關(guān), 且機器人距離目標(biāo)點越遠(yuǎn)引力越大.中人工勢場表示如下:

(1)

式中:Utotal為總勢場,Urep為斥力場,Uatt為引力場.勢場中的力表示為:

(2)

式中:Ftotal為合力,Frep為斥力,Fatt為引力,其中：

(3)

(4)

根據(jù)式(3)和式(4)分析得到,機器人工作環(huán)境中引力勢場為全局性的，斥力場為局部性的,如果障礙物與機器人的距離超出ρ0時Urep為0; 如果目標(biāo)在障礙物的附近且機器人向目標(biāo)運動,則引力越來越小,斥力越來越大當(dāng)Ftotal=0,陷入局部最小. 機器人將會出現(xiàn)停滯不前或在障礙物前振蕩的狀態(tài),障礙物越多出現(xiàn)局部最小的概率就越大. GNRON問題存在的根本原因是總勢場函數(shù)的最小值不在目標(biāo)點.為了解決這個問題我們構(gòu)造了一個新的斥力場函數(shù)如下:

(5)

Frep=-Urep

(6)

其中

(7)

(8)

a是從障礙物到機器人的單位向量,b是從機器人到目標(biāo)點的單位向量.根據(jù)式(5)分析,當(dāng)n=0時,式(6)退化為:

(9)

因此,必須根據(jù)環(huán)境的變化選擇參數(shù)n,且n>0.

2 改進的量子遺傳算法

2.1 量子比特編碼

算法采用量子比特進行編碼,一個量子比特有0或1兩個狀態(tài),如式(10):

(10)

而α、β是相應(yīng)狀態(tài)時出現(xiàn)概率的兩個復(fù)數(shù), 并且

(11)

2.2 量子遺傳算法自適應(yīng)調(diào)整策略

量子狀態(tài)的轉(zhuǎn)移是量子門通過變換矩陣實現(xiàn)的. 用量子旋轉(zhuǎn)門的旋轉(zhuǎn)角度來表示量子染色體的加快收斂速度.量子旋轉(zhuǎn)門的調(diào)整操作如下:

(12)

(13)

(14)

θi=s(αi,βi)和Δθi分別代表旋轉(zhuǎn)的方向和角度,其中Δθi的取值在0.1π～0.005π之間. 本文主要采用自適應(yīng)調(diào)整對其進行調(diào)整. 自適應(yīng)調(diào)整主要是考慮個體當(dāng)前測量值的適應(yīng)度f(xi)與該個體當(dāng)前目標(biāo)值的適應(yīng)度f(bi)兩個因素,如果(f(xi)-f(bi))/f(bi)<閾值(根據(jù)實際的優(yōu)化問題確定),當(dāng)接近最優(yōu)解的個體出現(xiàn)時,則減小Δθi的值,加快收斂速度; (f(xi)-f(bi))/f(bi)>閾值,解群中的個體就會適應(yīng)度不佳,則會增加Δθi的值,使解群偏離局部最優(yōu)解或者使得產(chǎn)生最優(yōu)解的機會加大.

2.3 路徑適應(yīng)度評價

安全性和路徑代價是評價路徑優(yōu)劣考慮的兩個主要因素.本文采用了兩個不同的適應(yīng)度函數(shù)對路徑進行評價.

(15)

(16)

式中:β、γ為加權(quán)調(diào)整系數(shù).

(17)

式中:L為路徑點到目標(biāo)點的水平距離,u越大, 路徑越優(yōu).

(18)

式中:q為障礙物個數(shù),

(19)

osk為障礙評價度,v為該路徑點的安全評價度.式(15)確定路徑點的量子態(tài)更新,式(16)確定對路徑的選擇.

2.4 融合算法流程

Step3 用式(15)和(16)對個體進行評價,記下當(dāng)前的最優(yōu)解并與當(dāng)前的目標(biāo)值進行比較;

Step4 用式(12)和(14)調(diào)整策略U (t),并進一步改進P(t);

Step5 判斷停止的條件,如果滿足條件時則停止,否則繼續(xù);

Step6 賦值t=t+1, 轉(zhuǎn)到step(2),則進入循環(huán)迭代.

3 仿真實驗和對比分析

用Matlab仿真軟件對所提算法進行仿真,來驗證算法的有效性.主要參數(shù)設(shè)置如下:機器人工作環(huán)境為30×30的柵格模型;取初始種群規(guī)模為50; m=20,Δθi=0.01,ρ0=1.在實驗過程中這些參數(shù)可根據(jù)情況調(diào)整,其他參數(shù)另定.

圖1 人工勢場的局部極小

圖2 改進的算法效果

圖3 算法在復(fù)雜環(huán)境下的路徑規(guī)劃

實驗2: 為驗證所提算法的有效性,對文獻[2]和文獻[4]的算法以及所提算法進行了仿真對比,如表1所示為3種算法性能的對比結(jié)果.

表1 算法性能對照表

4 結(jié)論

本文提出的是一種基于融合算法的移動機器人路徑規(guī)劃技術(shù),是利用改進的人工勢場法對移動機器人進行實時控制,可以平衡障礙物的斥力,因而消除奇異值點,使得機器人到達(dá)目標(biāo)點.通過量子遺傳算法對最優(yōu)或次優(yōu)個體進行選擇,為最優(yōu)或次優(yōu)個體進入下一代提供了保障,實現(xiàn)了路徑的優(yōu)化和安全性的提高.仿真結(jié)果表明了融合算法的有效性.

[1] 劉春陽,程億強,柳長安.基于改進勢場法的移動機器人避障路徑規(guī)劃[J].東南大學(xué)學(xué)報, 2008, 39(增刊).

[2] KHATIB O. Real-time obstacle avoidance for manipulators and mobile robot[J]. Int J of Robotic Research, 1986, 5(1).

[3] Ko N Y, Lee B H. Avoid ability measure in moving obstacle avoidance problem and its use for robot motion planning[J]. IEEE Int Conf on Intelligent Robots and System. Osaka, 1996.

[4] Ge S S, Cui Y J. New potential functions for mobile robot path planning[J]. IEEE Trans on Robotic Automation,2000, 16(5).

[責(zé)任編輯 冰 竹]

Mobile Robot Path Planning Technology Based on a Fusion Algorithm

WEI Xianyong, MA Li

(ShangqiuPolytechnic,Shangqiu476000,China)

In order to solve goals non-reachable with obstacles nearby (GNRON), a novel technology of mobile robot path planning based on a fusion algorithm is proposed. A new potential field function is presented by adding an exponential factor to the repulsive potential functions, it can balance the repulsive force of obstacles and eliminate singularity in planning, and the robot can get to the goal. QGA is used to select the optimal or sub-optimal path in order to protect the optimal or sub-optimal path into the next generation, and optimization of the route length and safety are realized. Simulation result shows that the proposed method can effectively improve the performance of path planning.

potential field; path Planning; mobile robot; quantum genetic algorithm (QGA)

2015-08-06

魏先勇(1979- )，男，河南寧陵人，商丘職業(yè)技術(shù)學(xué)院講師，碩士，主要從事計算機網(wǎng)絡(luò)安全、信息安全、智能計算研究。

1671-8127(2015)05-0025-04

TP24

A