【智能系统】基于改进粒子群算法的移动机器人多目标点路径规划

第12卷第3期 智能系统学报 Vol.12 No.3 2017年6月 CAAI Transactions on Intelligent Systems Jun.2017 D0I:10.11992/tis.201606046 网络出版地址：http:/kns.cmki.ne/kcms/detail/23.1538.TP.20170404.1218.004.html 基于改进粒子群算法的移动机器人多目标点路径规划 蒲兴成，李俊杰2，吴慧超2，张毅 (1.重庆邮电大学数理学院，重庆400065：2.重庆邮电大学智能系统及机器人研究所，重庆400065：3.重庆邮电大学 先进制造学院，重庆400065) 摘要：针对移动机器人遍历多个目标点的路径规划问题，提出了一种基于改进粒子群算法和蚁群算法相结合的路 径规划新方法。该方法将目标点的选择转化为旅行商问题，并利用蚁群算法进行优化，定义了每两个目标点之间的 路径规划目标函数，利用粒子群算法对其进行优化。针对粒子群算法存在的早熟现象，将反向学习策略引入粒子群 算法，并对粒子群算法的惯性权重和学习因子进行改进。性能测试结果表明，改进的粒子群算法能有效避免粒子早 熟现象，提高粒子群算法的寻优能力及稳定性。仿真实验结果验证了新方法能有效地实现机器人的多目标点无碰 撞路径规划。真实环境下的实验结果证明了新方法在机器人多目标点路径规划的实际应用中也具有有效性。 关键词：移动机器人；多目标点路径规划：蚁群算法；改进粒子群算法；反向学习策略；惯性权重：学习因子 中图分类号：TP242.6文献标志码：A文章编号：1673-4785(2017)03-0301-09 中文引用格式：蒲兴成，李俊杰，吴慧超，等.基于改进粒子群算法的移动机器人多目标点路径规划[J].智能系统学报，2017,12 (3):301-309. 英文引用格式：PU Xingcheng,LI Junjie,WU Huichao,ctal.Mobile robot multi-goal path planning using improved particle swarm optimization[J].CAAI transactions on intelligent systems,2017,12(3):301-309. Mobile robot multi-goal path planning using improved particle swarm optimization PU Xingcheng',LI Junjie2,WU Huichao2,ZHANG Yi3 (1.School of Science,Chongqing University of Posts and Telecommunications,Chongqing 400065,China;2.Research Center of Intelligent System and Robot,Chongqing University of Posts and Telecommunications,Chongqing 400065,China;3.Advanced Manufacturing Engineering School,Chongqing University of Posts and Telecommunications,Chongqing 400065,China) Abstract:To solve the problem of multi-goal path planning for mobile robots that pass multiple goals,a new path planning method,based on improved particle swarm optimization (PSO)and ant colony optimization (ACO),is proposed.In this new method,the first step is to use an improved PSO,which has high convergence,to optimize the path between two goals among a sequence of goals.The second step is to use the ACO to obtain the shortest path for all target points.The performance experimental result demonstrates that the improved PSO algorithm can effectively avoid premature convergence and enhances search ability and stability.Simulation results show that the improved PSO algorithm can make a mobile robot realize collision-free multi-goal path planning effectively Experiments in a real environment demonstrate that this algorithm has practical application for multi-goal path planning. Keywords:mobile robot;multi-goal path planning;ACO;improved PSO;opposition-based learning;inertia weight;learning factors 路径规划是研究移动机器人的一个重要内容，按其规划范围，分为全局路径规划和局部路径规 划。目前，针对这两种路径规划方式许多学者进行 收稿日期：2016-06-30.网络出版日期：2017-04-04. 基金项目：国家自然科学基金(51604056)，重庆市科学技术委员会项目 了深人研究，并提出了相应的解决方法。全局路径 (cstc2015 jcyBx(0066):重庆市数委项目(K1400432). 通信作者：李俊杰.E-mail:lijunjiel66@126.com. 规划方法有栅格法、可视图法和神经网络法等：局

第 １２ 卷第 ３ 期 智 能 系 统 学 报 Ｖｏｌ．１２ №．３ ２０１７ 年 ６ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｊｕｎ． ２０１７ ＤＯＩ：１０．１１９９２ ／ ｔｉｓ．２０１６０６０４６ 网络出版地址：ｈｔｔｐ： ／ ／ ｋｎｓ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ＴＰ．２０１７０４０４．１２１８．００４．ｈｔｍｌ 基于改进粒子群算法的移动机器人多目标点路径规划 蒲兴成１ ，李俊杰２ ，吴慧超２ ，张毅３ （１．重庆邮电大学 数理学院，重庆 ４０００６５；２．重庆邮电大学 智能系统及机器人研究所，重庆 ４０００６５；３．重庆邮电大学 先进制造学院，重庆 ４０００６５） 摘 要：针对移动机器人遍历多个目标点的路径规划问题，提出了一种基于改进粒子群算法和蚁群算法相结合的路 径规划新方法。 该方法将目标点的选择转化为旅行商问题，并利用蚁群算法进行优化，定义了每两个目标点之间的 路径规划目标函数，利用粒子群算法对其进行优化。 针对粒子群算法存在的早熟现象，将反向学习策略引入粒子群 算法，并对粒子群算法的惯性权重和学习因子进行改进。 性能测试结果表明，改进的粒子群算法能有效避免粒子早 熟现象，提高粒子群算法的寻优能力及稳定性。 仿真实验结果验证了新方法能有效地实现机器人的多目标点无碰 撞路径规划。 真实环境下的实验结果证明了新方法在机器人多目标点路径规划的实际应用中也具有有效性。 关键词：移动机器人；多目标点路径规划；蚁群算法；改进粒子群算法；反向学习策略；惯性权重；学习因子 中图分类号：ＴＰ２４２．６ 文献标志码：Ａ 文章编号：１６７３－４７８５（２０１７）０３－０３０１－０９ 中文引用格式：蒲兴成，李俊杰，吴慧超，等．基于改进粒子群算法的移动机器人多目标点路径规划［ Ｊ］． 智能系统学报， ２０１７， １２ （３）： ３０１－３０９． 英文引用格式：ＰＵ Ｘｉｎｇｃｈｅｎｇ， ＬＩ Ｊｕｎｊｉｅ， ＷＵ Ｈｕｉｃｈａｏ， ｅｔ ａｌ． Ｍｏｂｉｌｅ ｒｏｂｏｔ ｍｕｌｔｉ⁃ｇｏａｌ ｐａｔｈ ｐｌａｎｎｉｎｇ ｕｓｉｎｇ ｉｍｐｒｏｖｅｄ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ［Ｊ］． ＣＡＡＩ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｉｎｔｅｌｌｉｇｅｎｔ ｓｙｓｔｅｍｓ， ２０１７， １２（３）： ３０１－３０９． Ｍｏｂｉｌｅ ｒｏｂｏｔ ｍｕｌｔｉ⁃ｇｏａｌ ｐａｔｈ ｐｌａｎｎｉｎｇ ｕｓｉｎｇ ｉｍｐｒｏｖｅｄ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ ＰＵ Ｘｉｎｇｃｈｅｎｇ １ ， ＬＩ Ｊｕｎｊｉｅ ２ ， ＷＵ Ｈｕｉｃｈａｏ ２ ， ＺＨＡＮＧ Ｙｉ ３ （１． Ｓｃｈｏｏｌ ｏｆ Ｓｃｉｅｎｃｅ， Ｃｈｏｎｇｑｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｐｏｓｔｓ ａｎｄ Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎｓ， Ｃｈｏｎｇｑｉｎｇ ４０００６５， Ｃｈｉｎａ； ２． Ｒｅｓｅａｒｃｈ Ｃｅｎｔｅｒ ｏｆ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍ ａｎｄ Ｒｏｂｏｔ， Ｃｈｏｎｇｑｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｐｏｓｔｓ ａｎｄ Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎｓ， Ｃｈｏｎｇｑｉｎｇ ４０００６５， Ｃｈｉｎａ； ３． Ａｄｖａｎｃｅｄ Ｍａｎｕｆａｃｔｕｒｉｎｇ Ｅｎｇｉｎｅｅｒｉｎｇ Ｓｃｈｏｏｌ， Ｃｈｏｎｇｑｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｐｏｓｔｓ ａｎｄ Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎｓ， Ｃｈｏｎｇｑｉｎｇ ４０００６５， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｏ ｓｏｌｖｅ ｔｈｅ ｐｒｏｂｌｅｍ ｏｆ ｍｕｌｔｉ－ｇｏａｌ ｐａｔｈ ｐｌａｎｎｉｎｇ ｆｏｒ ｍｏｂｉｌｅ ｒｏｂｏｔｓ ｔｈａｔ ｐａｓｓ ｍｕｌｔｉｐｌｅ ｇｏａｌｓ， ａ ｎｅｗ ｐａｔｈ ｐｌａｎｎｉｎｇ ｍｅｔｈｏｄ， ｂａｓｅｄ ｏｎ ｉｍｐｒｏｖｅｄ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ （ＰＳＯ） ａｎｄ ａｎｔ ｃｏｌｏｎｙ ｏｐｔｉｍｉｚａｔｉｏｎ （ＡＣＯ）， ｉｓ ｐｒｏｐｏｓｅｄ． Ｉｎ ｔｈｉｓ ｎｅｗ ｍｅｔｈｏｄ， ｔｈｅ ｆｉｒｓｔ ｓｔｅｐ ｉｓ ｔｏ ｕｓｅ ａｎ ｉｍｐｒｏｖｅｄ ＰＳＯ， ｗｈｉｃｈ ｈａｓ ｈｉｇｈ ｃｏｎｖｅｒｇｅｎｃｅ， ｔｏ ｏｐｔｉｍｉｚｅ ｔｈｅ ｐａｔｈ ｂｅｔｗｅｅｎ ｔｗｏ ｇｏａｌｓ ａｍｏｎｇ ａ ｓｅｑｕｅｎｃｅ ｏｆ ｇｏａｌｓ． Ｔｈｅ ｓｅｃｏｎｄ ｓｔｅｐ ｉｓ ｔｏ ｕｓｅ ｔｈｅ ＡＣＯ ｔｏ ｏｂｔａｉｎ ｔｈｅ ｓｈｏｒｔｅｓｔ ｐａｔｈ ｆｏｒ ａｌｌ ｔａｒｇｅｔ ｐｏｉｎｔｓ． Ｔｈｅ ｐｅｒｆｏｒｍａｎｃｅ ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔ ｄｅｍｏｎｓｔｒａｔｅｓ ｔｈａｔ ｔｈｅ ｉｍｐｒｏｖｅｄ ＰＳＯ ａｌｇｏｒｉｔｈｍ ｃａｎ ｅｆｆｅｃｔｉｖｅｌｙ ａｖｏｉｄ ｐｒｅｍａｔｕｒｅ ｃｏｎｖｅｒｇｅｎｃｅ ａｎｄ ｅｎｈａｎｃｅｓ ｓｅａｒｃｈ ａｂｉｌｉｔｙ ａｎｄ ｓｔａｂｉｌｉｔｙ． Ｓｉｍｕｌａｔｉｏｎ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ｉｍｐｒｏｖｅｄ ＰＳＯ ａｌｇｏｒｉｔｈｍ ｃａｎ ｍａｋｅ ａ ｍｏｂｉｌｅ ｒｏｂｏｔ ｒｅａｌｉｚｅ ｃｏｌｌｉｓｉｏｎ⁃ｆｒｅｅ ｍｕｌｔｉ⁃ｇｏａｌ ｐａｔｈ ｐｌａｎｎｉｎｇ ｅｆｆｅｃｔｉｖｅｌｙ ． Ｅｘｐｅｒｉｍｅｎｔｓ ｉｎ ａ ｒｅａｌ ｅｎｖｉｒｏｎｍｅｎｔ ｄｅｍｏｎｓｔｒａｔｅ ｔｈａｔ ｔｈｉｓ ａｌｇｏｒｉｔｈｍ ｈａｓ ｐｒａｃｔｉｃａｌ ａｐｐｌｉｃａｔｉｏｎ ｆｏｒ ｍｕｌｔｉ⁃ｇｏａｌ ｐａｔｈ ｐｌａｎｎｉｎｇ． Ｋｅｙｗｏｒｄｓ： ｍｏｂｉｌｅ ｒｏｂｏｔ； ｍｕｌｔｉ⁃ｇｏａｌ ｐａｔｈ ｐｌａｎｎｉｎｇ； ＡＣＯ； ｉｍｐｒｏｖｅｄ ＰＳＯ； ｏｐｐｏｓｉｔｉｏｎ⁃ｂａｓｅｄ ｌｅａｒｎｉｎｇ； ｉｎｅｒｔｉａ ｗｅｉｇｈｔ； ｌｅａｒｎｉｎｇ ｆａｃｔｏｒｓ 收稿日期：２０１６－０６－３０． 网络出版日期：２０１７－０４－０４． 基金项目：国家自然科学基金（５１６０４０５６），重庆市科学技术委员会项目 （ｃｓｔｃ２０１５ｊｃｙＢｘ００６６）；重庆市教委项目（ＫＪ１４００４３２）． 通信作者：李俊杰． Ｅ⁃ｍａｉｌ：ｌｉｊｕｎｊｉｅ１６６＠ １２６．ｃｏｍ． 路径规划是研究移动机器人的一个重要内容， 按其规划范围，分为全局路径规划和局部路径规 划。 目前，针对这两种路径规划方式许多学者进行 了深入研究，并提出了相应的解决方法。 全局路径 规划方法有栅格法、可视图法和神经网络法等；局

·302 智能系统学报 第12卷 部路径规划方法包括人工势场法、A·算法、人工蜂 了避免PS0出现早熟现象，提高算法的效率，提出 群算法等)。虽然这些算法得到广泛应用，但也存 了具有快速收敛性的粒子群算法。实验结果验证 在一些缺点：栅格力度越小，栅格法对障碍物的描 了混合算法的有效性以及改进的粒子群算法的优 述越精确，但环境信息的存储会占据大量的存储空 越性。 间，算法的搜索范围也将成指数增加)：人工势场 1问题描述 法由于斥力的作用，机器人很难准确到达目标点。 A·算法对开放列表的维护是最耗时的，尤其是在地 1.1多目标点路径规划 图过大的情况下。 假设在移动机器人多目标点路径规划中含有n 移动机器人多目标点路径规划是指在复杂的 个目标点，则移动机器人会产生n(n-1)/2条路径。 环境下找到一条从起始点开始经过所有目标点的 为了满足移动机器人行走路径最短的要求，机器人 无碰撞的最优路径。在实际应用中，移动机器人多 需要从n(n-1)/2条路线中选择出一条经过所有点 目标点路径规划多应用于电厂巡检、医院查房等。 的最短路径。图1描述了在起始点和目标点位置已 移动机器人多目标点路径规划的基本原则包括3个 知的情况下，移动机器人的运动轨迹。从图1(a)中 方面：1)当前点或起始点以及目标点提前已知；2) 可知移动机器人的移动路线有很多条，且必须经过 任意时刻机器人都可以决定移动路线：3)机器人必 所有目标点才能完成路径规划：图1(b)表示移动机 须经过的所有目标点来完成路径规划。根据移动 器人运动的理想路线。 机器人多目标点路径规划的特点，移动机器人多目 15 标点路径规划问题可以转化为旅行商(traveling saleman problem,TSP)问题。目前有很多算法用于 10 解决TSP问题)，但多目标点路径规划与TSP问题 相比更复杂。因此本文提出了一种基于粒子群算 法和蚁群算法相结合的混合算法用于解决移动机 器人多目标点路径规划问题。 81 蚁群算法(ant colony optimization,ACO)是一种 10 20 启发式进化算法，由蚂蚁觅食行为演化而来。在解 (a)所有路径 决TSP问题上，蚁群算法表现出了较强的优越性。 粒子群算法(particle swarm optimization,PSO)是 15 种群体智能算法，由鸟群觅食行为演化而来。与 ~般的群体智能算法相比，PS0具有记忆特性，可 10 以通过自我学习和向他人学习方式获得更多的信 息。由于参数少，计算方便等优点，PS0广泛应用 在优化问题上，并取得了很好的效果。随着移动机 器人技术的发展，国内外学者对粒子群算法在移动 机器人路径规划上做了大量的研究，如多机器人路 10 15 20 径规划s6,自由浮动机器人轨迹规划)以及其他 (b)理想路径 应用领域[8-。PS0在路径规划上应用广泛，ACO 图1多点之间的路径轨迹 善于解决TSP问题，因此采用两者结合的方式非常 Fig.1 The path trajectory of multi-goal 适合移动机器人多目标点路径规划问题。 为了解决上述问题，我们将目标点的选择规划 在一个包含障碍物的空间内，利用PS0算法对 为TSP问题的一个分支。目前，求解TSP问题最有 起始点到目标点及每个目标点与目标点之间进行 效的方法主要有郭涛算法、模拟退火算法、遗传算 路径规划。起始点、目标点以及障碍物位置已知， 法、蚁群算法等)。由于这些算法都有优缺点，因 但是哪一条路线会被选择是未知的。为了确定哪 此有些学者尝试结合两种或多种算法解决彼此算 一条路径会被选择，AC0被用于遍历起始点和所有 法上的缺点[]。蚁群算法作为一种自组织正反馈 目标点，以便得到一条经过所有点的最短路径。为 算法，与其他算法相比，具有很强的鲁棒性。而且

部路径规划方法包括人工势场法、Ａ ∗ 算法、人工蜂 群算法等［１］ 。 虽然这些算法得到广泛应用，但也存 在一些缺点：栅格力度越小，栅格法对障碍物的描 述越精确，但环境信息的存储会占据大量的存储空 间，算法的搜索范围也将成指数增加［２］ ；人工势场 法由于斥力的作用，机器人很难准确到达目标点。 Ａ ∗算法对开放列表的维护是最耗时的，尤其是在地 图过大的情况下。 移动机器人多目标点路径规划是指在复杂的 环境下找到一条从起始点开始经过所有目标点的 无碰撞的最优路径。 在实际应用中，移动机器人多 目标点路径规划多应用于电厂巡检、医院查房等。 移动机器人多目标点路径规划的基本原则包括 ３ 个 方面：１）当前点或起始点以及目标点提前已知；２） 任意时刻机器人都可以决定移动路线；３）机器人必 须经过的所有目标点来完成路径规划。 根据移动 机器人多目标点路径规划的特点，移动机器人多目 标点路径规划问题可以转化为旅行商 （ ｔｒａｖｅｌｉｎｇ ｓａｌｅｍａｎ ｐｒｏｂｌｅｍ， ＴＳＰ）问题。 目前有很多算法用于 解决 ＴＳＰ 问题［３］ ，但多目标点路径规划与 ＴＳＰ 问题 相比更复杂。 因此本文提出了一种基于粒子群算 法和蚁群算法相结合的混合算法用于解决移动机 器人多目标点路径规划问题。 蚁群算法（ａｎｔ ｃｏｌｏｎｙ ｏｐｔｉｍｉｚａｔｉｏｎ， ＡＣＯ）是一种 启发式进化算法，由蚂蚁觅食行为演化而来。 在解 决 ＴＳＰ 问题上，蚁群算法表现出了较强的优越性。 粒子群算法（ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ， ＰＳＯ）是一 种群体智能算法，由鸟群觅食行为演化而来［４］ 。 与 一般的群体智能算法相比，ＰＳＯ 具有记忆特性，可 以通过自我学习和向他人学习方式获得更多的信 息。 由于参数少，计算方便等优点，ＰＳＯ 广泛应用 在优化问题上，并取得了很好的效果。 随着移动机 器人技术的发展，国内外学者对粒子群算法在移动 机器人路径规划上做了大量的研究，如多机器人路 径规划［５－６］ ，自由浮动机器人轨迹规划［７］ 以及其他 应用领域［８－９］ 。 ＰＳＯ 在路径规划上应用广泛，ＡＣＯ 善于解决 ＴＳＰ 问题，因此采用两者结合的方式非常 适合移动机器人多目标点路径规划问题。 在一个包含障碍物的空间内，利用 ＰＳＯ 算法对 起始点到目标点及每个目标点与目标点之间进行 路径规划。 起始点、目标点以及障碍物位置已知， 但是哪一条路线会被选择是未知的。 为了确定哪 一条路径会被选择，ＡＣＯ 被用于遍历起始点和所有 目标点，以便得到一条经过所有点的最短路径。 为 了避免 ＰＳＯ 出现早熟现象，提高算法的效率，提出 了具有快速收敛性的粒子群算法。 实验结果验证 了混合算法的有效性以及改进的粒子群算法的优 越性。 １ 问题描述 １．１ 多目标点路径规划 假设在移动机器人多目标点路径规划中含有 ｎ 个目标点，则移动机器人会产生 ｎ（ｎ－１） ／ ２ 条路径。 为了满足移动机器人行走路径最短的要求，机器人 需要从 ｎ（ｎ－１） ／ ２ 条路线中选择出一条经过所有点 的最短路径。 图 １ 描述了在起始点和目标点位置已 知的情况下，移动机器人的运动轨迹。 从图 １（ａ）中 可知移动机器人的移动路线有很多条，且必须经过 所有目标点才能完成路径规划；图 １（ｂ）表示移动机 器人运动的理想路线。 （ａ）所有路径 （ｂ）理想路径 图 １ 多点之间的路径轨迹 Ｆｉｇ．１ Ｔｈｅ ｐａｔｈ ｔｒａｊｅｃｔｏｒｙ ｏｆ ｍｕｌｔｉ⁃ｇｏａｌ 为了解决上述问题，我们将目标点的选择规划 为 ＴＳＰ 问题的一个分支。 目前，求解 ＴＳＰ 问题最有 效的方法主要有郭涛算法、模拟退火算法、遗传算 法、蚁群算法等［３］ 。 由于这些算法都有优缺点，因 此有些学者尝试结合两种或多种算法解决彼此算 法上的缺点［１０］ 。 蚁群算法作为一种自组织正反馈 算法，与其他算法相比，具有很强的鲁棒性。 而且 ·３０２· 智 能 系 统 学 报 第 １２ 卷

第3期 蒲兴成，等：基于改进粒子群算法的移动机器人多目标点路径规划 ·303. 从本质上讲，蚁群算法的并行特性，强化了算法的 F= 可靠性。因此在解决多目标点选择的问题上，我们 将采用蚁群算法搜索能够遍历所有目标点的方法。 √x四-x)2+0-)下] 1.2粒子的适应度函数 式中，g是目标点的个数，S是粒子个数。 粒子的适应度函数是检验粒子群算法收敛性 移动机器人在向目标点移动过程中，除了要保 的重要函数。在路径规划中，移动距离最短是机器 证其最短性，安全性也是必须要考虑的。为此，将 人首要考虑的目标，其次是安全性。因此，将移动 障碍物对目标点的斥力场函数作为安全性的惩罚 机器人运动距离作为粒子的首要适应度函数。移 函数。斥力场函数定义如下： 动机器人多目标点路径规划如图2所示。由图2可 1)2 d(xgxc),d(xgxo)d 知，移动机器人从起始位置开始避开障碍物，经过 d(xg,o)d 一系列目标点到达目标点n。 0 d(xR,xo)>d 式中：F2是障碍物对机器人的斥力：k,是斥力场系 日标点2 数；d(xR,xo)为机器人到障碍物的距离；d(xR,xc) 目标点1Q 是机器人到目标点的距离：d是障碍物的影响 障碍物 目标点n 范围。 移动机器人多目标点路径规划问题可以抽象 起始点 为当前位置到目标点的最短距离的优化问题，而障 碍物对机器人的斥力作用是保证最短路径安全性 图2移动机器人多目标点路径规划示意图 的前提。因此，针对路径规划的目标函数可以定 Fig.2 The diagram of mobile robot multi-goal path planning 义为 为了便于理解移动机器人多目标点路径规划， F=AF +uF, 可将图2中的多目标点路径规划分解为多个目标点 式中入和μ分别是最短路路径和约束条件的权重。 中的两两目标点之间路径规划。机器人在保证两 2 基本知识 点之间路径规划最短的基础上才能保证多目标路 径规划最短。分解后如图3所示，机器人在当前点 2.1标准粒子群算法 需要选择下一个所经过点，然后到达目标点，在此 在PS0算法中，每个粒子通过自我学习及向 期间要避开障碍物。 “他人”学习向问题空间中的最佳位置移动，进而找 到最优解。V维空间内粒子的位置变量为x:= p目标点 (x1,x2,…,xn）,=(,2,…,)为粒子的速度 下一个 变量。粒子迭代时，通过向两个“极值”学习来更新 经过点 自己：l)局部最优值pe;2)全局最优值gm。PS0 障碍物 充分利用局部最优值和全局最优值，可使优秀粒子 6 的基因得到传承。粒子寻优的过程是粒子根据自 当前点 我学习和向他人学习来更新自己的速度和位置，逐 步获得最优解。粒子的速度和位置更新公式为 图3当前点到目标点避障描述 yt1=wv+c1,(pt-x)+c22(gm-)(1) Fig.3 The obstacle avoidance description of current x1=x+时 (2) point to goal 式中：w是粒子的惯性权重：C1c2是学习因子；r1'2 综上所述，为了保证路径规划的最短性，下一 是[0,1]的随机数；x表示粒子t的位置且x∈ 个移动点的选取是保证移动机器人运动轨迹最短 [rin,r];速度∈[vmn,vr]。当粒子的位置超 的前提。因此，设立移动机器人路径规划目标函数 出了[xm,xm]时，粒子被限制为xn或xr;若粒 F,F,决定了移动机器人行走路径长度。本文中， 子的速度超出了y时，粒子的速度被限制为最大 F,定义为 速度vmso

从本质上讲，蚁群算法的并行特性，强化了算法的 可靠性。 因此在解决多目标点选择的问题上，我们 将采用蚁群算法搜索能够遍历所有目标点的方法。 １．２ 粒子的适应度函数 粒子的适应度函数是检验粒子群算法收敛性 的重要函数。 在路径规划中，移动距离最短是机器 人首要考虑的目标，其次是安全性。 因此，将移动 机器人运动距离作为粒子的首要适应度函数。 移 动机器人多目标点路径规划如图 ２ 所示。 由图 ２ 可 知，移动机器人从起始位置开始避开障碍物，经过 一系列目标点到达目标点 ｎ。 图 ２ 移动机器人多目标点路径规划示意图 Ｆｉｇ．２ Ｔｈｅ ｄｉａｇｒａｍ ｏｆ ｍｏｂｉｌｅ ｒｏｂｏｔ ｍｕｌｔｉ⁃ｇｏａｌ ｐａｔｈ ｐｌａｎｎｉｎｇ 为了便于理解移动机器人多目标点路径规划， 可将图 ２ 中的多目标点路径规划分解为多个目标点 中的两两目标点之间路径规划。 机器人在保证两 点之间路径规划最短的基础上才能保证多目标路 径规划最短。 分解后如图 ３ 所示，机器人在当前点 需要选择下一个所经过点，然后到达目标点，在此 期间要避开障碍物。 图 ３ 当前点到目标点避障描述 Ｆｉｇ．３ Ｔｈｅ ｏｂｓｔａｃｌｅ ａｖｏｉｄａｎｃｅ ｄｅｓｃｒｉｐｔｉｏｎ ｏｆ ｃｕｒｒｅｎｔ ｐｏｉｎｔ ｔｏ ｇｏａｌ 综上所述，为了保证路径规划的最短性，下一 个移动点的选取是保证移动机器人运动轨迹最短 的前提。 因此，设立移动机器人路径规划目标函数 Ｆ１ ，Ｆ１ 决定了移动机器人行走路径长度。 本文中， Ｆ１ 定义为 Ｆ１ ＝ ∑ ｇ ｊ ＝ １ ∑ Ｓ ｉ ＝ １ ｘ ｃｕｒｒｅｎｔ ｉ，ｊ － ｘ ｎｅｘｔ ｉ，ｊ ( ) ２ ＋ ｙ ｃｕｒｒｅｎｔ ｉ，ｊ － ｙ ｎｅｘｔ ｉ，ｊ ( ) ２ [ ＋ ｘ ｎｅｘｔ ｉ，ｊ － ｘ ｇｏａｌ ｉ，ｊ ( ) ２ ＋ ｙ ｎｅｘｔ ｉ，ｊ － ｙ ｇｏａｌ ｉ，ｊ ( ) ２ ] 式中，ｇ 是目标点的个数，Ｓ 是粒子个数。 移动机器人在向目标点移动过程中，除了要保 证其最短性，安全性也是必须要考虑的。 为此，将 障碍物对目标点的斥力场函数作为安全性的惩罚 函数。 斥力场函数定义如下： Ｆ２ ＝ ｋｒ × １ ｄ（ｘＲ，ｘＯ） － １ ｄｍ æ è ç ö ø ÷ ２ ｄ ２ （ｘＲ，ｘＧ）， ｄ（ｘＲ，ｘＯ）≤ｄｍ ０， ｄ（ｘＲ，ｘＯ）＞ｄｍ ì î í ï ï ïï 式中：Ｆ２ 是障碍物对机器人的斥力；ｋｒ 是斥力场系 数；ｄ（ｘＲ ，ｘＯ ）为机器人到障碍物的距离；ｄ（ ｘＲ ，ｘＧ ） 是机器人到目标点的距离； ｄｍ 是障碍物的影响 范围。 移动机器人多目标点路径规划问题可以抽象 为当前位置到目标点的最短距离的优化问题，而障 碍物对机器人的斥力作用是保证最短路径安全性 的前提。 因此，针对路径规划的目标函数可以定 义为 Ｆ ＝ λＦ１ ＋ μＦ２ 式中 λ 和 μ 分别是最短路路径和约束条件的权重。 ２ 基本知识 ２．１ 标准粒子群算法 在 ＰＳＯ 算法中，每个粒子通过自我学习及向 “他人”学习向问题空间中的最佳位置移动，进而找 到最优解。 Ｎ 维空间内粒子的位置变量为 ｘｉ ＝ ｘｉ１ ，ｘｉ２ ，…，ｘｉｎ ( ) ，ｖｉ ＝ ｖｉ１ ，ｖｉ２ ，…，ｖｉｎ ( ) 为粒子的速度 变量。 粒子迭代时，通过向两个“极值”学习来更新 自己：１）局部最优值 ｐｂｅｓｔ；２）全局最优值 ｇｂｅｓｔ。 ＰＳＯ 充分利用局部最优值和全局最优值，可使优秀粒子 的基因得到传承。 粒子寻优的过程是粒子根据自 我学习和向他人学习来更新自己的速度和位置，逐 步获得最优解。 粒子的速度和位置更新公式为 ｖ ｔ＋１ ｉ ＝ ωｖ ｔ ｉ ＋ ｃ１ ｒ１ ｐｂｅｓｔ － ｘ ｔ ｉ ( ) ＋ ｃ２ ｒ２ ｇｂｅｓｔ － ｘ ｔ ｉ ( ) （１） ｘ ｔ＋１ ｉ ＝ ｘ ｔ ｉ ＋ ｖ ｔ ｉ （２） 式中：ω 是粒子的惯性权重；ｃ１ 、ｃ２ 是学习因子；ｒ１ 、ｒ２ 是［０，１］ 的随机数； ｘ ｔ ｉ 表示粒子 ｔ 的位置且 ｘ ｔ ｉ ∈ ｘｍｉｎ ，ｘｍａｘ [ ] ；速度 ｖ ｔ ｉ∈ ｖｍｉｎ ，ｖｍａｘ [ ] 。 当粒子的位置超 出了 ｘｍｉｎ ，ｘｍａｘ [ ] 时，粒子被限制为 ｘｍｉｎ或 ｘｍａｘ；若粒 子的速度超出了 ｖｍａｘ时，粒子的速度被限制为最大 速度 ｖｍａｘ。 第 ３ 期 蒲兴成，等：基于改进粒子群算法的移动机器人多目标点路径规划 ·３０３·

·304. 智能系统学报 第12卷 2.2反向学习策略 远的粒子要快。但是，粒子在问题空间中是随机分 Tizhoosh]在2005年基于相反数或对立点的 布的，每一个粒子相对于最优解的位置都是未知的。 概念提出了反向学习策略。在随后的发展中，该方 基于以上分析，在改进的粒子群算法初始化时 法被应用于解决一些优化问题中[2]。反向坐标 引入反向学习策略有助于粒子寻找最优解。在初 定义如下。 始化时，首先，计算粒子的适应度值以及其反向粒 定义1)假设x在一维空间中的坐标是-5， 子适应度值，并对两者进行比较，选择适应度值较 目标点的坐标为10。那么x反向点x的坐标点为 好的粒子；其次，从种群中选择S个适应度值最好的 5,且点x到目标点的距离为15，点x到目标点的距 粒子作为初始种群。 离为5。比较可得，反向点靠近目标点。x的反向坐 3.2迭代进化过程 标点x的计算公式为 在标准PS0算法中，粒子在问题空间中选择另 x=a+b-x 一个粒子作为学习对象，根据式(1)、(2)进行移动。 式中x∈[a,b],且为实数。把上述定义应用到高维 但在粒子进化的过程中，粒子会发生早熟现象，导 空间可表示成定义2。 致算法无法得到最优解。由式(1)可知，粒子的速 定义2[)在N维空间中的一个点P可表示 度受到惯性权重和学习因子的影响：惯性权重影响 为P(x1,x2,…,xn),其中x1,x2,…,xn∈R,且x:∈ 着粒子的全局搜索和局部搜索能力，学习因子影响 粒子获取信息的能力。为了找到问题最优解，粒子 [a,b],i={1,2,…,n}。则点P对应的反向点P 在进化的过程中，其全局搜索能力和局部搜索能力 可表示为P(元，x2,…,x),其中x表示为 也应该随之发生变化，即从全局搜索渐变为局部搜 x:=a:+b:-x 索，保证粒子可以寻找到问题的最优解。同样，粒 将定义2应用到优化过程中，则反向机制的优 子也应该逐渐增强社交能力，由“自我”学习逐渐向 化过程如定义3。 “他人”学习过渡，以便获取更多有用的信息。 定义34)根据定义1和定义2，反向学习可 根据以上分析，粒子在寻优过程中，惯性权重 以描述为：假设f(x)是已知问题的函数方程，n维空 应该保持动态变化。ω取值较大时，粒子的全局搜 间中的点P(x1,x2,…,xn)是函数方程f(x)的一个 索能力较强：ω取值较小时，粒子的局部搜索能力较 解，且x∈[a:,b],i={1,2,…,n}。则P,的反向 强。由于粒子在寻优的过程中，会逐渐靠近最优 点，粒子的惯性权重应该随着寻优过程自适应变 点为P(元1，x2,…,元n)。计算P:和P:在函数f(x) 化。因此粒子的惯性权重更新公式为 中的函数值。如果f(P)>f(P),则反向点P代替 dist P,;否则保留P,。因此通过不断地计算点P,与反向 ω=0s-(0mx-wmn） max dist 点P,的f(x)值选择其中最优值。 式中：wms和wm分别是粒子惯性权重的最大值和 最小值；dist:是第i个粒子到全局最优粒子的欧几 3 反向学习粒子群算法 里德距离；max_dist是粒子到全局最优粒子的最大 基于反向学习策略的思想，本文提出一种改进 距离。dist,和max_dist表达式分别为[s 的粒子群算法(opposition-based learning improved PSO,OBLIPS0)。本文采用反向学习策略时，将反 dist=(∑8u-a)月 d=1 向学习策略应用到单个粒子中，而不是粒子群体 max_dist argmax(dist,) 中，以便减小粒子迭代过程中的计算量。性能测试 学习因子c,和c2控制粒子本身记忆与同伴记 结果证明，改进的粒子群算法能抑制粒子早熟现 忆之间的相对影响：c,的值较小时，表现为自我认 象，提高收敛效率。下面介绍改进算法的主要机制 知能力不足；C2的值较小时，表现为社交能力不足。 和流程。 为了保证在迭代过程中，粒子的自我认知和社交能 3.1初始化种群 力能够因时而异，因此，粒子的学习因子更新公 粒子在问题空间中找到最优解的时间与粒子 式6]如下： 初始化时在空间中的分布存在正比关系，距离最佳 位置近的粒子找到最优解的时间比距离最佳位置

２．２ 反向学习策略 Ｔｉｚｈｏｏｓｈ ［１１］在 ２００５ 年基于相反数或对立点的 概念提出了反向学习策略。 在随后的发展中，该方 法被应用于解决一些优化问题中［１２－１３］ 。 反向坐标 定义如下。 定义 １ ［１４］ 假设 ｘ 在一维空间中的坐标是－５， 目标点的坐标为 １０。 那么 ｘ 反向点 ｘ ～ 的坐标点为 ５，且点 ｘ 到目标点的距离为 １５，点 ｘ ～ 到目标点的距 离为 ５。 比较可得，反向点靠近目标点。 ｘ 的反向坐 标点 ｘ ～ 的计算公式为 ｘ ～ ＝ ａ ＋ ｂ － ｘ 式中 ｘ∈［ａ，ｂ］，且为实数。 把上述定义应用到高维 空间可表示成定义 ２。 定义 ２ ［１４］ 在 Ｎ 维空间中的一个点 Ｐ 可表示 为 Ｐ ｘ１ ，ｘ２ ，…，ｘｎ ( ) ，其中 ｘ１ ，ｘ２ ，…，ｘｎ ∈Ｒ，且 ｘｉ ∈ ａｉ，ｂｉ [ ] ，∀ｉ ＝{１，２，…，ｎ} 。 则点 Ｐ 对应的反向点 Ｐ ～ 可表示为 Ｐ ～ （ｘ ～ １ ，ｘ ～ ２ ，…，ｘ ～ ｎ ），其中ｘｉ ～ 表示为 ｘ ～ ｉ ＝ ａｉ ＋ ｂｉ － ｘｉ 将定义 ２ 应用到优化过程中，则反向机制的优 化过程如定义 ３。 定义 ３ ［１４］ 根据定义 １ 和定义 ２，反向学习可 以描述为：假设 ｆ（ｘ）是已知问题的函数方程，ｎ 维空 间中的点 Ｐｉ（ｘ１ ，ｘ２ ，…，ｘｎ ）是函数方程 ｆ（ ｘ）的一个 解，且 ｘｉ∈ ａｉ，ｂｉ [ ] ，∀ｉ ＝ {１，２，…，ｎ} 。 则 Ｐｉ 的反向 点为 Ｐ ～ ｉ（ｘ ～ １ ，ｘ ～ ２ ，…，ｘ ～ ｎ ）。 计算 Ｐｉ 和 Ｐ ～ ｉ 在函数 ｆ（ ｘ） 中的函数值。 如果 ｆ（Ｐ ～ ｉ） ＞ｆ（Ｐｉ），则反向点 Ｐ ～ ｉ 代替 Ｐｉ；否则保留 Ｐｉ。 因此通过不断地计算点 Ｐｉ 与反向 点 Ｐ ～ ｉ 的 ｆ（ｘ）值选择其中最优值。 ３ 反向学习粒子群算法 基于反向学习策略的思想，本文提出一种改进 的粒 子 群 算 法 （ ｏｐｐｏｓｉｔｉｏｎ⁃ｂａｓｅｄ ｌｅａｒｎｉｎｇ ｉｍｐｒｏｖｅｄ ＰＳＯ， ＯＢＬＩＰＳＯ）。 本文采用反向学习策略时，将反 向学习策略应用到单个粒子中，而不是粒子群体 中，以便减小粒子迭代过程中的计算量。 性能测试 结果证明，改进的粒子群算法能抑制粒子早熟现 象，提高收敛效率。 下面介绍改进算法的主要机制 和流程。 ３．１ 初始化种群 粒子在问题空间中找到最优解的时间与粒子 初始化时在空间中的分布存在正比关系，距离最佳 位置近的粒子找到最优解的时间比距离最佳位置 远的粒子要快。 但是，粒子在问题空间中是随机分 布的，每一个粒子相对于最优解的位置都是未知的。 基于以上分析，在改进的粒子群算法初始化时 引入反向学习策略有助于粒子寻找最优解。 在初 始化时，首先，计算粒子的适应度值以及其反向粒 子适应度值，并对两者进行比较，选择适应度值较 好的粒子；其次，从种群中选择 Ｓ 个适应度值最好的 粒子作为初始种群。 ３．２ 迭代进化过程 在标准 ＰＳＯ 算法中，粒子在问题空间中选择另 一个粒子作为学习对象，根据式（１）、（２）进行移动。 但在粒子进化的过程中，粒子会发生早熟现象，导 致算法无法得到最优解。 由式（１） 可知，粒子的速 度受到惯性权重和学习因子的影响：惯性权重影响 着粒子的全局搜索和局部搜索能力，学习因子影响 粒子获取信息的能力。 为了找到问题最优解，粒子 在进化的过程中，其全局搜索能力和局部搜索能力 也应该随之发生变化，即从全局搜索渐变为局部搜 索，保证粒子可以寻找到问题的最优解。 同样，粒 子也应该逐渐增强社交能力，由“自我”学习逐渐向 “他人”学习过渡，以便获取更多有用的信息。 根据以上分析，粒子在寻优过程中，惯性权重 应该保持动态变化。 ω 取值较大时，粒子的全局搜 索能力较强；ω 取值较小时，粒子的局部搜索能力较 强。 由于粒子在寻优的过程中，会逐渐靠近最优 点，粒子的惯性权重应该随着寻优过程自适应变 化。 因此粒子的惯性权重更新公式为 ω ＝ ωｍａｘ － ωｍａｘ － ωｍｉｎ ( ) １ － ｄｉｓｔ ｉ ｍａｘ＿ｄｉｓｔ æ è ç ö ø ÷ 式中： ω ｍａｘ 和 ω ｍｉｎ 分别是粒子惯性权重的最大值和 最小值； ｄｉｓｔ ｉ 是第 ｉ 个粒子到全局最优粒子的欧几 里德距离； ｍａｘ＿ｄｉｓｔ 是粒子到全局最优粒子的最大 距离。 ｄｉｓｔ ｉ 和 ｍａｘ＿ｄｉｓｔ 表达式分别为［１５］ ｄｉｓｔ ｉ ＝ ∑ Ｄ ｄ ＝ １ ｇｂｅｓｔｄ ( － ｘｉ，ｄ ) １ ２ ｍａｘ＿ｄｉｓｔ ＝ ａｒｇｍａｘ ｄｉｓｔ ｉ ( ) ｉ 学习因子 ｃ１ 和 ｃ２ 控制粒子本身记忆与同伴记 忆之间的相对影响：ｃ１ 的值较小时，表现为自我认 知能力不足；ｃ２ 的值较小时，表现为社交能力不足。 为了保证在迭代过程中，粒子的自我认知和社交能 力能够因时而异， 因此， 粒子的学习因子更新公 式［１６］如下： ｃ１ ＝ ｃ１ｍａｘ × ｃ１ｍｉｎ ｃ１ｍａｘ æ è ç ö ø ÷ ｔ Ｔｍａｘ ( ) ·３０４· 智 能 系 统 学 报 第 １２ 卷

第3期 蒲兴成，等：基于改进粒子群算法的移动机器人多目标点路径规划 ·305· 在表2中，OBLIPS0算法在四测试函数上的平 C2=C2min 均值均小于其他3种算法的值，尤其是在Sphere函 式中：c1m和c2max以及c1mn和c2an分别是学习因子c, 数和Rastrigin函数中。从表2中数据可知， 和c,的最大值和最小值：t是当前的迭代次数：T OBLIPS0算法具有更好的收敛性，得到的解更优。 是最大迭代次数。 表3中的数据反映出改进算法的稳定性。OBLIPSO 3.3算法实现流程 算法与IAPS0算法、IPSO算法和WPSO算法对比， 1)首先初始化种群P(S),包括粒子的位置x 在稳定性上表现得更好。 和速度y,i=1,2,…,S,S是种群的大小，初始化惯 表2平均最优值结果对比 性权重ω以及学习因子c,和c,等参数。 Table 2 The comparison of average best values 2)在速度和位置规定的范围内根据式(1)、(2) 函数OBLIPSO IAPSO IPSO WPSO 更新第i个粒子的速度"：和位置x,o 0 0.1327900.020476 0.034939 3)计算第i个粒子的适应度值∫。 0 0.0663790.066331 0.298488 4)a,=min(x:)。 5 0.0021530.0316920.017342 0.018080 5)b:=max(x:)。 f 0.0032730.0053280.006179 0.017561 6)计算第i个粒子的位置和速度反向解：x, a:+b:-Xio 表3标准方差结果对比 7)计算第i个粒子反向解的适应度值了：。 Table 3 The comparison of standard deviation 函数 OBLIPSO IAPSO IPSO WPSO 8)比较f和子：的大小，如果了：<f,则x:=x, 0 0.7147750.009423 0.006733 f=fio 9)从最优适应度值中选出S个适应度值最好 0 0.2481740.248186 0.455948 的粒子组成初始化种群。 5 0.0044180.0875050.021595 0.019151 10)接下来同粒子群算法基本流程。 f40.00456000.0046990.004650 0.032801 11)算法满足结束条件，结束算法过程。 由表2和表3数据可得：反向学习策略提高了 4 实验结果与分析 种群的多样性，增加了粒子寻优成功概率，节省了 4.1 OBLIPS0性能测试 粒子寻优时间：线性变化的惯性权重保障了粒子从 为了验证改进粒子群算法的性能是否得到改 全局搜索到局部搜索的线性转换，抑制了粒子早熟 进，笔者将反向学习的粒子群算法与其他改进算 现象：学习因子的变化保证了粒子能够充分完成自 法[15,7-1]在4个适应度函数上进行对比。这4个适 我学习和社交行为，提高了粒子的收敛速度。 应度函数分别为Sphere函数、Rastrigin函数、 4.2路径规划仿真实验 Grewank函数、Schaffer函数，测试函数参数设置如 为了验证新方法的实用性及有效性，笔者将该 表1所示。 方法在仿真环境下进行实验。仿真实验环境设置 表1测试函数参数设置 在18×16的二维矩形空间内，并设置成简单环境和 Table 1 The parameter setting of test function 复杂环境。在环境中有不规则的障碍物，起始点位 函数 取值范围 最优点 最优解 置使用方形表示，目标点处用五角形表示。 1)第1次实验中，OBLIPS0算法的参数设置 Sphere(f) [-100,100] (0,0) 0 为：0x=0.9,0mn=0.4,S=10,c1mm=2.75,c2mx= Rastrigin() [-5.12,5.12] (0,0) 0 2.25,c1n=1.25,c2in=0.5,心=1.9,0m=0,斥力场 Grewank() [-600,600] (0.0) 0 中的安全距离dn=2,k,=2.7,入=0.25,4=0.25，最大 Schaffer(f) [-100,100] (0,0) 0 迭代次数为100。图4(a)给出了在简单环境下的 OBLIPS0算法参数设置为：粒子群大小为40， OBLIPSO作用的移动机器人多目标点移动轨迹。 空间维度为2，w=[0.4,0.9],c1=[1.25,2.75],c2= 图4(b)是IAPS0作用的运动轨迹。图4(c)是 [0.5,2.25],最大迭代次数为100。 PS0作用的运动轨迹

ｃ２ ＝ ｃ２ｍｉｎ × ｃ２ｍａｘ ｃ２ｍｉｎ æ è ç ö ø ÷ ｔ Ｔｍａｘ ( ) 式中：ｃ１ｍａｘ和 ｃ２ｍａｘ以及 ｃ１ｍｉｎ和 ｃ２ｍｉｎ分别是学习因子 ｃ１ 和 ｃ２ 的最大值和最小值；ｔ 是当前的迭代次数；Ｔｍａｘ 是最大迭代次数。 ３．３ 算法实现流程 １）首先初始化种群 Ｐ（ Ｓ），包括粒子的位置 ｘｉ 和速度 ｖｉ，ｉ ＝ １，２，…，Ｓ，Ｓ 是种群的大小，初始化惯 性权重 ω 以及学习因子 ｃ１ 和 ｃ２ 等参数。 ２）在速度和位置规定的范围内根据式（１）、（２） 更新第 ｉ 个粒子的速度 ｖｉ 和位置 ｘｉ。 ３）计算第 ｉ 个粒子的适应度值 ｆ ｉ。 ４）ａｉ ＝ｍｉｎ（ｘｉ）。 ５）ｂｉ ＝ｍａｘ（ｘｉ）。 ６）计算第 ｉ 个粒子的位置和速度反向解： ｘ ～ ｉ ＝ ａｉ ＋ｂｉ －ｘｉ。 ７）计算第 ｉ 个粒子反向解的适应度值 ｆ ～ ｉ。 ８）比较 ｆ ｉ 和 ｆ ～ ｉ 的大小，如果 ｆ ～ ｉ ＜ｆ ｉ，则 ｘｉ ＝ ｘ ～ ｉ， ｆ ｉ ＝ ｆ ～ ｉ。 ９）从最优适应度值中选出 Ｓ 个适应度值最好 的粒子组成初始化种群。 １０）接下来同粒子群算法基本流程。 １１）算法满足结束条件，结束算法过程。 ４ 实验结果与分析 ４．１ ＯＢＬＩＰＳＯ 性能测试 为了验证改进粒子群算法的性能是否得到改 进，笔者将反向学习的粒子群算法与其他改进算 法［１５，１７－１８］在 ４ 个适应度函数上进行对比。 这 ４ 个适 应 度 函 数 分 别 为 Ｓｐｈｅｒｅ 函 数、 Ｒａｓｔｒｉｇｉｎ 函 数、 Ｇｒｅｗａｎｋ 函数、Ｓｃｈａｆｆｅｒ 函数，测试函数参数设置如 表 １ 所示。 表 １ 测试函数参数设置 Ｔａｂｌｅ １ Ｔｈｅ ｐａｒａｍｅｔｅｒ ｓｅｔｔｉｎｇ ｏｆ ｔｅｓｔ ｆｕｎｃｔｉｏｎ 函数 取值范围 最优点 最优解 Ｓｐｈｅｒｅ（ｆ １ ） ［－１００，１００］ （０，０） ０ Ｒａｓｔｒｉｇｉｎ（ｆ ２ ） ［－５．１２，５．１２］ （０，０） ０ Ｇｒｅｗａｎｋ（ｆ ３ ） ［－６００，６００］ （０，０） ０ Ｓｃｈａｆｆｅｒ（ｆ ４ ） ［－１００，１００］ （０，０） ０ ＯＢＬＩＰＳＯ 算法参数设置为：粒子群大小为 ４０， 空间维度为 ２，ω ＝ [０．４，０．９] ，ｃ１ ＝ [１．２５，２．７５] ，ｃ２ ＝ [０．５，２．２５] ，最大迭代次数为 １００。 在表 ２ 中，ＯＢＬＩＰＳＯ 算法在四测试函数上的平 均值均小于其他 ３ 种算法的值，尤其是在 Ｓｐｈｅｒｅ 函 数和 Ｒａｓｔｒｉｇｉｎ 函 数 中。 从 表 ２ 中 数 据 可 知， ＯＢＬＩＰＳＯ 算法具有更好的收敛性，得到的解更优。 表 ３ 中的数据反映出改进算法的稳定性。 ＯＢＬＩＰＳＯ 算法与 ＩＡＰＳＯ 算法、ＩＰＳＯ 算法和 ＷＰＳＯ 算法对比， 在稳定性上表现得更好。 表 ２ 平均最优值结果对比 Ｔａｂｌｅ ２ Ｔｈｅ ｃｏｍｐａｒｉｓｏｎ ｏｆ ａｖｅｒａｇｅ ｂｅｓｔ ｖａｌｕｅｓ 函数 ＯＢＬＩＰＳＯ ＩＡＰＳＯ ＩＰＳＯ ＷＰＳＯ ｆ １ ０ ０．１３２ ７９０ ０．０２０ ４７６ ０．０３４ ９３９ ｆ ２ ０ ０．０６６ ３７９ ０．０６６ ３３１ ０．２９８ ４８８ ｆ ２ ０．００２ １５３ ０．０３１ ６９２ ０．０１７ ３４２ ０．０１８ ０８０ ｆ ４ ０．００３ ２７３ ０．００５ ３２８ ０．００６ １７９ ０．０１７ ５６１ 表 ３ 标准方差结果对比 Ｔａｂｌｅ ３ Ｔｈｅ ｃｏｍｐａｒｉｓｏｎ ｏｆ ｓｔａｎｄａｒｄ ｄｅｖｉａｔｉｏｎ 函数 ＯＢＬＩＰＳＯ ＩＡＰＳＯ ＩＰＳＯ ＷＰＳＯ ｆ １ ０ ０．７１４ ７７５ ０．００９ ４２３ ０．００６ ７３３ ｆ ２ ０ ０．２４８ １７４ ０．２４８ １８６ ０．４５５ ９４８ ｆ ２ ０．００４ ４１８ ０．０８７ ５０５ ０．０２１ ５９５ ０．０１９ １５１ ｆ ４ ０．００４ ５６０ ０ ０．００４ ６９９ ０．００４ ６５０ ０．０３２ ８０１ 由表 ２ 和表 ３ 数据可得：反向学习策略提高了 种群的多样性，增加了粒子寻优成功概率，节省了 粒子寻优时间；线性变化的惯性权重保障了粒子从 全局搜索到局部搜索的线性转换，抑制了粒子早熟 现象；学习因子的变化保证了粒子能够充分完成自 我学习和社交行为，提高了粒子的收敛速度。 ４．２ 路径规划仿真实验 为了验证新方法的实用性及有效性，笔者将该 方法在仿真环境下进行实验。 仿真实验环境设置 在 １８×１６ 的二维矩形空间内，并设置成简单环境和 复杂环境。 在环境中有不规则的障碍物，起始点位 置使用方形表示，目标点处用五角形表示。 １） 第 １ 次实验中，ＯＢＬＩＰＳＯ 算法的参数设置 为：ωｍａｘ ＝ ０． ９，ωｍｉｎ ＝ ０． ４，Ｓ ＝ １０，ｃ１ｍａｘ ＝ ２． ７５，ｃ２ｍａｘ ＝ ２．２５，ｃ１ｍｉｎ ＝ １．２５，ｃ２ｍｉｎ ＝ ０．５，ｖｍａｘ ＝ １．９，ｖｍｉｎ ＝ ０，斥力场 中的安全距离 ｄｍ ＝ ２，ｋｒ ＝ ２．７，λ ＝ ０．２５，μ ＝ ０．２５，最大 迭代次数为 １００。 图 ４（ ａ） 给出了在简单环境下的 ＯＢＬＩＰＳＯ 作用的移动机器人多目标点移动轨迹。 图 ４（ ｂ） 是 ＩＡＰＳＯ 作用的运动轨迹。 图 ４ （ ｃ） 是 ＩＰＳＯ 作用的运动轨迹。 第 ３ 期 蒲兴成，等：基于改进粒子群算法的移动机器人多目标点路径规划 ·３０５·

·306 智能系统学报 第12卷 由图4框中路径轨迹可知：在目标点3到目标 点4和目标点6到目标点7之间，OBLIPS0和 IAPS0的避障性能上优于PS0,在经过目标点4和 目标点5时，OBLIPSO的路径较为平滑。而且 642086420 OBLIPSO0在迭代72次左右时成功完成路径规划。 2)在第2次实验中，实验环境相对第1次实验 而言，增加了障碍物以及目标点的个数。实验参数 2468.101214618g 设置如下：”=20，最大迭代次数为300，其余参数 与第1次实验中参数相同。由于环境复杂度的增 加，相对第1次实验而言，粒子收敛速度变慢。图 5(a)是在复杂环境下的OBLIPS0获得的移动机器 (a)OBLIPSO路径轨迹 人多目标点运动轨迹。图5(b)是IAPS0获得的运 动轨迹。图5(c)是PS0作用的运动轨迹。 6420864 12 8.1012T41618 x/m 681012141618 x/m (b)IAPSO路径轨透 (a)OBLIPSO路径轨迹 6420 1 14 8642 日 右8101241618 6 4 x/m 6 /mo 12 4 16 18 82 (c)IPSO路径轨迹 图4简单环境下的优化过程 (b)IAPSO路径轨迹 Fig.4 The motion process in the first environment

（ａ）ＯＢＬＩＰＳＯ 路径轨迹 （ｂ） ＩＡＰＳＯ 路径轨迹 （ｃ）ＩＰＳＯ 路径轨迹 图 ４ 简单环境下的优化过程 Ｆｉｇ．４ Ｔｈｅ ｍｏｔｉｏｎ ｐｒｏｃｅｓｓ ｉｎ ｔｈｅ ｆｉｒｓｔ ｅｎｖｉｒｏｎｍｅｎｔ 由图 ４ 框中路径轨迹可知：在目标点 ３ 到目标 点 ４ 和目标点 ６ 到目标点 ７ 之 间， ＯＢＬＩＰＳＯ 和 ＩＡＰＳＯ 的避障性能上优于 ＩＰＳＯ，在经过目标点 ４ 和 目标 点 ５ 时， ＯＢＬＩＰＳＯ 的 路 径 较 为 平 滑。 而 且 ＯＢＬＩＰＳＯ 在迭代 ７２ 次左右时成功完成路径规划。 ２）在第 ２ 次实验中，实验环境相对第 １ 次实验 而言，增加了障碍物以及目标点的个数。 实验参数 设置如下：ｖｍａｘ ＝ ２０，最大迭代次数为 ３００，其余参数 与第 １ 次实验中参数相同。 由于环境复杂度的增 加，相对第 １ 次实验而言，粒子收敛速度变慢。 图 ５（ａ）是在复杂环境下的 ＯＢＬＩＰＳＯ 获得的移动机器 人多目标点运动轨迹。 图 ５（ ｂ）是 ＩＡＰＳＯ 获得的运 动轨迹。 图 ５（ｃ）是 ＩＰＳＯ 作用的运动轨迹。 （ａ）ＯＢＬＩＰＳＯ 路径轨迹 （ｂ）ＩＡＰＳＯ 路径轨迹 ·３０６· 智 能 系 统 学 报 第 １２ 卷

第3期 蒲兴成，等：基于改进粒子群算法的移动机器人多目标点路径规划 ·307· 距离长于IAPSO,但其比PSO算法短：在路径安全 性方面，OBLIPS0算法要优于其他两种对比算法。 由于在设计路径规划目标函数时不仅考虑了路径 最短性问题，也考虑到了其安全性的问题，因此综 合两种环境下实验结果可以得出OBLIPSO算法综 14 合性能强于IAPS0算法和PSO算法。 图6给出的是简单环境下OBLIPS0算法、 5 IAPS0算法和PSO算法在目标函数上的收敛曲线 对比。从图6中曲线可以得出，在迭代72次左右 681012146i8 时，OBLIPS0算法可在多目标点路径规划中寻到最 优路径，而IAPS0算法和PS0算法在迭代1O0次 时仍未获得OBLIPSO算法的收敛值。 70 OBLIPSO (c)IPS0路径轨迹 65 …e…IAPSO -IPSO 图5复杂环境下迭代过程 60 Fig.5 The iteration process in complicated environment 对比图5中3条轨迹可知，随着障碍物和目标 50 点增加，3种算法都满足了路径的可达性。根据图5 框中的路径轨迹可知，在经过目标点6和目标点9 0 20 4060 80100 时，OBLIPSO算法规划的路径相比于IAPSO和 迭代次数 PSO算法规划的路径更为平滑。OBLIPS0算法规 图6 OBLIPSO与IAPSO和PSO目标函数收敛曲线比较 划的路径在目标点5与目标点10之间相比于 Fig.6 The convergence comparison of OBLIPSO with IAPSO和PS0算法规划的路径安全性更好， IAPSO and IPSO OBLIPS0移动距离较短（见表4），而且其规划的路 综上所述，在相同任务下，OBLIPSO算法的综 径安全性最好。 合性能优于IAPSO算法和PS0算法。随着任务复 3)路径规划性能对比 杂度的变化，OBLIPSO算法能够有效且较好地完成 重复10次上述两种任务的实验，取其平均值。 移动距离和时间消耗以及安全性上表现得更好，表 移动机器人多目标点路径规划的时间消耗和移动 明了OBLIPSO算法能够有效且较好地完成移动机 距离性能对比如表4所示。 器人多目标点路径规划上有效性。 表4路径性能对比 4.3实际环境下路径规划 Table 4 The performance comparison of path 为了验证OBLIPSO算法在实际应用中的有效 环境 算法 移动距离/m 消耗时间/s 性，笔者将在实际环境下对OBLIPS0算法进行实验 OBLIPSO 40.943 8.866 验证。实验环境设置为重庆邮电大学自动化学院 简单 IAPSO 41.749 10.257 环境 办公楼一楼。实验平台为先锋3机器人，软件背景 IPSO 42.865 10.625 为ROS(robot operation system)i9-)。实验中设置 44.942 了3个目标点，机器人从目标点1出发经过两个目 OBLIPSO 18.583 复杂 标点，最后返回目标点1。 IAPSO 43.127 23.265 环境 图7中显示的是机器人在无障碍环境中完成的 IPSO 45.336 25.186 多目标点路径规划。图7(a)为OBLIPS0算法规划 从表4数据中可以得出，随着任务复杂度的增 的路径，图7(b)为IAPS0算法规划的路径。由图7 加，OBLIPS0、IAPSO和PS0在时间消耗上也在增 可知：机器人从目标点2到目标点3的过程中， 加，任务越复杂，用时越多。但在进行相同任务时， OBLIPSO算法能够保证机器人与墙体保持安全距 OBLIPSO用时比IAPSO和PS0少；在移动距离方 离且路径平滑：IAPSO算法虽然保证了机器人与墙 面，简单任务时，OBLIPS0的移动距离比其他两种 的安全距离，但由于机器人远离墙体移动造成了路 对比算法短，在复杂任务时，虽然OBLIPSO的移动 径的交叉，如图7中方框所示

（ｃ） ＩＰＳＯ 路径轨迹 图 ５ 复杂环境下迭代过程 Ｆｉｇ．５ Ｔｈｅ ｉｔｅｒａｔｉｏｎ ｐｒｏｃｅｓｓ ｉｎ ｃｏｍｐｌｉｃａｔｅｄ ｅｎｖｉｒｏｎｍｅｎｔ 对比图 ５ 中 ３ 条轨迹可知，随着障碍物和目标 点增加，３ 种算法都满足了路径的可达性。 根据图 ５ 框中的路径轨迹可知，在经过目标点 ６ 和目标点 ９ 时，ＯＢＬＩＰＳＯ 算 法 规 划 的 路 径 相 比 于 ＩＡＰＳＯ 和 ＩＰＳＯ 算法规划的路径更为平滑。 ＯＢＬＩＰＳＯ 算法规 划的路径在目标点 ５ 与目标点 １０ 之间相 比 于 ＩＡＰＳＯ 和 ＩＰＳＯ 算 法 规 划 的 路 径 安 全 性 更 好， ＯＢＬＩＰＳＯ 移动距离较短（见表 ４），而且其规划的路 径安全性最好。 ３）路径规划性能对比 重复 １０ 次上述两种任务的实验，取其平均值。 移动机器人多目标点路径规划的时间消耗和移动 距离性能对比如表 ４ 所示。 表 ４ 路径性能对比 Ｔａｂｌｅ ４ Ｔｈｅ ｐｅｒｆｏｒｍａｎｃｅ ｃｏｍｐａｒｉｓｏｎ ｏｆ ｐａｔｈ 环境 算法 移动距离／ ｍ 消耗时间／ ｓ 简单 环境 ＯＢＬＩＰＳＯ ４０．９４３ ８．８６６ ＩＡＰＳＯ ４１．７４９ １０．２５７ ＩＰＳＯ ４２．８６５ １０．６２５ 复杂 环境 ＯＢＬＩＰＳＯ ４４．９４２ １８．５８３ ＩＡＰＳＯ ４３．１２７ ２３．２６５ ＩＰＳＯ ４５．３３６ ２５．１８６ 从表 ４ 数据中可以得出，随着任务复杂度的增 加，ＯＢＬＩＰＳＯ、ＩＡＰＳＯ 和 ＩＰＳＯ 在时间消耗上也在增 加，任务越复杂，用时越多。 但在进行相同任务时， ＯＢＬＩＰＳＯ 用时比 ＩＡＰＳＯ 和 ＩＰＳＯ 少；在移动距离方 面，简单任务时，ＯＢＬＩＰＳＯ 的移动距离比其他两种 对比算法短，在复杂任务时，虽然 ＯＢＬＩＰＳＯ 的移动 距离长于 ＩＡＰＳＯ，但其比 ＩＰＳＯ 算法短；在路径安全 性方面，ＯＢＬＩＰＳＯ 算法要优于其他两种对比算法。 由于在设计路径规划目标函数时不仅考虑了路径 最短性问题，也考虑到了其安全性的问题，因此综 合两种环境下实验结果可以得出 ＯＢＬＩＰＳＯ 算法综 合性能强于 ＩＡＰＳＯ 算法和 ＩＰＳＯ 算法。 图 ６ 给 出 的 是 简 单 环 境 下 ＯＢＬＩＰＳＯ 算 法、 ＩＡＰＳＯ 算法和 ＩＰＳＯ 算法在目标函数上的收敛曲线 对比。 从图 ６ 中曲线可以得出，在迭代 ７２ 次左右 时，ＯＢＬＩＰＳＯ 算法可在多目标点路径规划中寻到最 优路径，而 ＩＡＰＳＯ 算法和 ＩＰＳＯ 算法在迭代 １００ 次 时仍未获得 ＯＢＬＩＰＳＯ 算法的收敛值。 图 ６ ＯＢＬＩＰＳＯ 与 ＩＡＰＳＯ 和 ＩＰＳＯ 目标函数收敛曲线比较 Ｆｉｇ．６ Ｔｈｅ ｃｏｎｖｅｒｇｅｎｃｅ ｃｏｍｐａｒｉｓｏｎ ｏｆ ＯＢＬＩＰＳＯ ｗｉｔｈ ＩＡＰＳＯ ａｎｄ ＩＰＳＯ 综上所述，在相同任务下，ＯＢＬＩＰＳＯ 算法的综 合性能优于 ＩＡＰＳＯ 算法和 ＩＰＳＯ 算法。 随着任务复 杂度的变化，ＯＢＬＩＰＳＯ 算法能够有效且较好地完成 移动距离和时间消耗以及安全性上表现得更好，表 明了 ＯＢＬＩＰＳＯ 算法能够有效且较好地完成移动机 器人多目标点路径规划上有效性。 ４．３ 实际环境下路径规划 为了验证 ＯＢＬＩＰＳＯ 算法在实际应用中的有效 性，笔者将在实际环境下对 ＯＢＬＩＰＳＯ 算法进行实验 验证。 实验环境设置为重庆邮电大学自动化学院 办公楼一楼。 实验平台为先锋 ３ 机器人，软件背景 为 ＲＯＳ（ ｒｏｂｏｔ ｏｐｅｒａｔｉｏｎ ｓｙｓｔｅｍ） ［１９－２１］ 。 实验中设置 了 ３ 个目标点，机器人从目标点 １ 出发经过两个目 标点，最后返回目标点 １。 图 ７ 中显示的是机器人在无障碍环境中完成的 多目标点路径规划。 图 ７（ａ）为 ＯＢＬＩＰＳＯ 算法规划 的路径，图 ７（ｂ）为 ＩＡＰＳＯ 算法规划的路径。 由图 ７ 可知：机器人从目标点 ２ 到目标点 ３ 的过程中， ＯＢＬＩＰＳＯ 算法能够保证机器人与墙体保持安全距 离且路径平滑；ＩＡＰＳＯ 算法虽然保证了机器人与墙 的安全距离，但由于机器人远离墙体移动造成了路 径的交叉，如图 ７ 中方框所示。 第 ３ 期 蒲兴成，等：基于改进粒子群算法的移动机器人多目标点路径规划 ·３０７·

.308. 智能系统学报 第12卷 (a)OBLIPSO路径轨迹 (b)IAPS0路径轨迹 图8机器人在障碍环境下的移动过程 Fig.8 The motion process of robot in the obstacle environment 表5真实环境下路径性能对比 Table 5 The performance comparison of path in real environment 无障碍 有障碍 指标 (OBLIPSO/IAPSO) (OBLIPSO/IAPSO) 时间/s 114/114 186/216 (b)IAPS0路径轨迹 距离/m 20.1/20.1 19.5/20 图7机器人在无障碍环境下的移动过程 Fig.7 The motion process of robot in barrier-free 5 结束语 environment 本文提出了一种结合ACO算法和OBLIPSO算 为了进一步验证OBLIPS0算法的有效性，环境 法的移动机器人多目标点路径规划新方法，并通过 中设置了障碍物，并改变了目标点3的位置，如图8 实验验证了新方法的可行性。AC0算法在TSP问 所示。图8表示机器人在含有障碍物的环境下实现 题上表现出较好的优越性，因此AC0算法适用于移 的多目标点路径规划。图8(a)为OBLIPSO算法规 动机器人的目标点选择问题。OBLIPSO算法不仅 继承了PS0算法计算简单的特点，而且在初始化时 划的路径，图8(b)为IAPS0算法规划的路径。由 引入反向学习策略，保证了粒子的多样性。在迭代 图8可知：在含有障碍物的环境中，机器人在两种算 过程中，OBLIPS0算法抑制了粒子的早熟，提高了 法下都能够避开障碍物完成路径规划，但是机器人 收敛速度。采用4个适应度函数对OBLIPS0算法 从目标点2到目标点3的过程中，OBLIPS0算法能 进行性能评估，取得了良好的测试结果。仿真实验 够保证机器人与障碍物保持安全距离并且路径平 与真实环境下实验结果表明提出的新方法是一种 滑；IAPS0算法在移动过程中，虽然机器人与障碍物 有效的多目标点路径规划方法。将本文提出的新 保持了安全的距离，但由于其路径的交叉导致移动 方法应用到动态环境下的移动机器人的多目标点 轨迹较长，如图8中方框所示。 路径规划是下一步的研究内容。 表5为两次实验重复10次取得的时间和路径 参考文献： 长度的平均值。由表5可知：在障碍环境下， [1]杨兴，张亚，杨巍，等.室内移动机器人路径规划研究 OBLIPSO算法可以实现机器人多目标点的路径规 [J刀.科学技术与工程，2016,16(15)：234-238. 划，并且消耗的时间较少。 YANG Xing,ZHANG Ya,YANG Wei,et al.Research on path planning of indoor mobile robot [J].Science technology and engineering,2016,16(15):234-238. [2]Ammar A,Bennaceur H,Chaari I,et al.Relaxed Dijkstra and A'with linear complexity for robot path planning problems in large-scale grid environments[J].Soft computing,2016.20 (10):4149-4171. [3]杜鹏桢，唐振民，孙研.一种面向对象的多角色蚁群算 法及其TSP问题求解[J].控制与决策，2014(10)： 1729-1736. DU Pengzhen,TANG Zhenmin,SUN Yan.An object-orien- (a)OBLIPS0路径轨迹 ted multi-role ant colony optimization algorithm for solving

（ａ）ＯＢＬＩＰＳＯ 路径轨迹 （ｂ）ＩＡＰＳＯ 路径轨迹 图 ７ 机器人在无障碍环境下的移动过程 Ｆｉｇ．７ Ｔｈｅ ｍｏｔｉｏｎ ｐｒｏｃｅｓｓ ｏｆ ｒｏｂｏｔ ｉｎ ｂａｒｒｉｅｒ⁃ｆｒｅｅ ｅｎｖｉｒｏｎｍｅｎｔ 为了进一步验证 ＯＢＬＩＰＳＯ 算法的有效性，环境 中设置了障碍物，并改变了目标点 ３ 的位置，如图 ８ 所示。 图 ８ 表示机器人在含有障碍物的环境下实现 的多目标点路径规划。 图 ８（ａ）为 ＯＢＬＩＰＳＯ 算法规 划的路径，图 ８（ ｂ） 为 ＩＡＰＳＯ 算法规划的路径。 由 图 ８ 可知：在含有障碍物的环境中，机器人在两种算 法下都能够避开障碍物完成路径规划，但是机器人 从目标点 ２ 到目标点 ３ 的过程中，ＯＢＬＩＰＳＯ 算法能 够保证机器人与障碍物保持安全距离并且路径平 滑；ＩＡＰＳＯ 算法在移动过程中，虽然机器人与障碍物 保持了安全的距离，但由于其路径的交叉导致移动 轨迹较长，如图 ８ 中方框所示。 表 ５ 为两次实验重复 １０ 次取得的时间和路径 长度 的 平 均 值。 由 表 ５ 可 知： 在 障 碍 环 境 下， ＯＢＬＩＰＳＯ 算法可以实现机器人多目标点的路径规 划，并且消耗的时间较少。 （ａ）ＯＢＬＩＰＳＯ 路径轨迹 （ｂ）ＩＡＰＳＯ 路径轨迹 图 ８ 机器人在障碍环境下的移动过程 Ｆｉｇ． ８ Ｔｈｅ ｍｏｔｉｏｎ ｐｒｏｃｅｓｓ ｏｆ ｒｏｂｏｔ ｉｎ ｔｈｅ ｏｂｓｔａｃｌｅ ｅｎｖｉｒｏｎｍｅｎｔ 表 ５ 真实环境下路径性能对比 Ｔａｂｌｅ ５ Ｔｈｅ ｐｅｒｆｏｒｍａｎｃｅ ｃｏｍｐａｒｉｓｏｎ ｏｆ ｐａｔｈ ｉｎ ｒｅａｌ ｅｎｖｉｒｏｎｍｅｎｔ 指标 无障碍 有障碍 （ＯＢＬＩＰＳＯ／ ＩＡＰＳＯ） （ＯＢＬＩＰＳＯ／ ＩＡＰＳＯ） 时间／ ｓ １１４ ／ １１４ １８６ ／ ２１６ 距离／ ｍ ２０．１ ／ ２０．１ １９．５ ／ ２０ ５ 结束语 本文提出了一种结合 ＡＣＯ 算法和 ＯＢＬＩＰＳＯ 算 法的移动机器人多目标点路径规划新方法，并通过 实验验证了新方法的可行性。 ＡＣＯ 算法在 ＴＳＰ 问 题上表现出较好的优越性，因此 ＡＣＯ 算法适用于移 动机器人的目标点选择问题。 ＯＢＬＩＰＳＯ 算法不仅 继承了 ＰＳＯ 算法计算简单的特点，而且在初始化时 引入反向学习策略，保证了粒子的多样性。 在迭代 过程中，ＯＢＬＩＰＳＯ 算法抑制了粒子的早熟，提高了 收敛速度。 采用 ４ 个适应度函数对 ＯＢＬＩＰＳＯ 算法 进行性能评估，取得了良好的测试结果。 仿真实验 与真实环境下实验结果表明提出的新方法是一种 有效的多目标点路径规划方法。 将本文提出的新 方法应用到动态环境下的移动机器人的多目标点 路径规划是下一步的研究内容。 参考文献： ［１］杨兴， 张亚， 杨巍，等． 室内移动机器人路径规划研究 ［Ｊ］． 科学技术与工程， ２０１６， １６（１５）：２３４－２３８． ＹＡＮＧ Ｘｉｎｇ， ＺＨＡＮＧ Ｙａ， ＹＡＮＧ Ｗｅｉ， ｅｔ ａｌ．Ｒｅｓｅａｒｃｈ ｏｎ ｐａｔｈ ｐｌａｎｎｉｎｇ ｏｆ ｉｎｄｏｏｒ ｍｏｂｉｌｅ ｒｏｂｏｔ ［ Ｊ ］． Ｓｃｉｅｎｃｅ ｔｅｃｈｎｏｌｏｇｙ ａｎｄ ｅｎｇｉｎｅｅｒｉｎｇ， ２０１６， １６ （１５）： ２３４－２３８． ［２］Ａｍｍａｒ Ａ， Ｂｅｎｎａｃｅｕｒ Ｈ， Ｃｈâａｒｉ Ｉ， ｅｔ ａｌ． Ｒｅｌａｘｅｄ Ｄｉｊｋｓｔｒａ ａｎｄ Ａ ∗ ｗｉｔｈ ｌｉｎｅａｒ ｃｏｍｐｌｅｘｉｔｙ ｆｏｒ ｒｏｂｏｔ ｐａｔｈ ｐｌａｎｎｉｎｇ ｐｒｏｂｌｅｍｓ ｉｎ ｌａｒｇｅ⁃ｓｃａｌｅ ｇｒｉｄ ｅｎｖｉｒｏｎｍｅｎｔｓ ［Ｊ］． Ｓｏｆｔ ｃｏｍｐｕｔｉｎｇ， ２０１６， ２０ （１０）：４１４９－４１７１． ［３］杜鹏桢， 唐振民， 孙研． 一种面向对象的多角色蚁群算 法及其 ＴＳＰ 问题求解 ［ Ｊ］． 控制与决策， ２０１４ （ １０）： １７２９－１７３６． ＤＵ Ｐｅｎｇｚｈｅｎ， ＴＡＮＧ Ｚｈｅｎｍｉｎ， ＳＵＮ Ｙａｎ． Ａｎ ｏｂｊｅｃｔ⁃ｏｒｉｅｎ⁃ ｔｅｄ ｍｕｌｔｉ⁃ｒｏｌｅ ａｎｔ ｃｏｌｏｎｙ ｏｐｔｉｍｉｚａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｓｏｌｖｉｎｇ ·３０８· 智 能 系 统 学 报 第 １２ 卷

第3期 蒲兴成，等：基于改进粒子群算法的移动机器人多目标点路径规划 ·309. TSP problem J].Control and decision,2014 (10): of the 2010 International Joint Conference on Neural Net- 1729-1736. works (IJCNN).Barcelona:IEEE,2010. [4]AGRAWAL R K,BAWANE N G.Multiobjective PSO based [15 SURESH K,GHOSH S,KUNDU D,et al.Inertia- adaption of neural network topology for pixel classification in adaptive particle swarm optimizer for improved global satellite imagery [J].Applied soft computing,2015,28 search[C//Proceedings of Eighth International Conference on (C):217-225. Intelligent Systems Design and Applications.Kaohsiung: [5]DAS P K,BEHERA H S,PANIGRAHI B K.Intelligent-based IEEE,2008:253-258. multi-robot path planning inspired by improved classical Q- [16]姜建国，叶华，刘慧敏，等.融合快速信息交流和局部 learning and improved particle swarm optimization with 搜索的粒子群算法[J].哈尔滨工程大学学报，2015， perturbed velocity[].Engineering science and technology,an 36(5):687-691 international journal,2015,19(1):651-669. JIANG Jianguo,YE Hua,LIU Huimin,et al.Particle [6]YANG Mao,LI Chunzhe.Path planning and tracking for swarm optimization method with combination of rapid infor- multi-robot system based on improved PSO algorithm[C]/ mation communication and local search [J].Journal of Proceedings of 2011 Intemational Conference on Mechatronic Harbin engineering university,2015,36(5):687-691. Science,Electric Engineering and Computer(MEC).Jilin: [17]GAO Bingkun,REN Xiuju,XU Mingzi.An improved par- EEE,2011:1667-1670. ticle swarm algorithm and its application[].Procedia en- [7]WANG Mingming,LUO Jianjun,WALTER U.Trajectory gineering,2011,15:2444-2448. planning of free-floating space robot using particle swarm op- [18]许少华，李新幸.一种自适应改变惯性权重的粒子群算 timization PSO )J].Acta astronautica,2015,112: 法[J].科学技术与工程，2012,12(9)：2205-2208. 77-88 XU Shaohua,LI Xinxing.An adaptive changed inertia [8]张万绪，张向兰，李莹.基于改进粒子群算法的智能机 weight particle swarm algorithm J].Science technology 器人路径规划[J].计算机应用，2014,34(2)： and engineering,.2012,12(9):2205-2208. 510-513. [19]张建伟，张立伟，胡颖，等.开源机器人操作系统： ZHANG Wanxu,ZHANG Xianglan,LI Ying.Path planning ROS[M].北京：科学出版社，2012. for intelligent robots based on improved particle swarm opti- [20 COUSINS S,GERKEY B,CONLEY K,et al.Sharing mization algorithm[].Journal of computer applications, Software with ROS[J].IEEE robotics automation maga- 2014,34(2):510-513 zine,2010,17(2):12-14. [9]王娟，吴宪祥，郭宝龙.基于改进粒子群优化算法的移 [21]ZAMAN S.SLANY W,STEINBAUER G.ROS-based 动机器人路径规划[J].计算机工程与应用，2012,48 mapping,localization and autonomous navigation using a (15):240-244. Pioneer 3-DX robot and their relevant issues[C]//Pro- WANG Juan,WU Xianxiang,GUO Baolong.Robot path ceedings of 2011 Saudi International Electronics,Commu- planning using improved particle swarm optimization[J]. nications and Photonics Conference (SIECPC).Riyadh: Computer engineering and applications,2012,48(15): EEE,2011:1-5. 240-244 作者简介： [10]张勇，陈玲，徐小龙，等.基于PSO-GA混合算法时间 蒲兴成.男，1973年生，副教授，博 优化的旅行商问题研究[J].计算机应用研究，2015. 士，主要研究方向为非线性系统、随机 32(12):3613-3617 系统和现代智能算法。主持重庆邮电 ZHANG Yong,CHEN Ling,XU Xiaolong,et al.Research on 大学校级科研项目3项，参与国际合作 time optimal TSP based on hybrid PSO-GA[J].Application 项目1项，参与省部级项目6项。发表 research of computers,2015,32(12):3613-3617. 学术论文30余篇，出版著作1部。 [11]TIZHOOSH H R.Opposition-based learning:a new scheme for machine intelligence [C]//Proceedings of 2005 and International Conference on Intelligent Agents, 李俊杰，男，1990年生，硕士研究 Web Technologies and Internet Commerce,International 生，主要研究方向为移动机器人自主 Conference on Computational Intelligence for Modelling, 导航。 Control and Automation.Vienna:IEEE,2005:695-701. [12]MUNOZ D M,LLANOS C H,COELHO L D S,et al. Hardware opposition-based PSO applied to mobile robot controllers[].Engineering applications of artificial intel- ligence,2014,28:64-77. [13]汪慎文，丁立新，谢大同，等.应用反向学习策略的群搜 吴慧超，女，1990年生，硕士研究 索优化算法[J].计算机科学，2012,39(9)：183-187. 生，主要研究方向为智能服务机器人。 WANG Shenwen,DING Lixin,XIE Datong,et al.Group search optimizer applying opposition-based learning [J]. Computer science,2012,39(9):183-187. [14]AL-QUNAIEER F S,TIZHOOSH H R,RAHNAMAYAN S.Opposition based computing-a survey[C]//Proceedings

ＴＳＰ ｐｒｏｂｌｅｍ ［ Ｊ ］． Ｃｏｎｔｒｏｌ ａｎｄ ｄｅｃｉｓｉｏｎ， ２０１４ （ １０ ）： １７２９－１７３６． ［４］ＡＧＲＡＷＡＬ Ｒ Ｋ， ＢＡＷＡＮＥ Ｎ Ｇ． Ｍｕｌｔｉｏｂｊｅｃｔｉｖｅ ＰＳＯ ｂａｓｅｄ ａｄａｐｔｉｏｎ ｏｆ ｎｅｕｒａｌ ｎｅｔｗｏｒｋ ｔｏｐｏｌｏｇｙ ｆｏｒ ｐｉｘｅｌ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ｉｎ ｓａｔｅｌｌｉｔｅ ｉｍａｇｅｒｙ ［ Ｊ］． Ａｐｐｌｉｅｄ ｓｏｆｔ ｃｏｍｐｕｔｉｎｇ， ２０１５， ２８ （Ｃ）：２１７－２２５． ［５］ＤＡＳ Ｐ Ｋ， ＢＥＨＥＲＡ Ｈ Ｓ， ＰＡＮＩＧＲＡＨＩ Ｂ Ｋ． Ｉｎｔｅｌｌｉｇｅｎｔ⁃ｂａｓｅｄ ｍｕｌｔｉ⁃ｒｏｂｏｔ ｐａｔｈ ｐｌａｎｎｉｎｇ ｉｎｓｐｉｒｅｄ ｂｙ ｉｍｐｒｏｖｅｄ ｃｌａｓｓｉｃａｌ Ｑ⁃ ｌｅａｒｎｉｎｇ ａｎｄ ｉｍｐｒｏｖｅｄ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ ｗｉｔｈ ｐｅｒｔｕｒｂｅｄ ｖｅｌｏｃｉｔｙ［Ｊ］． Ｅｎｇｉｎｅｅｒｉｎｇ ｓｃｉｅｎｃｅ ａｎｄ ｔｅｃｈｎｏｌｏｇｙ， ａｎ ｉｎｔｅｒｎａｔｉｏｎａｌ ｊｏｕｒｎａｌ， ２０１５， １９（１）： ６５１－６６９． ［６］ ＹＡＮＧ Ｍａｏ， ＬＩ Ｃｈｕｎｚｈｅ． Ｐａｔｈ ｐｌａｎｎｉｎｇ ａｎｄ ｔｒａｃｋｉｎｇ ｆｏｒ ｍｕｌｔｉ⁃ｒｏｂｏｔ ｓｙｓｔｅｍ ｂａｓｅｄ ｏｎ ｉｍｐｒｏｖｅｄ ＰＳＯ ａｌｇｏｒｉｔｈｍ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ２０１１ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｍｅｃｈａｔｒｏｎｉｃ Ｓｃｉｅｎｃｅ， Ｅｌｅｃｔｒｉｃ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ｃｏｍｐｕｔｅｒ（ＭＥＣ）． Ｊｉｌｉｎ： ＩＥＥＥ， ２０１１： １６６７－１６７０． ［７］ ＷＡＮＧ Ｍｉｎｇｍｉｎｇ， ＬＵＯ Ｊｉａｎｊｕｎ， ＷＡＬＴＥＲ Ｕ． Ｔｒａｊｅｃｔｏｒｙ ｐｌａｎｎｉｎｇ ｏｆ ｆｒｅｅ⁃ｆｌｏａｔｉｎｇ ｓｐａｃｅ ｒｏｂｏｔ ｕｓｉｎｇ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐ⁃ ｔｉｍｉｚａｔｉｏｎ （ ＰＳＯ ） ［ Ｊ ］． Ａｃｔａ ａｓｔｒｏｎａｕｔｉｃａ， ２０１５， １１２： ７７－８８． ［８］张万绪， 张向兰， 李莹． 基于改进粒子群算法的智能机 器人 路 径 规 划 ［ Ｊ ］． 计 算 机 应 用， ２０１４， ３４ （ ２ ）： ５１０－５１３． ＺＨＡＮＧ Ｗａｎｘｕ， ＺＨＡＮＧ Ｘｉａｎｇｌａｎ， ＬＩ Ｙｉｎｇ． Ｐａｔｈ ｐｌａｎｎｉｎｇ ｆｏｒ ｉｎｔｅｌｌｉｇｅｎｔ ｒｏｂｏｔｓ ｂａｓｅｄ ｏｎ ｉｍｐｒｏｖｅｄ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉ⁃ ｍｉｚａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ［ Ｊ］． Ｊｏｕｒｎａｌ ｏｆ ｃｏｍｐｕｔｅｒ ａｐｐｌｉｃａｔｉｏｎｓ， ２０１４， ３４（２）： ５１０－５１３． ［９］王娟， 吴宪祥， 郭宝龙． 基于改进粒子群优化算法的移 动机器人路径规划［ Ｊ］． 计算机工程与应用， ２０１２， ４８ （１５）： ２４０－２４４． ＷＡＮＧ Ｊｕａｎ， ＷＵ Ｘｉａｎｘｉａｎｇ， ＧＵＯ Ｂａｏｌｏｎｇ． Ｒｏｂｏｔ ｐａｔｈ ｐｌａｎｎｉｎｇ ｕｓｉｎｇ ｉｍｐｒｏｖｅｄ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ ［ Ｊ］． Ｃｏｍｐｕｔｅｒ ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ ａｐｐｌｉｃａｔｉｏｎｓ， ２０１２， ４８ （ １５ ）： ２４０－２４４． ［１０］张勇， 陈玲， 徐小龙， 等． 基于 ＰＳＯ⁃ＧＡ 混合算法时间 优化的旅行商问题研究［ Ｊ］． 计算机应用研究， ２０１５， ３２（１２）： ３６１３－３６１７． ＺＨＡＮＧ Ｙｏｎｇ， ＣＨＥＮ Ｌｉｎｇ， ＸＵ Ｘｉａｏｌｏｎｇ， ｅｔ ａｌ． Ｒｅｓｅａｒｃｈ ｏｎ ｔｉｍｅ ｏｐｔｉｍａｌ ＴＳＰ ｂａｓｅｄ ｏｎ ｈｙｂｒｉｄ ＰＳＯ⁃ＧＡ［Ｊ］． Ａｐｐｌｉｃａｔｉｏｎ ｒｅｓｅａｒｃｈ ｏｆ ｃｏｍｐｕｔｅｒｓ， ２０１５， ３２（１２）： ３６１３－３６１７． ［ １１ ］ ＴＩＺＨＯＯＳＨ Ｈ Ｒ． Ｏｐｐｏｓｉｔｉｏｎ⁃ｂａｓｅｄ ｌｅａｒｎｉｎｇ： ａ ｎｅｗ ｓｃｈｅｍｅ ｆｏｒ ｍａｃｈｉｎｅ ｉｎｔｅｌｌｉｇｅｎｃｅ ［ Ｃ ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ２００５ ａｎｄ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ａｇｅｎｔｓ， Ｗｅｂ Ｔｅｃｈｎｏｌｏｇｉｅｓ ａｎｄ Ｉｎｔｅｒｎｅｔ Ｃｏｍｍｅｒｃｅ， Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔａｔｉｏｎａｌ Ｉｎｔｅｌｌｉｇｅｎｃｅ ｆｏｒ Ｍｏｄｅｌｌｉｎｇ， Ｃｏｎｔｒｏｌ ａｎｄ Ａｕｔｏｍａｔｉｏｎ． Ｖｉｅｎｎａ： ＩＥＥＥ， ２００５： ６９５－７０１． ［１２］ ＭＵＮ ～ ＯＺ Ｄ Ｍ， ＬＬＡＮＯＳ Ｃ Ｈ， ＣＯＥＬＨＯ Ｌ Ｄ Ｓ， ｅｔ ａｌ． Ｈａｒｄｗａｒｅ ｏｐｐｏｓｉｔｉｏｎ－ｂａｓｅｄ ＰＳＯ ａｐｐｌｉｅｄ ｔｏ ｍｏｂｉｌｅ ｒｏｂｏｔ ｃｏｎｔｒｏｌｌｅｒｓ［Ｊ］． Ｅｎｇｉｎｅｅｒｉｎｇ ａｐｐｌｉｃａｔｉｏｎｓ ｏｆ ａｒｔｉｆｉｃｉａｌ ｉｎｔｅｌ⁃ ｌｉｇｅｎｃｅ， ２０１４， ２８： ６４－７７． ［１３］汪慎文， 丁立新， 谢大同， 等． 应用反向学习策略的群搜 索优化算法［Ｊ］． 计算机科学， ２０１２， ３９（９）： １８３－１８７． ＷＡＮＧ Ｓｈｅｎｗｅｎ， ＤＩＮＧ Ｌｉｘｉｎ， ＸＩＥ Ｄａｔｏｎｇ， ｅｔ ａｌ． Ｇｒｏｕｐ ｓｅａｒｃｈ ｏｐｔｉｍｉｚｅｒ ａｐｐｌｙｉｎｇ ｏｐｐｏｓｉｔｉｏｎ⁃ｂａｓｅｄ ｌｅａｒｎｉｎｇ ［ Ｊ ］． Ｃｏｍｐｕｔｅｒ ｓｃｉｅｎｃｅ， ２０１２， ３９（９）： １８３－１８７． ［１４］ＡＬ⁃ＱＵＮＡＩＥＥＲ Ｆ Ｓ， ＴＩＺＨＯＯＳＨ Ｈ Ｒ， ＲＡＨＮＡＭＡＹＡＮ Ｓ． Ｏｐｐｏｓｉｔｉｏｎ ｂａｓｅｄ ｃｏｍｐｕｔｉｎｇ⁃ａ ｓｕｒｖｅｙ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２０１０ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｊｏｉｎｔ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｎｅｕｒａｌ Ｎｅｔ⁃ ｗｏｒｋｓ （ＩＪＣＮＮ）． Ｂａｒｃｅｌｏｎａ： ＩＥＥＥ， ２０１０． ［ １５ ］ ＳＵＲＥＳＨ Ｋ， ＧＨＯＳＨ Ｓ， ＫＵＮＤＵ Ｄ， ｅｔ ａｌ． Ｉｎｅｒｔｉａ⁃ ａｄａｐｔｉｖｅ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚｅｒ ｆｏｒ ｉｍｐｒｏｖｅｄ ｇｌｏｂａｌ ｓｅａｒｃｈ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ Ｅｉｇｈｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｄｅｓｉｇｎ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ． Ｋａｏｈｓｉｕｎｇ： ＩＥＥＥ， ２００８： ２５３－２５８． ［１６］姜建国， 叶华， 刘慧敏， 等． 融合快速信息交流和局部 搜索的粒子群算法［ Ｊ］． 哈尔滨工程大学学报， ２０１５， ３６（５）： ６８７－６９１． ＪＩＡＮＧ Ｊｉａｎｇｕｏ， ＹＥ Ｈｕａ， ＬＩＵ Ｈｕｉｍｉｎ， ｅｔ ａｌ． Ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ ｍｅｔｈｏｄ ｗｉｔｈ ｃｏｍｂｉｎａｔｉｏｎ ｏｆ ｒａｐｉｄ ｉｎｆｏｒ⁃ ｍａｔｉｏｎ ｃｏｍｍｕｎｉｃａｔｉｏｎ ａｎｄ ｌｏｃａｌ ｓｅａｒｃｈ ［ Ｊ ］． Ｊｏｕｒｎａｌ ｏｆ Ｈａｒｂｉｎ ｅｎｇｉｎｅｅｒｉｎｇ ｕｎｉｖｅｒｓｉｔｙ， ２０１５， ３６（５）： ６８７－６９１． ［１７］ＧＡＯ Ｂｉｎｇｋｕｎ， ＲＥＮ Ｘｉｕｊｕ， ＸＵ Ｍｉｎｇｚｉ． Ａｎ ｉｍｐｒｏｖｅｄ ｐａｒ⁃ ｔｉｃｌｅ ｓｗａｒｍ ａｌｇｏｒｉｔｈｍ ａｎｄ ｉｔｓ ａｐｐｌｉｃａｔｉｏｎ［Ｊ］． Ｐｒｏｃｅｄｉａ ｅｎ⁃ ｇｉｎｅｅｒｉｎｇ， ２０１１， １５： ２４４４－２４４８． ［１８］许少华， 李新幸． 一种自适应改变惯性权重的粒子群算 法［Ｊ］． 科学技术与工程， ２０１２， １２（９）： ２２０５－２２０８． ＸＵ Ｓｈａｏｈｕａ， ＬＩ Ｘｉｎｘｉｎｇ． Ａｎ ａｄａｐｔｉｖｅ ｃｈａｎｇｅｄ ｉｎｅｒｔｉａ ｗｅｉｇｈｔ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ａｌｇｏｒｉｔｈｍ ［ Ｊ］． Ｓｃｉｅｎｃｅ ｔｅｃｈｎｏｌｏｇｙ ａｎｄ ｅｎｇｉｎｅｅｒｉｎｇ， ２０１２， １２（９）： ２２０５－２２０８． ［１９］张建伟， 张立伟， 胡颖， 等． 开源机器人操作系统： ＲＯＳ［Ｍ］． 北京： 科学出版社， ２０１２． ［２０］ ＣＯＵＳＩＮＳ Ｓ， ＧＥＲＫＥＹ Ｂ， ＣＯＮＬＥＹ Ｋ， ｅｔ ａｌ． Ｓｈａｒｉｎｇ Ｓｏｆｔｗａｒｅ ｗｉｔｈ ＲＯＳ［Ｊ］． ＩＥＥＥ ｒｏｂｏｔｉｃｓ ＆ ａｕｔｏｍａｔｉｏｎ ｍａｇａ⁃ ｚｉｎｅ， ２０１０， １７（２）： １２－１４． ［２１］ ＺＡＭＡＮ Ｓ， ＳＬＡＮＹ Ｗ， ＳＴＥＩＮＢＡＵＥＲ Ｇ． ＲＯＳ⁃ｂａｓｅｄ ｍａｐｐｉｎｇ， ｌｏｃａｌｉｚａｔｉｏｎ ａｎｄ ａｕｔｏｎｏｍｏｕｓ ｎａｖｉｇａｔｉｏｎ ｕｓｉｎｇ ａ Ｐｉｏｎｅｅｒ ３⁃ＤＸ ｒｏｂｏｔ ａｎｄ ｔｈｅｉｒ ｒｅｌｅｖａｎｔ ｉｓｓｕｅｓ ［ Ｃ］ ／ ／ Ｐｒｏ⁃ ｃｅｅｄｉｎｇｓ ｏｆ ２０１１ Ｓａｕｄｉ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｅｌｅｃｔｒｏｎｉｃｓ， Ｃｏｍｍｕ⁃ ｎｉｃａｔｉｏｎｓ ａｎｄ Ｐｈｏｔｏｎｉｃｓ Ｃｏｎｆｅｒｅｎｃｅ （ ＳＩＥＣＰＣ）． Ｒｉｙａｄｈ： ＩＥＥＥ， ２０１１： １－５． 作者简介： 蒲兴成，男，１９７３ 年生，副教授，博 士，主要研究方向为非线性系统、随机 系统和现代智能算法。 主持重庆邮电 大学校级科研项目 ３ 项，参与国际合作 项目 １ 项，参与省部级项目 ６ 项。 发表 学术论文 ３０ 余篇，出版著作 １ 部。 李俊杰，男，１９９０ 年生，硕士研究 生，主要研究方向为移动机器人自主 导航。 吴慧超，女，１９９０ 年生，硕士研究 生，主要研究方向为智能服务机器人。 第 ３ 期 蒲兴成，等：基于改进粒子群算法的移动机器人多目标点路径规划 ·３０９·