正在加载图片...
第3期 李擎等：基于粒子群算法的移动机器人全局路径规划策略 ,399. y=+X(一)（斤12…，D)(8) 式中，r为[01]上的随机数.y"和"为位置边 界约束，取值由各等分线}与可活动区域的交点 决定，如图2中的“；可活动区域在地图边界以 外的部分，则取为地图边界，如图2中的.速度 极值规定了粒子一次迭代中能够飞行的最大距 离，这里取为位置变化范围的10%，即： 图1路径编码方法 =0.1X(“一") (9) Fig 1 Path coding method 粒子初始速度取为： 0 =(2r-1)Xy (10) 3基于P9O的路径规划 式(1)、(3)和(4)中的惯性权重ω随迭代次数 线性减小)，可以使种群开始时大范围搜索新的解 3.1基本思想 空间，以后逐渐小范围搜索，加强搜索现有解空间的 初始化粒子时要满足粒子第潍分量和第汁 能力，即： 1维分量所对应地图中的两个点之间直线连接且无 障碍，即不在障碍物边界范围以内，为缩小粒子搜 w=wn一kX"a一0B (11) 索空间，提高搜索速度，这里提出了“可活动区域” 式中，k为当前迭代次数，k为设定的最大迭代次 这一概念，现举例说明如下：首先确定与规划起点 数，wm为最大惯性权重，wm为最小惯性权重，这 和规划终点连线(SG线)相交的障碍物顶点，并在 里取为=0.9n=0.41], SG线两侧找到与SG线距离最远的两个顶点，如 为加快搜索速度，本文中的加速系数也采用了 图钟的ef两点，然后通过efS和G作矩形 自适应调节算法，在搜索开始时采用较大的Q和较 abcd并在与所作矩形有交集的障碍物顶点中找到 小的，目的是使粒子飞遍整个搜索空间而不趋于 G线两侧与SG线距离最远的两个顶点，如图2中 个体极值点，而在迭代后期则采用较小的q和较大 的m、n两点，接着采用由m、nS和G形成的矩形 ab'c'代替原有矩形.重复以上过程，直到与所作 的。，以便使粒子趋于全局最优解，自适应调节 的公式如下所示： 矩形相交的障碍物不再存在时为止，将所得矩形在 SG线两侧各扩展一个较小的正数飞，这时得到的矩 (12) 形范围即为本文所指的粒子“可活动区域”，如图2 中的灰色区域所示，根据基本的几何知识可知，最 十2 (13) 短路径一定存在于该区域内，这样就变相地缩小了 式中，q和e分别为q和g的初始值，q和分别 搜索空间 为q和g的最终值.q:=2.5,g:=0.5qr=0.5 gr=2.54 在粒子搜索过程中，每进行一次速度和位置的 更新，部分有效粒子会变为无效粒子，这里的无效是 相对有效而言的，指粒子所代表的路径穿过障碍物， 即为有碰的，有碰路径不能被接受，必须被放弃， 如果对所有无效粒子都重新进行初始化必然要耗费 大量的计算时间，为此本文提出直接将部分有碰路 径粒子的位置取为整个群体目前找到的最优位置， 在该位置附近细化搜索；另一部分有碰路径粒子的 位置取为邻域粒子所找到的最好解L?使得该无效 粒子进入邻域粒子所在的局部最优区域搜索，其中 图2可活动区域图例 L由 Fg 2 Illustration for the active region L,∈{P-pP-H1…,P-P,P+1…,PtP+1, 粒子第维的初始位置由下式计算得到： f(L)=mini f(P1),f(P)...f(P-1).f(P:).第 3期 李 擎等： 基于粒子群算法的移动机器人全局路径规划策略 图 1 路径编码方法 Ｆｉｇ．1 Ｐａｔｈｃｏｄｉｎｇｍｅｔｈｏｄ 3 基于 ＰＳＯ的路径规划 3∙1 基本思想 初始化粒子时要满足粒子 ｉ第 ｊ维分量和第 ｊ＋ 1维分量所对应地图中的两个点之间直线连接且无 障碍即不在障碍物边界范围以内．为缩小粒子搜 索空间提高搜索速度这里提出了 “可活动区域 ” 这一概念．现举例说明如下：首先确定与规划起点 和规划终点连线 （ＳＧ线 ）相交的障碍物顶点并在 ＳＧ线两侧找到与 ＳＧ线距离最远的两个顶点如 图 2中的 ｅ、ｆ两点然后通过 ｅ、ｆ、Ｓ和 Ｇ作矩形 ａｂｃｄ并在与所作矩形有交集的障碍物顶点中找到 ＳＧ线两侧与 ＳＧ线距离最远的两个顶点如图 2中 的 ｍ、ｎ两点接着采用由 ｍ、ｎ、Ｓ和 Ｇ形成的矩形 ａ′ｂ′ｃ′ｄ′代替原有矩形．重复以上过程直到与所作 矩形相交的障碍物不再存在时为止将所得矩形在 ＳＧ线两侧各扩展一个较小的正数 ε这时得到的矩 形范围即为本文所指的粒子 “可活动区域 ”如图 2 中的灰色区域所示．根据基本的几何知识可知最 短路径一定存在于该区域内这样就变相地缩小了 搜索空间． 图 2 可活动区域图例 Ｆｉｇ．2 Ｉｌｌｕｓｔｒａｔｉｏｎｆｏｒｔｈｅａｃｔｉｖｅｒｅｇｉｏｎ 粒子 ｉ第 ｊ维的初始位置由下式计算得到： ｙｊ＝ｙ ｍｉｎ ｊ ＋ｒ×（ｙ ｍａｘ ｊ —ｙ ｍｉｎ ｊ ） （ｊ＝12…Ｄ） （8） 式中ｒ为 ［01］上的随机数．ｙ ｍａｘ ｊ 和 ｙ ｍｉｎ ｊ 为位置边 界约束取值由各等分线 ｌｊ与 “可活动区域 ”的交点 决定如图 2中的 ｙ ｍａｘ ｊ ；“可活动区域 ”在地图边界以 外的部分则取为地图边界如图 2中的 ｙ ｍｉｎ ｊ ．速度 极值 ｖｊｍａｘ规定了粒子一次迭代中能够飞行的最大距 离这里取为位置变化范围的 10％ ［11］即： ｖｊｍａｘ＝0∙1×（ｙ ｍａｘ ｊ —ｙ ｍｉｎ ｊ ） （9） 粒子初始速度取为： ｖ 0 ｊ＝（2ｒ—1）×ｖｊｍａｘ （10） 式 （1）、（3）和 （4）中的惯性权重 ω随迭代次数 线性减小 ［12］可以使种群开始时大范围搜索新的解 空间以后逐渐小范围搜索加强搜索现有解空间的 能力即： ω＝ωｍａｘ—ｋ× ωｍａｘ—ωｍｉｎ ｋｍａｘ （11） 式中ｋ为当前迭代次数ｋｍａｘ为设定的最大迭代次 数ωｍａｘ为最大惯性权重ωｍｉｎ为最小惯性权重．这 里取为 ωｍａｘ＝0∙9ωｍｉｎ＝0∙4 ［13］． 为加快搜索速度本文中的加速系数也采用了 自适应调节算法．在搜索开始时采用较大的 ｃ1和较 小的 ｃ2目的是使粒子飞遍整个搜索空间而不趋于 个体极值点而在迭代后期则采用较小的 ｃ1 和较大 的 ｃ2以便使粒子趋于全局最优解自适应调节 ［14］ 的公式如下所示： ｃ1＝（ｃ1ｉ—ｃ1ｆ） ｋｍａｘ—ｋ ｋｍａｘ ＋ｃ1ｆ （12） ｃ2＝（ｃ2ｉ—ｃ2ｆ） ｋｍａｘ—ｋ ｋｍａｘ ＋ｃ2ｆ （13） 式中ｃ1ｉ和 ｃ2ｉ分别为 ｃ1和 ｃ2的初始值ｃ1ｆ和 ｃ2ｆ分别 为 ｃ1和 ｃ2 的最终值．ｃ1ｉ＝2∙5ｃ2ｉ＝0∙5ｃ1ｆ＝0∙5 ｃ2ｆ＝2∙5 ［14］． 在粒子搜索过程中每进行一次速度和位置的 更新部分有效粒子会变为无效粒子这里的无效是 相对有效而言的指粒子所代表的路径穿过障碍物 即为有碰的．有碰路径不能被接受必须被放弃． 如果对所有无效粒子都重新进行初始化必然要耗费 大量的计算时间为此本文提出直接将部分有碰路 径粒子的位置取为整个群体目前找到的最优位置 在该位置附近细化搜索；另一部分有碰路径粒子的 位置取为邻域粒子所找到的最好解 Ｌｉ使得该无效 粒子进入邻域粒子所在的局部最优区域搜索其中 Ｌｉ由 Ｌｉ∈｛Ｐｉ—ｌＰｉ—ｌ＋1…Ｐｉ—1ＰｉＰｉ＋1…Ｐｉ＋ｌ—1Ｐｉ＋ｌ｝ ｆ（Ｌｉ）＝ｍｉｎ｛ｆ（Ｐｉ—ｌ）ｆ（Ｐｉ—ｌ＋1）…ｆ（Ｐｉ—1）ｆ（Ｐｉ） ·399·