基于粒子群算法的机器人路径规划

#基于改进粒子群算法的智能机器人路径规划摘要:针对机器人路径规划问题，为了使机器人能在较短的时间里，经过最短的路径，且较平滑的从起始位置运动到目标位置。本文采用粒子群群智能算法，首先，用栅格法建模，然后用粒子群算法寻优。针对粒子群算法局部寻优能力差的缺点，提出一种非线性动态调整惯性权重的改进粒子群路径规划算法。该算法将栅格法与粒子群算法进行有效结合，在路径长度的基础上引入安全度和平滑度概念，建立动态调整路径长度的适应度函数。与传统的粒子群算法相比，实验结果表明，改进算法具有较强的安性实时性及寻优能力。关键词:智能机器人；路径规划；栅格法；粒子群算法0引言路径规划是智能机器人导航的最基本环节之一，它是指智能机器人在具有障碍物的工作环境中，按照某一性能指标(如距离、时间、能量等)，不间断地利用所携带的传感器去认知周围的环境，读取障碍物的大小、位置和距离，不断地感知环境信息和周围障碍物的变化，搜索一条从起始状态到目标状态的最优或近似最优的安全、无碰撞路径。根据智能机器人对环境信息的已知程度，路径规划可分为两类：一类是环境信息已知的全局路径规划，另一类是环境信息未知或部分已知的局部路径规划。目前，常用的路径规划方法主要有粒子群(ParticleSwarmOptimization，PSO)算法、人工势场法、栅格法、神经网络法和蚁群算法等。相比其他算法而言，粒子群算法具有收敛速度快、设置参数少、实现简单等特点，近年来受到很多学者的重视，并成功应用于许多领域。但粒子群算法本身还存在着一些缺陷，如局部寻优能力差、速度和位置更新公式不够完善等问题，严重影响了路径规划的计算效率和可靠性。在对粒子群算法的深入研究中，国内外学者对其固有缺陷提出了各种改进方法，主要通过引入固定的惯性权重和学习因子等方法对速度更新公式进行修改，有所改观但并不完美。针对上述问题，本文采用栅格法建立环境模型，以粒子群算法为基本演化算法，引入非线性动态调整惯性权重和改进适应度函数的方法对粒子群算法加以改进[2],将粒子群算法直接运用到栅格法中，得到智能机器人全局最优路径。1粒子群算法基本思想粒子群算法的背景是“人工生命”“人工生命”是来研究具有某些生命基本特征的人工系统。人工生命包括两方面的内容。其一是研究如何利用计算技术研究生物现象；其二研究如何利用生物技术研究计算问题。我们现在关注的是第二部分的内容。现在已经有很多源于生物现象的计算技巧。例如，人工神经网络是简化的大脑模型；遗传算法是模拟基因进化过程的。现在我们讨论另一种生物系统一社会系统。更确切的是，在由简单个体组成的群落与环境以及个体之间的互动行为。也可称做“群智能”(SwarmIntelligence)。这些模拟系统利用局部信息从而可能产生不可预测的群体行为，它们都用来模拟鱼群和鸟群的运动规律，主要用于计算机视觉和计算机辅助设计。在计算智能(ComputationalIntelligence)领域有两种基于群智能的算法。蚁群算法(AntColonyOptimization)和粒子群算法(ParticleSwarmOptimization)。前者是对蚂蚁群落食物采集过程的模拟。已经成功运用在很多离散优化问题上。粒子群优化算法(PSO)也是起源对简单社会系统的模拟。最初设想是模拟鸟群觅食的过程，但后来发现PSO是一种很好的优化工具。如前所述，PSO模拟鸟群的捕食行为。设想这样一个场景：一群鸟在随机搜索食物。在这个区域里只有一块食物。所有的鸟都不知道食物在那里。但是他们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢？最简单有效的就是搜寻目前离食物最近的鸟的周围区域。PSO从这种模型中得到启示并用于解决优化问题。在PSO中，每个优化问题的解都是搜索空间中的一只鸟。我们称之为“粒子”所有的粒子都有一个由被优化的函数决定的适应值(Fitnessvalue)，每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。PSO初始化为一群随机粒子(随机解)。然后通过迭代找到最优解。第i个微粒表示为X=(x,x,,x)，然后粒子们就跟踪两个“极值”在ii1i2iD解空间中搜索。第一个就是粒子本身所找到的最优解，这个解叫做个体极值P,best

记为P=(p,p,,p);另一个极值是群体所有微粒经历过的最好位置(有最TOC\o"1-5"\h\zii1i2iD好的适应度)，这个极值就是全局极值g，记为P=(,p，…,p)。另外也bestgg1g2gD可以不用整个种群而只是用其中一部分作为粒子的邻居，那么在所有邻居中的极值就是局部极值。微粒i的速度用V=(v,v,...,v)表示，而每一个粒子的位置ii1i2iD就是一个潜在的解。在每一次迭代计算中，粒子的第d维(1<d<D)根据如下公式来更新自己的速度和位置:Vn+1二WVn+Vn+1二WVn+clrand()ididid-Xnid)+c2rand()cgd—Xn(1)id(2)(2)Xn+1=Xn+Vn+1

ididid其中，rand()是［0,1］范围内变化的随机函数；c1和c2是正实数，称作学习因子(LearningFactors),用来调节每次迭代的步长；w为惯性权重(InertiaWeight)；n=1,2,…为迭代次数；此外，微粒的速度V被一个最大速度V所限制。如果idmax当前对微粒的加速导致它在某维的速度超过该维的最大速度V，则该维的速度max被限制为该维最大速度V。max公式(1)的第1部分为动量项，该项系数w随着迭代逐步减小可渐进地加强局部搜索能力；第2部分为“认知(Cognition)”部分，表示微粒自身的思考；第3部分为“社会(Social)”部分，表示微粒间的信息共享与相互合作。2环境模型的建立在二维平面上对智能机器人的工作环境用改进的栅格法进行建模。环境建模的有效性对于机器人能否高效地规划和避障具有关键性的作用，栅格法的优点是建模方便迅速，能运用多个栅格的拼合来代表多种形状的障碍物，以减少可行区域由障碍物建模造成的损失。但该方法也存在不足，采用传统栅格的序列进行路径规划时，当栅格粒度越小，虽然障碍物的表示越精确，但同时会占用大量的存储空间和延长规划时间，算法的搜索范围将按指数增加；当栅格粒度太大，规划的路径会很不精确。本文将采用一种改进的栅格法进行建模［牛，为保证机器人能够在环境模型中无碰撞地运动，将机器人模型简化为一个很小的质点，把机器人的实际尺寸折算进障碍物的面积内，根据机器人的实际尺寸将障碍物的边界向外扩展。如果某一栅格中存在障碍物，则定义此黑色栅格为障碍栅格，表示为1;反之白色为自由栅格，表示为0。用多个栅格的拼合来代表不同形状的障碍物，自由栅格则被合并成为机器人的可达区域，且栅格的大小以对障碍物表示的精确度为准。本文在对空间进行建模时，对空间内的障碍物做如下处理，实际障碍物如图1(a)所示，处理后障碍物如图1(b)所示：不满一个栅格时算一个栅格；障碍物的空凹部分和这个障碍物算成一个整体障碍物，避免局部死区的出现，这叫作障碍物的合并；把地图的边界当成障碍物来处理。图1障碍物形状处理图3改进粒子群算法的路径规划在建立的空间模型中，利用粒子群算法直接找出一条最优路径。粒子群算法中的每一个粒子都有一个解，也就是一条路径，粒子群算法从众多的解中寻找一个最优解形成最优路径。每个粒子的优化函数是粒子所代表的路径长度，在这里具体指的是每一个粒子所跨过的格数。3.1粒子的有效性粒子的有效性是指粒子中任意两个相邻的元素之间的矩形区域能自由连通，中间不能有障碍物。即满足约束条件且所经过的栅格为自由栅格的粒子为有效粒

子，只要粒子中任意两个相邻的元素不能自由连通或栅格中同一行(同一列)迂回出现两次路径，该粒子就无效。图2中三幅图表示的是粒子p从第k次迭代到第k+1次有效路径的实例，图3中三幅图表示的是粒子p从第k次迭代到第k+1次无效路径的实例。P(k}■\咻+1)1^!(c)相邻元素中间连通图2粒子有效路径图PtA)PtA)1A*HZ■■■*W1J(a)相邻元素无法连通(b)相邻元素无法上下迂回连通（c）相邻元素无法左右迂回连通图3粒子无效路径图3.2粒子适应度函数适应度函数是粒子群优化算法中的一个很重要的因素，它决定了算法能否收敛。本文在以路径长度作为适应度函数的基础上加入安全度、平滑度，对所有参数进行加权平均凸，以满足复杂环境下机器人路径规划的要求。1）规划的路径尽可能短，路径的长度可由下式表示:f=fv（x一x）2+（y一y）2ivi+iii+iii=1式中：f表示一个粒子中所有相邻顶点之间的直线距离的和，（x,y）表示粒子1ii当前的坐标，（x,y）表示粒子下一位置的坐标。i+1i+12）引入惩罚函数，提高路径的安全度。当机器人与障碍物相撞时，在机器(3)人的路径长度上引入一个惩罚函数，粒子碰撞的障碍物越多，施加的惩罚越大,使得此路径生成的概率越小。惩罚函数表示为:—M2k=1(4)式中：N表示粒子从起始点到终点的直线路径上障碍物的个数之和，M表示给定的一个较大常数项。3）引入路径平滑度。机器人在运动过程中走对角路线可缩短路径长度以节约时间，但改变机器人的运动方向也会耗费时间，为了使机器人完成任务所耗费的时间最短，本文引入路径平滑度公式如下:(5)式中：n表示粒子所走对角路径中机器人转角45°的次数,1角路径中机器人转角90°的次数，r表示机器人的半径。n表示粒子所走直2综合f、f、f所得123适应度函数为:(6)式中Q、P、Y为各自函数的加权因子，为大于等于0的任意实数。通过调整Q、P、丫可以调节f、f、f在适应度函数中所占的比重。当Q=1,P二0，123Y二0时，转化为常规的仅以路径长度作为适应度函数的数学模型。式中f和2f作为惩罚判断函数和平滑度修正函数，其取值一般小于f的数量级。313.3非线性动态调整惯性权重的PSO算法标准粒子群算法中，前期该算法容易陷入局部极值，产生早熟收敛。同时,由于迭代后的速度呈线性递增趋势，到后期无法进行较细的局部搜索，无法达到完全避碰的路径规划要求。针对以上缺陷，以Kennedy和Eberhart为代表的专家学者引入惯性权重w的粒子群算法(ParticleSwarmOptimizationalgorithmwithWeight，WPSO)[i],以限制迭代后期由于速度过快而无法进行精细局部搜索。引入初期，取固定值w可有效改善这一缺陷，随后又提出了线性递减规律改变惯性权重的粒子群算法(ParticleSwarmOptimizationalgorithmwithLinearlyDecreasingWeight，LDWPSO)，具体计算公式[5]如下:w=ww=wmax-(w-w)•—kmaxmink(7)max式中：ww表示惯性权重的最大值和最小值,k表示当前迭代次数，k表maxminmax示最大迭代次数。专家提出的改进对求最优化解有所改善，但不明显。本文将动态非线性递减惯性权重的思想引入粒子群算法中，公式如下:wk+1=wk+1=w+-w)•minkmin'k-k、—maxIk丿max(8)式中：w为当前迭代所得的值，其初始值为w;k表示当前迭代次数；k表TOC\o"1-5"\h\zkmaxmax示最大迭代次数。惯性权重w从初始值w随着n的不同值以及迭代变化k+1maxw的值，非线性下降，当k=0时w=w;当k=k时减小到最小值w。kk+1maxmaxmin根据个体粒子和粒子群所处的不同区域，惯性权重按不同的非线性指数n下降。当个体粒子和粒子群处于远离个体极值和全局极值的中心区域时，取n=1.1，由式(8)可知，惯性权重下降速度减慢，这样惯性权重在这一阶段具有较大值，粒子群将以较快的速度飞向群体最优位置；当个体粒子和粒子群逐渐靠近目标最优值时，进入中心范围后，取n=0.9，由式（8）可知，惯性权重下降加快，粒子在最优值所在区域对优化目标进行更加细致的搜索。中心区域的范围界限为个体粒子和全局粒子所发现的距个体极值和全局极值最大距离的中间位置。4仿真结果与分析本文利用Matlab7.0在IntelCore2主频1.86GHz计算机上进行了仿真实验。仿真参数选择如下：种群规模即粒子个数M=50,粒子最大速度v=15,max加速因子c=c=2算法最大迭代次数k=200，最大惯性权重w=0.9，最小12maxmax惯性权重w二0.4，固定的惯性权重设定为w=0.7，对于动态的惯性权重，惯min性权重W随着迭代次数k的增加非线性从0.9减少到0.4。利用栅格模型对粒子群算法的智能机器人路径规划进行仿真，复杂障碍物环境模型下的仿真结果如图所示。从仿真结果可以看出，智能机器人从开始点“S”运动到终止点（目标点）“E”，两种算法都能实现寻优和避障能力。但PSO机器人路径规划易陷入局部最优，在避障中过多地考虑障碍物带来的影响，而忽略了实时性；而WPSO机器人路径规划相比PSO路径规划能跳出局部最优，却没有考虑障碍物和机器人边缘的影响，机器人路径中的安全性下降;本文算法针对两种算法存在的缺陷，考虑障碍物边缘和机器人转角次数的影响，引入路径长度的安全度和平滑度，行50次，表1记录了复杂环境下基本粒子群算法（PSO）与优化后的粒子群算法（WPSO）最优路径长度及仿真时间的结果。表1仿真结果对比表算法算法路径长度仿真时间最优路径均值方差均值方差PSO30.67837.571128.5140.374.2e-3WPSO28.63636.345113.0670.342.4e-3

从表I可以看到，两种算法中WPSO算法的最优路径最短，由于引入了非线性惯性权重及新的适应度函数，但在机器人路径规划应用中优化后的算法的收敛速度大于原始算法，且最优路径最短，则运行时间最短。总的来说，优化后的算法无论最优路径长度还是运行时间都优于原始算法。5小结本文以栅格法为环境建模方法，直接将粒子群算法运用到智能机器人路径规划中，可在起点与终点之间得到一条简单安全的最优路径。计算机仿真证明该方法不仅可以找到最优路径，而且算法过程简单，容易实现，比传统粒子群算法能得出较优结果。参考文献KennedyJ,EberhartR.Particleswarmoptimization[A].in:Proceedingsofthe4thIEEEInternationalConferenceonNeuralNetworks[C]，Piscataway:IEEEServiceCenter,1995,pp.1942-1948.GarnierS,GautraisJ,TheraulazG.Thebiologicalprinciplesofswarmintelligence[J].SwarmIntelligen