正在加载图片...
,398 北京科技大学学报 第32卷 (particle swam optin ization algorith,PS0)作为 新方程，如下面两式所示，而其他粒子仍用原方程 一种模拟鸟群飞行的仿生算法，具有算法简洁、易于 (1)、(2)更新： 实现和鲁棒性好等优点，算法对种群大小不十分敏 1=-考+g+ω号+(1-2×and)(3) 感，其收敛速度快的特点非常适合于对移动机器人 路径规划这种实时性要求较高的复杂问题进行求解 1=g十ω岭+t(1-2Xand) (4) 搜索，文献[6]道次将PS0引入移动机器人路径规 式中， 划中，该方法首先使用D冰sta算法获得链接图的 2中， 15 最短路径，然后用P©0对所得路径中的节点位置进 =110.5, p>5 行二次优化以得到更优的路径，由于链接图并不能 其他 完全体现实际规划环境中的信息，二次优化后得到 为算法一次迭代过程中优化函数值连续保持不变 的路径不一定是全局最优路径，因此该方法限制了 的次数，s为一次迭代过程中优化函数值连续减小 PSO的全局寻优能力.文献[7提出了另一种基于 的迭代次数 PS0的全局路径规划算法，通过坐标变换将需规划 2模型描述 路径的二维编码简化为一维编码，充分利用了PS0 的全局寻优能力，但不能很好地解决早熟现象，文 对机器人运动空间建模时作如下假定：机器人 献[8]采用罚函数法表示粒子适应度函数，并加入 在二维有限空间中运动，空间中分布着有限个位置 碰撞能量测试点，极大地缩短了算法的执行时间，但 己知的静态障碍物，障碍物用多边形描述，且可以忽 没有给出碰撞和距离能量函数的权重比，并且该方 略其高度信息：为保证路径的安全性，这里把障碍物 法也不能保证寻得最优路径 按照机器人半径尺寸膨胀，以便将机器人看作质点， 本文旨在深入研究粒子群算法在移动机器人路 忽略其尺寸大小，即按照点机器人来处理问题 径规划问题中的应用.对所提出的方法在简单和复 如图1所示，在全局坐标系0XY中，S为机器 杂环境下进行了仿真实验，并同文献[7]中所提的 人的出发点，G为终点，图中黑色区域表示障碍物， 方法进行了仿真对比，仿真结果表明，无论是在路 机器人的路径规划就是在图中寻找一个点的集合 径长度还是在执行时间方面，本文所提的算法均优 P={S…,…,G,要求相邻点之间为直线 于文献[7]中的方法 连接且无障碍，问题的解是一条最短可行路径，它 1粒子群算法 对应优化算法中的一个粒子，点的坐标对应粒子的 位置，以机器人当前位置$作为原点，以$与目标 随机产生初始粒子群，而每一次迭代过程中粒 点G的连线作为X轴，以垂直于X且经过S点的直 子根据自身找到的最好解和整个群体目前找到的最 线作为Y轴，建立局部坐标系0XY设α为X轴与 好解来更新位置和速度)， X轴的夹角，则相应的坐标变换公式为： 粒子的速度和位置更新方程为： cosa 1=a岭十aand(房一考)十eand成(g-专) Y (5) sina cosd (1) =专+ 把线段SG作D十1等分，并在各个等分点上作 (2) 垂线，则垂线上点的y坐标即构成粒子的位置编 式中，为粒子在第k次迭代中第维的速度： 码对应于前面更新公式中的)等分点的个数D 为粒子在k十1次迭代中第潍位置；9、。为学习 即为粒子的维数.粒子的适应度取为路径长度： 因子，通常取为2；and、anb为[0,1]区间内 的伪随机数；ω为惯性权重，决定了粒子对前面速度 2 Y)= 十(#1一y)2 (6) 继承的多少；Pg分别为粒子自身找到的最好解和 N D+1 整个群体目前找到的最好解. 式中，L为线段SG的长度 对粒子i如果恰巧X=P:=s则速度更新仅仅 应用优化算法求得局部坐标系中的路径点后， 依赖于ω%项，使得算法不能保证收敛，出现早熟现 可以用反变换公式 象，为此Van den Bergh和Enge brecht提出了保收 PSO guaranteed convergence particle swam opti [[ (7) m ization GCPS0)o,对全局最好粒子用如下的更 得到路径点在全局坐标系中的坐标，北 京 科 技 大 学 学 报 第 32卷 （ｐａｒｔｉｃｌｅｓｗａｒｍｏｐｔｉｍｉｚａｔｉｏｎａｌｇｏｒｉｔｈｍＰＳＯ） ［5］作为 一种模拟鸟群飞行的仿生算法具有算法简洁、易于 实现和鲁棒性好等优点．算法对种群大小不十分敏 感其收敛速度快的特点非常适合于对移动机器人 路径规划这种实时性要求较高的复杂问题进行求解 搜索．文献 ［6］首次将 ＰＳＯ引入移动机器人路径规 划中该方法首先使用 Ｄｉｊｋｓｔｒａ算法获得链接图的 最短路径然后用 ＰＳＯ对所得路径中的节点位置进 行二次优化以得到更优的路径由于链接图并不能 完全体现实际规划环境中的信息二次优化后得到 的路径不一定是全局最优路径因此该方法限制了 ＰＳＯ的全局寻优能力．文献 ［7］提出了另一种基于 ＰＳＯ的全局路径规划算法通过坐标变换将需规划 路径的二维编码简化为一维编码充分利用了 ＰＳＯ 的全局寻优能力但不能很好地解决早熟现象．文 献 ［8］采用罚函数法表示粒子适应度函数并加入 碰撞能量测试点极大地缩短了算法的执行时间但 没有给出碰撞和距离能量函数的权重比并且该方 法也不能保证寻得最优路径． 本文旨在深入研究粒子群算法在移动机器人路 径规划问题中的应用．对所提出的方法在简单和复 杂环境下进行了仿真实验并同文献 ［7］中所提的 方法进行了仿真对比．仿真结果表明无论是在路 径长度还是在执行时间方面本文所提的算法均优 于文献 ［7］中的方法． 1 粒子群算法 随机产生初始粒子群而每一次迭代过程中粒 子根据自身找到的最好解和整个群体目前找到的最 好解来更新位置和速度 ［9］． 粒子 ｉ的速度和位置更新方程为： ｖ ｋ＋1 ｉｊ ＝ωｖ ｋ ｉｊ＋ｃ1ｒａｎｄ ｋ 1（ｐ ｋ ｉｊ—ｘ ｋ ｉｊ）＋ｃ2ｒａｎｄ ｋ 2（ｇ ｋ ｊ—ｘ ｋ ｉｊ） （1） ｘ ｋ＋1 ｉｊ ＝ｘ ｋ ｉｊ＋ｖ ｋ＋1 ｉｊ （2） 式中ｖ ｋ ｉｊ为粒子 ｉ在第 ｋ次迭代中第 ｊ维的速度；ｘ ｋ＋1 ｉｊ 为粒子 ｉ在 ｋ＋1次迭代中第 ｊ维位置；ｃ1、ｃ2为学习 因子通常取为 2 ［5］；ｒａｎｄ1、ｒａｎｄ2 为 ［ 01］区间内 的伪随机数；ω为惯性权重决定了粒子对前面速度 继承的多少；ｐ、ｇ分别为粒子自身找到的最好解和 整个群体目前找到的最好解． 对粒子 ｉ如果恰巧 Ｘｉ＝Ｐｉ＝ｇ则速度更新仅仅 依赖于 ωｖｉ项使得算法不能保证收敛出现早熟现 象为此 ＶａｎｄｅｎＢｅｒｇｈ和 Ｅｎｇｅｌｂｒｅｃｈｔ提出了保收 敛 ＰＳＯ （ｇｕａｒａｎｔｅｅｄｃｏｎｖｅｒｇｅｎｃｅｐａｒｔｉｃｌｅｓｗａｒｍｏｐｔｉ- ｍｉｚａｔｉｏｎＧＣＰＳＯ） ［10］对全局最好粒子用如下的更 新方程如下面两式所示而其他粒子仍用原方程 （1）、（2）更新： ｖ ｋ＋1 ｉｊ ＝—ｘ ｋ ｉｊ＋ｇ ｋ ｊ＋ωｖ ｋ ｉｊ＋ρ ｋ （1—2×ｒａｎｄ ｋ ） （3） ｘ ｋ＋1 ｉｊ ＝ｇ ｋ ｊ＋ωｖ ｋ ｉｊ＋ρ ｋ （1—2×ｒａｎｄ ｋ ） （4） 式中 ρ 0＝1ρ ｋ＋1＝ 2ρ ｋ ｓ＞15 0∙5ρ ｋ ｆ＞5 ρ ｋ 其他 ｆ为算法一次迭代过程中优化函数值连续保持不变 的次数ｓ为一次迭代过程中优化函数值连续减小 的迭代次数． 2 模型描述 对机器人运动空间建模时作如下假定：机器人 在二维有限空间中运动空间中分布着有限个位置 已知的静态障碍物障碍物用多边形描述且可以忽 略其高度信息；为保证路径的安全性这里把障碍物 按照机器人半径尺寸膨胀以便将机器人看作质点 忽略其尺寸大小即按照点机器人来处理问题． 如图 1所示在全局坐标系 Ｏ-Ｘ′Ｙ′中Ｓ为机器 人的出发点Ｇ为终点．图中黑色区域表示障碍物 机器人的路径规划就是在图中寻找一个点的集合 Ｐ＝｛Ｓｙ1…ｙｊ…ｙＤＧ｝要求相邻点之间为直线 连接且无障碍．问题的解是一条最短可行路径它 对应优化算法中的一个粒子点的坐标对应粒子的 位置．以机器人当前位置 Ｓ作为原点以 Ｓ与目标 点 Ｇ的连线作为 Ｘ轴以垂直于 Ｘ且经过 Ｓ点的直 线作为 Ｙ轴建立局部坐标系 Ｏ-ＸＹ．设 α为 Ｘ轴与 Ｘ′轴的夹角则相应的坐标变换公式为： Ｘ Ｙ ＝ ｃｏｓα ｓｉｎα —ｓｉｎα ｃｏｓα Ｘ′ Ｙ′ （5） 把线段 ＳＧ作 Ｄ＋1等分并在各个等分点上作 垂线 ｌｊ则垂线上点的 ｙ坐标即构成粒子 ｉ的位置编 码 （对应于前面更新公式中的 ｘ ｋ ｉｊ）．等分点的个数 Ｄ 即为粒子的维数．粒子的适应度取为路径长度： ｆ（Ｙｉ）＝∑ Ｄ ｊ＝0 ＬＳＧ Ｄ＋1 2 ＋（ｙｊ＋1—ｙｊ） 2 （6） 式中ＬＳＧ为线段 ＳＧ的长度． 应用优化算法求得局部坐标系中的路径点后 可以用反变换公式 Ｘ′ Ｙ′ ＝ ｃｏｓα —ｓｉｎα ｓｉｎα ｃｏｓα Ｘ Ｙ （7） 得到路径点在全局坐标系中的坐标． ·398·