基于融合算法的移動機器人路徑規劃技術

魏先勇,馬 黎

(商丘職業技術學院,河南 商丘 476000)

基于融合算法的移動機器人路徑規劃技術

魏先勇,馬 黎

(商丘職業技術學院,河南 商丘 476000)

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

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

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

1 改進的人工勢場法

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

(1)

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

(2)

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

(3)

(4)

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

(5)

Frep=-Urep

(6)

其中

(7)

(8)

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

(9)

因此,必須根據環境的變化選擇參數n,且n>0.

2 改進的量子遺傳算法

2.1 量子比特編碼

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

(10)

而α、β是相應狀態時出現概率的兩個復數, 并且

(11)

2.2 量子遺傳算法自適應調整策略

量子狀態的轉移是量子門通過變換矩陣實現的. 用量子旋轉門的旋轉角度來表示量子染色體的加快收斂速度.量子旋轉門的調整操作如下:

(12)

(13)

(14)

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

2.3 路徑適應度評價

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

(15)

(16)

式中:β、γ為加權調整系數.

(17)

式中:L為路徑點到目標點的水平距離,u越大, 路徑越優.

(18)

式中:q為障礙物個數,

(19)

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

2.4 融合算法流程

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

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

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

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

3 仿真實驗和對比分析

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

圖1 人工勢場的局部極小

圖2 改進的算法效果

圖3 算法在復雜環境下的路徑規劃

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

表1 算法性能對照表

4 結論

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

[1] 劉春陽,程億強,柳長安.基于改進勢場法的移動機器人避障路徑規劃[J].東南大學學報, 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).

[責任編輯 冰 竹]

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- )，男，河南寧陵人，商丘職業技術學院講師，碩士，主要從事計算機網絡安全、信息安全、智能計算研究。

1671-8127(2015)05-0025-04

TP24

A