1 引言
路径规划是机器人导航技术的重要部分,研究的内容是在已知或未知的环境中,寻找一条从起点到终点的满足一定优化指标的无碰撞路径。据机器人对环境的掌握状况,已有的路径规划方法可分为基于模型的全局路径规划和基于信息检测的局部路径规划。全局路径规划的基本问题是环境建模和路径寻优,重点在于开发高性能的搜索算法,使得规划的路径全局最优。目前,用于全局路径规划的方法主要有基于图论、栅格等的传统方法[1]和基于进化算法的智能方法[2]。这些方法各具优点,但又都有不足之处[3]。
粒子群优化是Kennedy等借鉴鸟群的集体捕食行为,提出的一种随机群进化方法[4]。相对传统的优化方法,该方法易于实现、可调参数少,以及收敛速度快,已成功应用于函数优化、模式识别、神经网络训练、数据挖掘,以及路径规划等领域。但是,利用粒子群优化进行机器人路径规划,存在局部收敛、效率低下,以及精度不高等缺点,尤其是含有非规则密集障碍物的复杂环境,优化的路径多与障碍物碰撞。
针对粒子群优化用于密集障碍物环境机器人全局路径规划存在的问题,本文提出一种双层微粒群优化方法(Two-layer particle swarm optimization, LPSO)。首先,采用坐标变换法构建环境模型,将路径规划问题表达为一个约束优化函数问题;接着,通过在评价函数中引入罚函数,将约束优化转变为无约束优化;随后,定义脱障算子,给出双层粒子群优化算法的思想及步骤;最后,仿真验证本文所提算法的有效性。
2 问题描述与建模
为了规划机器人路径,首先需要建立问题的数学模型。如图1所示,在机器人工作空间建立两维绝对坐标系
,其中,S为机器人的起点,G为终点,多边形物体表示障碍物。当起点与终点的连线与X轴不重合时,建立如下相对坐标系S-xy:以S和G间的连线为轴,过S点且垂直SG的直线为y轴[5]。两坐标系间的变换公式为:
式中,(X,Y)和(x,y)分别为点在坐标系O-XY和S-xy的坐标,
为坐标轴X与x的夹角,
为S在坐标系O-XY的坐标。
对线段SG进行D+1等分,并过每个等分点作SG的垂线,可以得到平行直线族
,该直线族与路径的交点,即为规划的目标点序列
机器人路径规划,就是在相对坐标系S-xy中,寻找一个目标点序列
,使得构成的路径
满足期望的性能指标。这里,对点
的约束是:
不在障碍物上或内部,且
与相邻点的连线也不与障碍物相交。
对于路径
相对坐标为
机器人路径规划问题,可以建模为一个约束优化问题,通过惩罚不可行路径,得到如下无约束优化问题:
式中,
与障碍物碰撞的次数。由式(5)可知,P与障碍物碰撞的次数越多,受到的惩罚程度越大,该路径的性能越差。
3 基于双层粒子群优化算法的机器人全局路径规划
3.1 启发式搜索——脱障算子
采用微粒群优化进行机器人路径规划时,如果能够根据机器人的起点和终点位置,以及障碍物的位置,引导微粒的搜索,那么,将会提高优化解成为可行路径的概率。基于此,当某路径不可行时,说明该路径的某段与障碍物相交,对该路径实施脱障操作,也即对微粒的相应分量定向定步长变异,以避免机器人与障碍物碰撞。
图2给出了脱障操作的过程,图中,Ⅰ线为原来的路径,由于与障碍物相交,因此,是不可行的;Ⅱ线为脱障操作后得到的路径,不再与障碍物相交,从而成为可行路径。
需要注意的是,对微粒实施脱障操作后,如果微粒的某维,如,超出了取值范围,那么,采用下式进一步调整:
3.2 双层粒子群优化算法
在复杂、密集障碍物的环境中,采用粒子群优化算法进行机器人全局路径规划时所得结果大多为非可行路径,既使为可行路径,也多为局部最优的;而调整粒子群优化算法的参数,已不能有效解决算法后期早熟收敛的问题。为此,本文基于算法结构,提出一种双层粒子群优化算法。
该算法包括两层,底层粒子群优化算法主要在决策变量的取值空间中执行全局搜索,并采用脱障算子动态调整其全局极值点,以快速定位最优路径的大致位置。循环运行若干次底层算法、快速获取若干条无碰路径后,将其上传到顶层,作为顶层种群的部分粒子,进而为顶层算法确定重点搜索区域。为提高底层算法的全局搜索能力,本文采用基于线性递减惯性权值的更新公式更新粒子的速度和位置,具体更新公式如下:
顶层粒子群优化算法接收底层搜索的若干条较优路径后进行局部搜索,并采用脱障算子动态扰动调整其全局极值点。为克服早熟收敛,顶层算法在初期仍需具有好的全局搜索能力。为此,在迭代过程中,顶层算法的惯性权重
和个体学习因子
采用线性递减方式,社会学习因子
值采用线性递增。具体公式如下:
3.3 算法步骤
基于双层粒子群优化算法的机器人全局路径规划方法可描述如下:
Step1:由第2节所提方法,建立问题的环境地图,给出问题的无约束最小优化模型;
Step2:给定种群规模
,变量维数D,令底层算法运行次数计数器
Step3:随机初始化底层种群;计算每个粒子的评价值并令该值为其个体极值点;
,求出种群的全局极值点
,令底层算法迭代计数器
;
Step4:据式(8)和(9)更新底层种群,进而更新其个体极值点
、全局极值点
；
Step5:检测全局极值点
是否为碰撞路径?若是,执行脱障操作,否则存储该全局极值点
至
并进至Step7;
Step8:随机初始化顶层种群,令
为种群的部分初始粒子;计算每个粒子评价值并令该值为其个体极值点
,进而求出全局极值点
;令顶层算法迭代计数器k=1
Step9:根据式(8)和(10)更新顶层种群,进而更新其个体极值点
、全局极值点
；
Step10:检测全局极值点
是否为碰撞路径?若是,执行脱障操作;
Step11:
，返回step9;否则,输出算法搜索结果。
4 仿真实验及结果分析
为验证所提算法的有效性,将本文算法应用到障碍物密集分布的环境中,并与仅含脱障算子的改进粒子群优化算法(OPSO)、标准粒子群优化算法(SPSO)以及遗传算法(GA)比较。
算法所需参数设置:底层和顶层算法皆取粒子群规模N=20,维数D=10,最大迭代次数Y=100。OPSO、SPSO的参数设置均同本文底层粒子群优化算法,但在OPSO中利用了本文的脱障算子。
GA的种群规模N=40,维数D=10,最大迭代次数T=300,采用比例选择复制,单点交叉概率
,变异概率
(大适应度,小概率变异)。实验的运行环境为PC机,Intel Celeron M-1.6GHz CPU,504MB RAM,以及MATLAB7.4。
障碍物密集分布的环境如图3-4所示,在的正方形环境中有12个静态障碍物,其顶点坐标已知,机器人始点终点坐标已知。运行上述四种算法各30次,图3-4和表1分别出示了四种算法所得的最好优化结果、最差优化结果及统计数据。
由表1可知,在障碍物密集分布的环境,SPSO运行30次存在21条碰撞路径,可见SPSO若不改进已不能应用于障碍物密集分布环境的路径规划。而OPSO以100%的比例找到问题的可行路径,且平均运行时间与SPSO相近,可见脱障算子显著提高了OPSO的可行性。然而,OPSO的所得路径均值、方差均明显差于LPSO算法,体现了OPSO仍存在不足,即在SPSO中仅引入脱障算子仍不能完全克服局部早熟。LPSO运行30次均能得到接近理论全局最优解的无碰撞最优路径,且方差很小,这表明LPSO具有较好的鲁棒性。虽然LPSO运行时间均值长于SPSO,但是相对优异的行走路径,稍长的时间花费是可以接受的。GA运行的结果与SPSO相似。由此可见,相对其余三种算法,LPSO具有较强的全局寻优能力和较快的收敛速度。
5 结束语
本文针对标准粒子群优化算法早熟收敛、效率低的缺点,给出了一种用于障碍物密集分布环境下机器人全局路径规划的双层粒子群优化算法。通过定义基于障碍物顶点信息的脱障算子,启发、引导全局极值点向理论全局最优解趋近,有效改善了标准粒子群优化算法的全局寻优能力。采用双层的算法结构,有效解决了早熟收敛问题。仿真结果表明本文所提算法的可行性和有效性。
参考文献:
[1] 刘华军,杨静宇,陆建峰,等.移动机器人运动规划研究综述[J].中国工程科学,2006,8(1):85-94.
[2] CASTILLO O,TRUJILLO L,MELIN P.Multiple objective genetic algorithms for path-planning optimization in autonomous mobile robots[J].Soft Computing,2007,11(3):269-279.
[3] 王志文,郭戈.移动机器人导航技术现状与展望[J].机器人,2003,25(5):470-474.
[4] KENNEDY J,EBERHART R C.Particle swarm optimization[C]//Proc of IEEE Int Conf on Neural Networks．Piscataway,NJ:IEEE Press,1995:1942—1948.
[5] 孙波,陈卫东,席裕庚.基于粒子群优化算法的移动机器人全局路径规划[J].控制与决策,2005,20(9):1052-1060.
作者简介:曾现峰(1972-),男,硕士,讲师,研究方向:智能优化与控制、工业自动化。