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