基于微分进化算法的室内移动机器人路径规划

马丽萍,吴丹丹,姚 鑫,李 珣

(西安工程大学 电子信息学院,陕西 西安 710048)

0 引 言

路径规划是机器人研究中最基本的关键问题,目的是寻找一条从起点到终点的最短安全路径[1]。对于时间的长短参数、能量的消耗参数以及很多生态性的问题均要找出最优的解决方法。国内外学者就移动机器人路径规划问题做了大量的工作[2]，如可视图法[3]、人工势场法[4]、动态窗口算法[5]、模糊逻辑算法[6]以及Dijkstra算法[7]等。除此之外,智能算法是近十年解决移动机器人路径规划问题的主流方法之一,微分进化算法则是其中一种较为新颖仿生智能算法,其通过“优胜略汰”的自然进化法则,解决路径规划问题,现有仿真实验表明,相较于其他算法,微分进化算法的全局优化能力强,是一种可以被广泛应用的优化方法[8]。

上述研究,大多依靠静态避障思维[9]进行移动机器人轨迹规划研究,根据障碍物进行既定的动作。控制移动机器人脱离险境,使用遍历法达到目的地,对于室内有限环境而言这种方式机器人的运行效率较低。因为,室内环境中有限次数的环境探知或是地图的输入,能够提供移动机器人路径规划的优化依据,所以根据这一假设进行室内机器人路径优化研究,能够有效提高移动机器人在特定环境中的工作效率。本文针对室内环境并在假设地图已知情况下,在Matlab仿真实验中基于微分进化算法对文中移动机器人的路径进行规划研究,在ROS的Mapping仿真环境进行了代码的移植和实验。

1 TurtleBot2移动机器人运动模型

本文实验物理对象是TurtleBot2移动机器人平台,为了能够将本文研究的路径规划算法进行ROS系统的可靠移植,需要进行运动学模型的建立。

1.1 移动机器人运动学模型

TurtleBot2 轮式移动机器人由底座、 驱动轮和从动轮组成, 从动轮仅起支撑作用。 忽略路面情况变化等影响, 得出移动机器人底座的运动学模型[10], 如图1所示。

图 1 移动机器人底座运动学模型Fig.1 Kinematics model of mobile robot base

图1中,l为两驱动轮的间距,v和w分别为机器人底座的线速度和角速度,vl和vr分别为机器人底座左右轮速。由图1可得到左右两轮速度的关系式为

(1)

假设两轮差速驱动移动机器人质心c在两驱动轮轴线中心位置,(xc,yc)为机器人的质心坐标,r为驱动轮半径,底座的位姿向量为p=(xc,yc,θ)T,两轮差速驱动底座模型,如图2所示。 运动学方程为

(2)

图 2 差速驱动移动机器人模型Fig.2 Model of differentially driven mobile robot

1.2 里程计模型

设ω为机器人的转向角速度;v为机器人质心处的线速度;vl和vr分别为机器人的2个驱动轮的线速度;θ为机器人运动方向与x轴的夹角即方向角;l为机器人驱动轮的间距,对于图2所示的两轮差速驱动移动机器人,当其运动满足纯滚动而无滑动条件时,机器人的运动有如下约束:

(3)

(4)

(5)

以上被称为仅适用于移动机器人直线行驶也就是起始和终止位姿方向角差值为0的里程计模型。

2 微分进化算法的路径规划

2.1 A*算法的路径规划

A*算法[11]是ROS系统仿真环境中,内置于移动机器人路径规划的基础算法,使用栅格法将移动机器人的室内工作环境模拟成为栅格地图[12],每个栅格的信息直接与地图中每个区域相匹配,根据栅格地图来定位导航。在栅格地图中,机器人的行进方向不再是任意方向,而是固定的8个行进方向,分别为左(L)、左前(F-L)、左后(B-L)、右(R)、右前(F-R)、右后(B-R)、前(F)、后(B)。以简单的机器人从客厅到餐厅的室内路线规划问题为例(见图3)，做室内2D空间仿真环境(见图4)。

图 3 室内平面环境示意图Fig.3 Sketch of indoor environment

移动机器人在前进的过程中通过自身所带的传感器扫描感应周围的环境和自身状态,其搜索过程如图4(a) (b) (c)所示,即首先起点由第一个搜索中心开始,相邻栅格标注A，B，C，D,如图4(a)所示;然后将相邻栅格做为t+1时刻的搜索备选中心,如图4(b)所示,判断当中心点是否为终点坐标;最后连接各个点位的搜索结果,获得规划好的路径如图4(c)所示。

(a) 搜索相邻栅格

(b) 搜索中心变化

(c) A*算法Matlab路径仿真图图 4 A*搜索算法示意图Fig.4 Sketch of A* search algorithm

从Matlab仿真环境中的实验明显看出,依靠A*算法进行的路径规划,由于其在临近栅格中搜索以距离为指标的路径,所以存在一定的“视野”局限性,最终仿真结果如图4(c)所示的路径,不能与图3中的理想路径匹配。因此,为改进实验中发现的问题,引入微分进化算法进行室内环境的移动机器人路径规划研究。

2.2 微分进化算法的路径规划

仿生优化算法中,蚁群算法易于实现,具有良好的全局优化能力,但是随着环境的扩大,计算量急速增长,易陷入局部最优[13];遗传算法最大的优点是易于和其他算法相结合,并充分发挥自身迭代的优势,缺点是适应度函数选择不当的情况下有可能收敛于局部,由于没有反馈信息,到后期之后运算效率将大大降低[14];同遗传算法相比,粒子群算法具有简洁、易于实现、鲁棒性好、路径短、收敛速度快等优点,但易陷入局部最优[15]。

(6)

式中:xj,max和xj,min分别为解空间第j维的上下界。随机选择2个不同的个体向量得到差分向量,将差分向量赋予权值后与另一个随机选出的向量相减得到变异个体,变异个体和目标个体进行参数混合交叉得到交叉个体,择优生成新一代种群。微分进化算法的基本操作包括变异,交叉及选择3种。

2.2.1 变异操作 对于父代种群中任意目标向量xi,利用微分进化算法，按式(7)生成变异向量vi:

vi=xr1+F·(xr2-xr3),i=1,2,…,N

(7)

式中:{xr1,xr2,xr3}是随机选择的3个不同个体,且r1≠r2≠r3≠i,种群规模满足N≥4；F用于控制差分向量(xr1-xr2)的影响,称为放缩因子，F值介于[0，2]之间。

2.2.2 交叉操作 通过变异向量vi和目标向量xi各维度的随机重组以提高种群个体的多样性,交叉向量[ui,1,ui,2,…,ui,D]:

(8)

微分进化算法主要控制参数和种群规模N、放缩因子F以及交叉常量C,若C为0则没有交叉,rand(b)保证ui至少从vi中获得一个元素用来确保有新的个体生成,防止种群出现进化停滞不变。

2.2.3 选择操作 新的向量个体ui的适应度值比目标向量个体xi的适应度值更好时,ui才会被种群所接受,否则xi仍然保存在下一代种群中,并且迭加计算时继续作为目标向量执行变异和交叉操作。设待优化问题minf(x)，则

(9)

本文中移动机器人路径规划的性能指标主要包括完成任务的安全和耗电指标,即威胁代价最小和耗电代价最小指标。

威胁代价最小性能指标为

(10)

耗电代价最小性能指标为

(11)

移动机器人路径规划的总性能指标为

minJ=kJt+(1-k)Jf

(12)

总威胁代价为

(13)

式中:n为威胁源个数；wt为路径上各点威胁代价;wf为路径上各点耗电代价;Lij为起始点到节点之间的长度;tk为威胁点的威胁等级,耗电代价和路径有关；k∈[0,1]表示安全性能和耗电性能的权衡系数,任务重视安全则k较大,若任务需要快速则k较小。本文微分进化算法流程如图5所示。

图 5 微分进化算法流程图

Fig.5 Flow chart of differential evolution algorithm

3 结果与分析

3.1 室内环境描述及初始化

设定实验仿真室内客厅环境含3个沙发,1架钢琴以及1个落地灯,房间内家具静止定点分布,移动机器人打扫路线规划是指满足某种性能指标的最优行走路线[17]。假设在得到威胁家具信息的时刻,移动机器人匀速保持当前方向。设定初始参数如表1所示:种群规模N=30,优化维数D=20,最大迭加次数Nmax=250,变异因子F=20,交叉因子C=0.6,之后改变种群规模N和迭加次数Nmax得到不同的路径规划结果和进化曲线。

表 1 移动机器人执行任务时的环境参数Tab.1 Environmental parameters for mobile robots in task execution

3.2 仿真及结果分析

根据上述初始化参数构建的仿真环境,需要特别说明的是,为证明规划方法的有效性和实时性,对仿真环境中的物品位置进行随意设置。

获得仿真实验结果如图6所示。图6(a)为A*算法与微分进化算法路径对比图，图6(b)为A*算法与微分进化算法迭代曲线图。

从仿真的结果来看,采用微分进化算法规划的移动机器人,将在有障碍环境下的路线规划问题转化为求D维函数极值的优化问题,收敛速度快而且性能良好,这一优点得到了很好的验证。移动机器人规划的前进路线成功绕过了各种障碍点,顺利到达任务终点。在微分进化算法中根据障碍点的大小,障碍等级的不同而产生不同的规划路线,在相同参数条件下由于微分进化算法本身收敛情况的不稳定也会导致规划路径的不同。实验不仅验证了微分进化算法的可行性,同时也验证了微分进化算法的高效性。从图6(b)的算法寻优迭代曲线可以看出,相对于传统启发算法,微分进化算法在复杂环境的路径规划过程中,于第12次迭代达到最优值,A*算法需要14余次迭代才能达到最优值。

(a) A*算法与微分进化算法路径对比

(b) A*算法与微分进化算法迭代曲线对比图 6 微分进化与A*算法仿真实验对比Fig.6 Simulation experiment comparison of differential evolution and A* algorithm

虽然在迭代次数上微分进化算法弱优于A*算法，但是，微分进化算法在最差路径长度、最优路径长度、平均路径长度上都优于A*算法，这是因为A*算法在搜索时“视野”有一定局限性，导致算法容易陷入局中最优解，规划的路径精度不高。微分进化算法的整体性能要远远优于A*算法路径规划,收敛时间短,具有很好的全局优化能力。

3.3 ROS的路径规划实现

根据西安工程大学电子信息学院207实验室布局创建地图，利用A*算法和微分进化算法对仿真环境中移动机器人TurtleBot2进行路径规划。

在ROS中Map-server是ROS的地图服务器[18],其能够在虚拟环境中根据实际室内特征建立地图,本文地图创建如图7所示。

图 7 ROS系统地图构建示意图Fig.7 Schematic map of ROS systematic map construction

图7中,箭头表示消息传递的方向,圆表示话题,矩形表示节点[19]。利用Gazebo进行机器人动力学的仿真,使用Rviz驱动TurtleBot2转动得到可视化环境[20],如图8(a)所示;建立室内环境仿真地如图8(b)所示。

(a) Rviz可视化环境 (b) 室内环境仿真图图 8 Gazebo中路径规划仿真地图Fig.8 Simulation map of path planning in Gazebo

机器人首先规划出全局路径,然后沿着全局路径前进,到达障碍物的影响距离以内时,机器人由于受到影响向远离障碍物的方向前进,直到过了障碍物,最后得到安全有效的规划路径。对于室内可能存在较复杂的环境,设定了跨度较复杂的起始点进行实验,如图9所示。其中图9(a)为A*算法规划的路径,图9(b)为微分进化算法规划的路径。

(a) A*算法规划的路径 (b) 微分进化算法规划的路径图 9 基于ROS的仿真实验图Fig.9 Simulation experiment diagram based on ROS

在ROS的Rviz中可视化环境中可以看到,虽然A*算法机器人安全有效的通过障碍物,但是机器人绕过障碍物时没有选择最短路径规划线路并不是最优。多次实验结果表明,本文方法与ROS内核中的A*算法都能够使机器人平稳、流畅的越过障碍物,并且最终再次回到规划的路径上面,直到到达目标点。但从图9中可以看出,当存在2个障碍物之间的距离略大于机器人的通过空间时,由于A*算法是利用遍历避障的方式,因此存在丢失最优路径的可能;但微分进化算法是一种全局优化算法,故机器人会选择到目标点距离最短的路径,即可获得障碍物之间的路径。因此,在地图已提供的基础上,微分进化算法在路径规划寻优的能力上具有更大的优势。

4 结 语

为能够针对室内环境特点给予移动机器人更优的规划路径,重点介绍了A*算法和微分进化算法的原理模型,通过Matlab软件仿真实验说明算法的可行性。由于A*算法存在多个最小值时不能保证搜索的路径最优,容易陷入局部最优解的时候无法跳出,搜索的点数多,搜索范围大,效率较低。为此,文中采用微分进化算法进行移动机器人路径规划研究,并进行了Matlab和ROS环境中的仿真实验验证。实验结果说明,基于微分进化算法的规划路径,由于算法的收敛性较强因此寻优效率较高,同时能够较A*算法具有更好的全局寻优能力。