魏先勇,馬 黎

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

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

魏先勇,馬 黎

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

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

勢(shì)場(chǎng)法; 路徑規(guī)劃; 移動(dòng)機(jī)器人; 量子遺傳算法

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

1 改進(jìn)的人工勢(shì)場(chǎng)法

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

(1)

式中:Utotal為總勢(shì)場(chǎng),Urep為斥力場(chǎng),Uatt為引力場(chǎng).勢(shì)場(chǎng)中的力表示為:

(2)

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

(3)

(4)

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

(5)

Frep=-Urep

(6)

其中

(7)

(8)

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

(9)

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

2 改進(jìn)的量子遺傳算法

2.1 量子比特編碼

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

(10)

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

(11)

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

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

(12)

(13)

(14)

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

2.3 路徑適應(yīng)度評(píng)價(jià)

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

(15)

(16)

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

(17)

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

(18)

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

(19)

osk為障礙評(píng)價(jià)度,v為該路徑點(diǎn)的安全評(píng)價(jià)度.式(15)確定路徑點(diǎn)的量子態(tài)更新,式(16)確定對(duì)路徑的選擇.

2.4 融合算法流程

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

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

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

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

3 仿真實(shí)驗(yàn)和對(duì)比分析

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

圖1 人工勢(shì)場(chǎng)的局部極小

圖2 改進(jìn)的算法效果

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

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

表1 算法性能對(duì)照表

4 結(jié)論

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

[1] 劉春陽(yáng),程億強(qiáng),柳長(zhǎng)安.基于改進(jìn)勢(shì)場(chǎng)法的移動(dòng)機(jī)器人避障路徑規(guī)劃[J].東南大學(xué)學(xué)報(bào), 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é)院講師，碩士，主要從事計(jì)算機(jī)網(wǎng)絡(luò)安全、信息安全、智能計(jì)算研究。

1671-8127(2015)05-0025-04

TP24

A