D0I:10.13374/i.i8sn1001-t53.2010.03.024 第32卷第3期 北京科技大学学报 Vol 32 No 3 2010年3月 Journal of Un iversity of Science and Techno logy Beijing Mar.2010 基于粒子群算法的移动机器人全局路径规划策略 李擎 徐银梅张德政尹怡欣 北京科技大学信息工程学院，北京100083 摘要提出了一种基于保收敛粒子群优化算法的移动机器人全局路径规划策略，为移动机器人在有限时间内找到一条避 开障碍物的最短路径提供了一种解决方案·首先建立环境地图模型，将连接地图中起点和终点的路径编码成粒子，然后根据 獐碍物位置规划出粒子的可活动区域，在此区域内产生初始种群，使粒子在受限的区域内寻找最优路径·在搜索过程中，粒子 群优化算法的加速系数和惯性权重均随迭代次数自适应调节.仿真实验表明算法可在起点与终点之间找到一条简单安全的 最优路径。与其他文献所提的方法进行了对比研究，结果表明本文所提算法具有更快的搜索速度和更高的搜索质量. 关键词移动机器人：路径规划：粒子群优化算法；活动区域 分类号TP273.5:TP2426 G lobal path plann ing m ethod form obile robots based on the particle swam algo- rithm LIQ ing XU Yin mei ZHANG De-theng YIN Yixin School of Infomation Engineering University of Science and Technobgy Beijng Beijing 100083.Chna ABSTRACT A global path planning method formobile robots based on the guaranteed convergence particle swam optin ization algo- rithm is presented A solution is provided formobile mobots to find the shortest path avoiding obstacles in a lin ited period of tie First l an environm entalm ap is set up and a path connecting the start point and the end point is coded as a particle Then a particular ac- tive region for particles is mapped out according to the location of obstacles The initial particle population is generated withn this re- gion and particles fly in the active region to searh for the optium path In the search process both the acceleration coefficient and n- ertia weight of the particle swam optin ization algorithm are self-adaptively adjusted along with iteration processes It is proved that the algorithm can plan out a smple and safe optmum path connecting the start point and the end point by siulation experm ents Com par ative studies with a recently reported method show that the proposed algorithm has advantages such as faster search speed and higher search quality KEY W ORDS mobile robot path planning particle swam optin ization:active region 路径规划是自主式移动机器人导航的基本环节 通常可以找到最优解，但需要预先知道准确的全局 之一，所谓移动机器人的路径规划问题，是指在其 环境信息，到目前为止，对于全局路径规划问题已 工作空间中找到一条从起始点到目标点的，能避开 经有许多解决方法2-)，但这些方法大都受到信息 动静态障碍物且能满足某个优化目标（如行走路线 存储方式和规划时间的制约，计算量大，实时性差， 最短、能量消耗最少)的最优（或次优）路径，基于 不能很好地适应于全局路径规划问题，如何对全局 环境模型的路径规划方法山可以分为两种类型：环 路径规划方法做出改进，使之在较短的有限时间内 境信息完全已知的全局路径规划和环境信息完全未 规划出最优路径，是本文的研究目的所在， 知或部分未知的局部路径规划，全局路径规划方法 由Ebetharti和Kennedy提出的粒子群优化算法 收稿日期：2009-01-20 基金项目：国家自然科学基金资助项目(N。60374032):第36批国家留学回国人员科研启动基金资助项目 作者简介：李擎(l97-)男，教授，博士，Email liqing@ies ustb edu cn第 32卷 第 3期 2010年 3月 北 京 科 技 大 学 学 报 ＪｏｕｒｎａｌｏｆＵｎｉｖｅｒｓｉｔｙｏｆＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙＢｅｉｊｉｎｇ Ｖｏｌ．32Ｎｏ．3 Ｍａｒ．2010 基于粒子群算法的移动机器人全局路径规划策略 李 擎 徐银梅 张德政 尹怡欣 北京科技大学信息工程学院‚北京 100083 摘 要 提出了一种基于保收敛粒子群优化算法的移动机器人全局路径规划策略‚为移动机器人在有限时间内找到一条避 开障碍物的最短路径提供了一种解决方案．首先建立环境地图模型‚将连接地图中起点和终点的路径编码成粒子‚然后根据 障碍物位置规划出粒子的可活动区域‚在此区域内产生初始种群‚使粒子在受限的区域内寻找最优路径．在搜索过程中‚粒子 群优化算法的加速系数和惯性权重均随迭代次数自适应调节．仿真实验表明算法可在起点与终点之间找到一条简单安全的 最优路径．与其他文献所提的方法进行了对比研究‚结果表明本文所提算法具有更快的搜索速度和更高的搜索质量． 关键词 移动机器人；路径规划；粒子群优化算法；活动区域 分类号 ＴＰ273 ＋．5；ＴＰ242．6 Ｇｌｏｂａｌｐａｔｈｐｌａｎｎｉｎｇｍｅｔｈｏｄｆｏｒｍｏｂｉｌｅｒｏｂｏｔｓｂａｓｅｄｏｎｔｈｅｐａｒｔｉｃｌｅｓｗａｒｍａｌｇｏ- ｒｉｔｈｍ ＬＩＱｉｎｇ‚ＸＵＹｉｎ-ｍｅｉ‚ＺＨＡＮＧＤｅ-ｚｈｅｎｇ‚ＹＩＮＹｉ-ｘｉｎ ＳｃｈｏｏｌｏｆＩｎｆｏｒｍａｔｉｏｎＥｎｇｉｎｅｅｒｉｎｇ‚ＵｎｉｖｅｒｓｉｔｙｏｆＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙＢｅｉｊｉｎｇ‚Ｂｅｉｊｉｎｇ100083‚Ｃｈｉｎａ ＡＢＳＴＲＡＣＴ Ａｇｌｏｂａｌｐａｔｈｐｌａｎｎｉｎｇｍｅｔｈｏｄｆｏｒｍｏｂｉｌｅｒｏｂｏｔｓｂａｓｅｄｏｎｔｈｅｇｕａｒａｎｔｅｅｄｃｏｎｖｅｒｇｅｎｃｅｐａｒｔｉｃｌｅｓｗａｒｍｏｐｔｉｍｉｚａｔｉｏｎａｌｇｏ- ｒｉｔｈｍｉｓｐｒｅｓｅｎｔｅｄ．Ａｓｏｌｕｔｉｏｎｉｓｐｒｏｖｉｄｅｄｆｏｒｍｏｂｉｌｅｒｏｂｏｔｓｔｏｆｉｎｄｔｈｅｓｈｏｒｔｅｓｔｐａｔｈａｖｏｉｄｉｎｇｏｂｓｔａｃｌｅｓｉｎａｌｉｍｉｔｅｄｐｅｒｉｏｄｏｆｔｉｍｅ．Ｆｉｒｓｔ- ｌｙ‚ａｎｅｎｖｉｒｏｎｍｅｎｔａｌｍａｐｉｓｓｅｔｕｐａｎｄａｐａｔｈｃｏｎｎｅｃｔｉｎｇｔｈｅｓｔａｒｔｐｏｉｎｔａｎｄｔｈｅｅｎｄｐｏｉｎｔｉｓｃｏｄｅｄａｓａｐａｒｔｉｃｌｅ．Ｔｈｅｎ‚ａｐａｒｔｉｃｕｌａｒａｃ- ｔｉｖｅｒｅｇｉｏｎｆｏｒｐａｒｔｉｃｌｅｓｉｓｍａｐｐｅｄｏｕｔａｃｃｏｒｄｉｎｇｔｏｔｈｅｌｏｃａｔｉｏｎｏｆｏｂｓｔａｃｌｅｓ．Ｔｈｅｉｎｉｔｉａｌｐａｒｔｉｃｌｅｐｏｐｕｌａｔｉｏｎｉｓｇｅｎｅｒａｔｅｄｗｉｔｈｉｎｔｈｉｓｒｅ- ｇｉｏｎａｎｄｐａｒｔｉｃｌｅｓｆｌｙｉｎｔｈｅａｃｔｉｖｅｒｅｇｉｏｎｔｏｓｅａｒｃｈｆｏｒｔｈｅｏｐｔｉｍｕｍｐａｔｈ．Ｉｎｔｈｅｓｅａｒｃｈｐｒｏｃｅｓｓ‚ｂｏｔｈｔｈｅａｃｃｅｌｅｒａｔｉｏｎｃｏｅｆｆｉｃｉｅｎｔａｎｄｉｎ- ｅｒｔｉａｗｅｉｇｈｔｏｆｔｈｅｐａｒｔｉｃｌｅｓｗａｒｍｏｐｔｉｍｉｚａｔｉｏｎａｌｇｏｒｉｔｈｍａｒｅｓｅｌｆ-ａｄａｐｔｉｖｅｌｙａｄｊｕｓｔｅｄａｌｏｎｇｗｉｔｈｉｔｅｒａｔｉｏｎｐｒｏｃｅｓｓｅｓ．Ｉｔｉｓｐｒｏｖｅｄｔｈａｔｔｈｅ ａｌｇｏｒｉｔｈｍｃａｎｐｌａｎｏｕｔａｓｉｍｐｌｅａｎｄｓａｆｅｏｐｔｉｍｕｍｐａｔｈｃｏｎｎｅｃｔｉｎｇｔｈｅｓｔａｒｔｐｏｉｎｔａｎｄｔｈｅｅｎｄｐｏｉｎｔｂｙｓｉｍｕｌａｔｉｏｎｅｘｐｅｒｉｍｅｎｔｓ．Ｃｏｍｐａｒ- ａｔｉｖｅｓｔｕｄｉｅｓｗｉｔｈａｒｅｃｅｎｔｌｙｒｅｐｏｒｔｅｄｍｅｔｈｏｄｓｈｏｗｔｈａｔｔｈｅｐｒｏｐｏｓｅｄａｌｇｏｒｉｔｈｍｈａｓａｄｖａｎｔａｇｅｓｓｕｃｈａｓｆａｓｔｅｒｓｅａｒｃｈｓｐｅｅｄａｎｄｈｉｇｈｅｒ ｓｅａｒｃｈｑｕａｌｉｔｙ． ＫＥＹＷＯＲＤＳ ｍｏｂｉｌｅｒｏｂｏｔ；ｐａｔｈｐｌａｎｎｉｎｇ；ｐａｒｔｉｃｌｅｓｗａｒｍｏｐｔｉｍｉｚａｔｉｏｎ；ａｃｔｉｖｅｒｅｇｉｏｎ 收稿日期：2009--01--20 基金项目：国家自然科学基金资助项目 （Ｎｏ．60374032）；第 36批国家留学回国人员科研启动基金资助项目 作者简介：李 擎 （1971— ）‚男‚教授‚博士‚Ｅ-ｍａｉｌ：ｌｉｑｉｎｇ＠ｉｅｓ．ｕｓｔｂ．ｅｄｕ．ｃｎ 路径规划是自主式移动机器人导航的基本环节 之一．所谓移动机器人的路径规划问题‚是指在其 工作空间中找到一条从起始点到目标点的‚能避开 动静态障碍物且能满足某个优化目标 （如行走路线 最短、能量消耗最少 ）的最优 （或次优 ）路径．基于 环境模型的路径规划方法 ［1］可以分为两种类型：环 境信息完全已知的全局路径规划和环境信息完全未 知或部分未知的局部路径规划．全局路径规划方法 通常可以找到最优解‚但需要预先知道准确的全局 环境信息．到目前为止‚对于全局路径规划问题已 经有许多解决方法 ［2--4］‚但这些方法大都受到信息 存储方式和规划时间的制约‚计算量大‚实时性差‚ 不能很好地适应于全局路径规划问题．如何对全局 路径规划方法做出改进‚使之在较短的有限时间内 规划出最优路径‚是本文的研究目的所在． 由 Ｅｂｅｒｈａｒｔ和 Ｋｅｎｎｅｄｙ提出的粒子群优化算法 DOI :10．13374／j．issn1001—053x．2010．03．024