基于融合算法的移动机器人路径规划技术

魏先勇,马 黎

(商丘职业技术学院,河南 商丘 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