第3期 李擎等：基于粒子群算法的移动机器人全局路径规划策略 401. 起始点 0.45 100 O文献刀的算法 本文算法 0.40 0.35 0.20 89101112131415161718192021 运行次数 目标点 图8简单环境下执行时间对比 图6复杂环境下最优路径 Fig 8 Comparison of mn tie in siple envimmment Fig 6 Optmnum path in camplex envimmment 实验，图4所示的简单环境中取种群大小M=80 5结语 粒子的维数D=4,迭代次数N=100相同的条件下， 两种算法每次运行得到的最优路径长度和执行时间 仿真研究表明，本文所提出的移动机器人路径 分别如图7和图8所示，在如图4所示的简单环境 规划算法可在起点与终点之间得到一条简单安全的 和如图6所示的复杂环境下，两种算法结果对比如 最优路径，其主要特点有：(1)粒子群算法和其他优 表1所示，其中复杂环境下参数取值均为种群大小 化算法相比有实现简单，可调参数少的优点；(2)加 M=50,粒子维数D=8,迭代次数N=80可见改进 速系数和惯性权重均自适应调节，收敛速度快；(3) 后的算法求得最优路径长度和执行时间都显著缩 将迭代过程中的无效粒子直接取为全局极值点或邻 短、可活动区域的引入使粒子群更容易搜索到最 域个体极值点的方案，避免了重新初始化粒子，从而 优路径，改进后的粒子群优化算法加快了收敛速度， 缩短了规划时间；(4)“可活动区域”别除了不必要 156 的搜索区域，提高了粒子群算法的搜索效率 0文献7刀的算法 155 ■本文算法 154 参考文献 [1]Dai B Xiao X M.CaiZ X.Current status and future devebopment 59 of mobile mbot path planning technobgy Control Eng China 200512(3):198 151 (戴博，肖晓明，蔡自兴.移动机器人路径规划技术的研究现状 150 与展望.控制工程，2005,12(3)：198) 149 [2] Lozanoperez T.Aukmatic planning of manipultor transfer move- 148 ments EEE Trans Syst Man Cybem 1981 11 (10):681 ggg地o地， [3]TakahashiO.Schillng R J Motion planning in a plane using gen eralized voronoi diagnms IEEE Trans Rob Autom.1989,5 (2): 运行次数 143 图7简单环境下最优路径长度对比 [4]Yu H B LiX A.Fast path panning based on gril model of mobot Fig 7 Comnparison of the shortest length in smple envimomment M icmelectmon Canput 2005 22(6):98 表1两种算法结果平均值对比 (于红斌，李孝安·基于栅格法的机器人快速路径规划微电子 Table I Camparison of average vahes cakulated by wo algorithms 学与计算机，2005,22(6)：98) [5] Kennedy J Ebethart R C Particle wwam optin ization//Proceed- 最优路径长度 执行时间/ 环境 算法 ings of the 1995 EEE In temational Confennce on Neural Net 均值 方差 均值 方差 works Perth 1995:1942 文献[7]算法152.952.48 0.396.1×10-5 [6]Qn Y Q Sun D B Li N.et al Path planning for mobile mbot 简单 本文算法 147.561.1×10-40.31 1.7×10-4 based on particle swam optin ization Robot 2004.26(3):222 (秦元庆，孙德宝，李宁，等基于粒子群算法的移动机器人路 文献[7]算法160.12 16.86 1.71 4.10X10-3 复杂 径规划.机器人，2004,26(3)：222) 本文算法 143.631.80×10-41.432.04×10-4 [7]Sun B.Chen W D.XiY G.Particle swam optin ization based glob-第 3期 李 擎等： 基于粒子群算法的移动机器人全局路径规划策略 图 6 复杂环境下最优路径 Ｆｉｇ．6 Ｏｐｔｉｍｕｍｐａｔｈｉｎｃｏｍｐｌｅｘｅｎｖｉｒｏｎｍｅｎｔ 实验．图 4所示的简单环境中取种群大小 Ｍ＝80‚ 粒子的维数 Ｄ＝4‚迭代次数 Ｎ＝100相同的条件下‚ 两种算法每次运行得到的最优路径长度和执行时间 分别如图 7和图 8所示．在如图 4所示的简单环境 和如图 6所示的复杂环境下‚两种算法结果对比如 表 1所示‚其中复杂环境下参数取值均为种群大小 Ｍ＝50‚粒子维数 Ｄ＝8‚迭代次数 Ｎ＝80．可见改进 后的算法求得最优路径长度和执行时间都显著缩 短．“可活动区域 ”的引入使粒子群更容易搜索到最 优路径‚改进后的粒子群优化算法加快了收敛速度． 图 7 简单环境下最优路径长度对比 Ｆｉｇ．7 Ｃｏｍｐａｒｉｓｏｎｏｆｔｈｅｓｈｏｒｔｅｓｔｌｅｎｇｔｈｉｎｓｉｍｐｌｅｅｎｖｉｒｏｎｍｅｎｔ 表 1 两种算法结果平均值对比 Ｔａｂｌｅ1 Ｃｏｍｐａｒｉｓｏｎｏｆａｖｅｒａｇｅｖａｌｕｅｓｃａｌｃｕｌａｔｅｄｂｙｔｗｏａｌｇｏｒｉｔｈｍｓ 环境 算法 最优路径长度 执行时间／ｓ 均值 方差 均值 方差 简单 文献 ［7］算法 152∙95 2∙48 0∙39 6∙1×10—5 本文算法 147∙56 1∙1×10—4 0∙31 1∙7×10—4 复杂 文献 ［7］算法 160∙12 16∙86 1∙71 4∙10×10—3 本文算法 143∙63 1∙80×10—4 1∙43 2∙04×10—4 图 8 简单环境下执行时间对比 Ｆｉｇ．8 Ｃｏｍｐａｒｉｓｏｎｏｆｒｕｎｔｉｍｅｉｎｓｉｍｐｌｅｅｎｖｉｒｏｎｍｅｎｔ 5 结语 仿真研究表明‚本文所提出的移动机器人路径 规划算法可在起点与终点之间得到一条简单安全的 最优路径．其主要特点有：（1）粒子群算法和其他优 化算法相比有实现简单‚可调参数少的优点；（2）加 速系数和惯性权重均自适应调节‚收敛速度快；（3） 将迭代过程中的无效粒子直接取为全局极值点或邻 域个体极值点的方案‚避免了重新初始化粒子‚从而 缩短了规划时间；（4） “可活动区域 ”剔除了不必要 的搜索区域‚提高了粒子群算法的搜索效率． 参 考 文 献 ［1］ ＤａｉＢ‚ＸｉａｏＸＭ‚ＣａｉＺＸ．Ｃｕｒｒｅｎｔｓｔａｔｕｓａｎｄｆｕｔｕｒｅｄｅｖｅｌｏｐｍｅｎｔ ｏｆｍｏｂｉｌｅｒｏｂｏｔｐａｔｈｐｌａｎｎｉｎｇｔｅｃｈｎｏｌｏｇｙ．ＣｏｎｔｒｏｌＥｎｇＣｈｉｎａ‚ 2005‚12（3）：198 （戴博‚肖晓明‚蔡自兴．移动机器人路径规划技术的研究现状 与展望．控制工程‚2005‚12（3）：198） ［2］ ＬｏｚａｎｏｐｅｒｅｚＴ．Ａｕｔｏｍａｔｉｃｐｌａｎｎｉｎｇｏｆｍａｎｉｐｕｌａｔｏｒｔｒａｎｓｆｅｒｍｏｖｅ- ｍｅｎｔｓ．ＩＥＥＥＴｒａｎｓＳｙｓｔＭａｎＣｙｂｅｒｎ‚1981‚11（10）：681 ［3］ ＴａｋａｈａｓｈｉＯ‚ＳｃｈｉｌｌｉｎｇＲＪ．Ｍｏｔｉｏｎｐｌａｎｎｉｎｇｉｎａｐｌａｎｅｕｓｉｎｇｇｅｎ- ｅｒａｌｉｚｅｄｖｏｒｏｎｏｉｄｉａｇｒａｍｓ．ＩＥＥＥＴｒａｎｓＲｏｂＡｕｔｏｍ‚1989‚5 （2）： 143 ［4］ ＹｕＨＢ‚ＬｉＸＡ．Ｆａｓｔｐａｔｈｐｌａｎｎｉｎｇｂａｓｅｄｏｎｇｒｉｄｍｏｄｅｌｏｆｒｏｂｏｔ． ＭｉｃｒｏｅｌｅｃｔｒｏｎＣｏｍｐｕｔ‚2005‚22（6）：98 （于红斌‚李孝安．基于栅格法的机器人快速路径规划．微电子 学与计算机‚2005‚22（6）：98） ［5］ ＫｅｎｎｅｄｙＪ‚ＥｂｅｒｈａｒｔＲＣ．Ｐａｒｔｉｃｌｅｓｗａｒｍｏｐｔｉｍｉｚａｔｉｏｎ∥Ｐｒｏｃｅｅｄ- ｉｎｇｓｏｆｔｈｅ1995ＩＥＥＥＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅｏｎＮｅｕｒａｌＮｅｔ- ｗｏｒｋｓ．Ｐｅｒｔｈ‚1995：1942 ［6］ ＱｉｎＹＱ‚ＳｕｎＤＢ‚ＬｉＮ‚ｅｔａｌ．Ｐａｔｈｐｌａｎｎｉｎｇｆｏｒｍｏｂｉｌｅｒｏｂｏｔ ｂａｓｅｄｏｎｐａｒｔｉｃｌｅｓｗａｒｍｏｐｔｉｍｉｚａｔｉｏｎ．Ｒｏｂｏｔ‚2004‚26（3）：222 （秦元庆‚孙德宝‚李宁‚等．基于粒子群算法的移动机器人路 径规划．机器人‚2004‚26（3）：222） ［7］ ＳｕｎＢ‚ＣｈｅｎＷ Ｄ‚ＸｉＹＧ．Ｐａｒｔｉｃｌｅｓｗａｒｍｏｐｔｉｍｉｚａｔｉｏｎｂａｓｅｄｇｌｏｂ- ·401·