第10卷第5期 智能系统学报 Vol.10 No.5 2015年10月 CAAI Transactions on Intelligent Systems 0ct.2015 D0I:10.11992/is.201407003 网s络出版t地址：htp:/ww.cmki.net/kcms/detail/23.1538.tp.20151008.1000.004.html 一种生物地理学移动机器人路径规划算法 莫宏伟，马靖雯 (哈尔滨工程大学自动化学院，黑龙江哈尔滨150001) 摘要：目前，虽然有多种智能计算方法用于移动机器人路径规划问题，但在复杂环境下，多数智能计算方法表现出 效率低下，结果较差的问题。提出一种结合基于有效顶点的栅格编码法和改进的生物地理学优化算法的移动机器 人路径规划方法，以解决该类问题。结合已知的环境信息，从精英策略、降维机制和基于惯性算子的迁移操作3方面 改进了生物地理学优化算法。改进算法用于机器人移动路径，与人工蜂群算法、粒子群算法和人工鱼群算法等智能 算法进行比较，实验的结果证实改进算法能够更有效地解决复杂环境下机器人路径规划问题。 关键词：移动机器人：路径规划：生物地理优化算法：有效顶点：栅格编码法 中图分类号：TP301文献标志码：A文章编号：1673-4785(2015)05-0705-07 中文引用格式：莫宏伟，马靖要.一种生物地理学移动机器人路径规划算法[J].智能系统学报，2015,10(5)：705-711. 英文引用格式：MO Hongwei,MA Jingwen..A biogeography-based mobile robot path planning algorithm[J】.CAAI Transactions on Intelligent Systems,2015,10(5):705-711. A biogeography-based mobile robot path planning algorithm MO Hongwei,MA Jingwen College of Automation,Harbin Engineering University,Harbin 150001,China) Abstract:At present,there are many intelligent computing methods used in mobile robot path planning;however, in complex environments,most of them have low efficiency and poor results.In order to solve such problems,this paper proposes a new method for mobile robot path planning,which combines the grid coding method based on the effective vertex with the improved biogeography-based optimization (BBO).On the basis of the environmental infor- mation that has been learned,the BBO is improved in three aspects:elite strategies,dimension reduction mecha- nisms and migration based on inertial operator.The improved BBO is applied in path planning.The method is com- pared with artificial bee colony (ABC),particle swarm optimization (PSO)and artificial fish algorithm (AFA). Experiment results show that the improved method can solve the problem of mobile robot path planning in a complex environment more efficiently. Keywords:mobile robot;path planning;biogeography-based optimization (BBO);effective vertex;grid coding method 移动机器人路径规划主要解决3个问题：1)使 概括为以下4类：模版匹配路径规划技术、人工 机器人能从初始点运动到目标点：2)用一定的算法 势场路径规划技术、地图构建路径规划技术和人工 使机器人能绕开障碍物，并且经过某些必须经过的 智能路径规划技术。 点完成相应的作业任务；3)在完成以上任务的前提 模版匹配技术在环境确定情况下，有较好的应 下，尽量优化机器人运行轨迹。移动机器人路径规 用效果2。人工势场路径规划将机器人在环境中 划技术从移动机器人路径规划的具体算法与策略可 的运动视为一种机器人在虚拟的人工受力场中的运 动。障碍物对机器人产生斥力，目标点对机器人产 收稿日期：2014-07-01.网络出版日期：201410-08 生引力，引力和斥力的合力作为机器人的控制力，从 基金项目：中央高校基本科研业务经费资助项目(HEUCFX041306) 通信作者：莫宏伟.E-mail:honwei.2004@126.com. 而控制机器人避开障碍物而到达目标位置6-2)。地 图构建分为路标法和栅格法，路标法是构造一幅由中央高校基本科研业务经费资助项目 收稿日期： 第 １０ 卷第 ５ 期 智 能 系 统 学 报 Ｖｏｌ．１０ №．５ ２０１５ 年 １０ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｏｃｔ． ２０１ 基金项目 ２０１４⁃０７⁃０１． 网络出版日期： 通信作者：莫宏伟． Ｅ⁃ｍａｉｌ：ｈｏｎｗｅｉ２００４＠ １２６.com. ２０１４⁃１０⁃０８． ５ ＤＯＩ：１０．１１９９２ ／ ｔｉｓ．２０１４０７００３ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ｔｐ．２０１５１００８．１０００．００４．ｈｔｍｌ 一种生物地理学移动机器人路径规划算法 莫宏伟，马靖雯 （哈尔滨工程大学 自动化学院，黑龙江 哈尔滨 １５０００１） 摘 要：目前，虽然有多种智能计算方法用于移动机器人路径规划问题，但在复杂环境下，多数智能计算方法表现出 效率低下，结果较差的问题。 提出一种结合基于有效顶点的栅格编码法和改进的生物地理学优化算法的移动机器 人路径规划方法，以解决该类问题。 结合已知的环境信息，从精英策略、降维机制和基于惯性算子的迁移操作 ３ 方面 改进了生物地理学优化算法。 改进算法用于机器人移动路径，与人工蜂群算法、粒子群算法和人工鱼群算法等智能 算法进行比较，实验的结果证实改进算法能够更有效地解决复杂环境下机器人路径规划问题。 关键词：移动机器人；路径规划；生物地理优化算法；有效顶点；栅格编码法 中图分类号：ＴＰ３０１ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１５）０５⁃０７０５⁃０７ 中文引用格式：莫宏伟，马靖雯． 一种生物地理学移动机器人路径规划算法［Ｊ］． 智能系统学报， ２０１５，１０（５）： ７０５⁃７１１． 英文引用格式：ＭＯ Ｈｏｎｇｗｅｉ， ＭＡ Ｊｉｎｇｗｅｎ． Ａ ｂｉｏｇｅｏｇｒａｐｈｙ⁃ｂａｓｅｄ ｍｏｂｉｌｅ ｒｏｂｏｔ ｐａｔｈ ｐｌａｎｎｉｎｇ ａｌｇｏｒｉｔｈｍ［ Ｊ］． ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ， ２０１５，１０（５）： ７０５⁃７１１． Ａ ｂｉｏｇｅｏｇｒａｐｈｙ⁃ｂａｓｅｄ ｍｏｂｉｌｅ ｒｏｂｏｔ ｐａｔｈ ｐｌａｎｎｉｎｇ ａｌｇｏｒｉｔｈｍ ＭＯ Ｈｏｎｇｗｅｉ， ＭＡ Ｊｉｎｇｗｅｎ （Ｃｏｌｌｅｇｅ ｏｆ Ａｕｔｏｍａｔｉｏｎ， Ｈａｒｂｉｎ Ｅｎｇｉｎｅｅｒｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ， Ｈａｒｂｉｎ １５０００１， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ａｔ ｐｒｅｓｅｎｔ， ｔｈｅｒｅ ａｒｅ ｍａｎｙ ｉｎｔｅｌｌｉｇｅｎｔ ｃｏｍｐｕｔｉｎｇ ｍｅｔｈｏｄｓ ｕｓｅｄ ｉｎ ｍｏｂｉｌｅ ｒｏｂｏｔ ｐａｔｈ ｐｌａｎｎｉｎｇ； ｈｏｗｅｖｅｒ， ｉｎ ｃｏｍｐｌｅｘ ｅｎｖｉｒｏｎｍｅｎｔｓ， ｍｏｓｔ ｏｆ ｔｈｅｍ ｈａｖｅ ｌｏｗ ｅｆｆｉｃｉｅｎｃｙ ａｎｄ ｐｏｏｒ ｒｅｓｕｌｔｓ． Ｉｎ ｏｒｄｅｒ ｔｏ ｓｏｌｖｅ ｓｕｃｈ ｐｒｏｂｌｅｍｓ， ｔｈｉｓ ｐａｐｅｒ ｐｒｏｐｏｓｅｓ ａ ｎｅｗ ｍｅｔｈｏｄ ｆｏｒ ｍｏｂｉｌｅ ｒｏｂｏｔ ｐａｔｈ ｐｌａｎｎｉｎｇ， ｗｈｉｃｈ ｃｏｍｂｉｎｅｓ ｔｈｅ ｇｒｉｄ ｃｏｄｉｎｇ ｍｅｔｈｏｄ ｂａｓｅｄ ｏｎ ｔｈｅ ｅｆｆｅｃｔｉｖｅ ｖｅｒｔｅｘ ｗｉｔｈ ｔｈｅ ｉｍｐｒｏｖｅｄ ｂｉｏｇｅｏｇｒａｐｈｙ⁃ｂａｓｅｄ ｏｐｔｉｍｉｚａｔｉｏｎ （ＢＢＯ）． Ｏｎ ｔｈｅ ｂａｓｉｓ ｏｆ ｔｈｅ ｅｎｖｉｒｏｎｍｅｎｔａｌ ｉｎｆｏｒ⁃ ｍａｔｉｏｎ ｔｈａｔ ｈａｓ ｂｅｅｎ ｌｅａｒｎｅｄ， ｔｈｅ ＢＢＯ ｉｓ ｉｍｐｒｏｖｅｄ ｉｎ ｔｈｒｅｅ ａｓｐｅｃｔｓ： ｅｌｉｔｅ ｓｔｒａｔｅｇｉｅｓ， ｄｉｍｅｎｓｉｏｎ ｒｅｄｕｃｔｉｏｎ ｍｅｃｈａ⁃ ｎｉｓｍｓ ａｎｄ ｍｉｇｒａｔｉｏｎ ｂａｓｅｄ ｏｎ ｉｎｅｒｔｉａｌ ｏｐｅｒａｔｏｒ． Ｔｈｅ ｉｍｐｒｏｖｅｄ ＢＢＯ ｉｓ ａｐｐｌｉｅｄ ｉｎ ｐａｔｈ ｐｌａｎｎｉｎｇ． Ｔｈｅ ｍｅｔｈｏｄ ｉｓ ｃｏｍ⁃ ｐａｒｅｄ ｗｉｔｈ ａｒｔｉｆｉｃｉａｌ ｂｅｅ ｃｏｌｏｎｙ （ＡＢＣ）， ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ （ＰＳＯ） ａｎｄ ａｒｔｉｆｉｃｉａｌ ｆｉｓｈ ａｌｇｏｒｉｔｈｍ （ＡＦＡ）． Ｅｘｐｅｒｉｍｅｎｔ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ｉｍｐｒｏｖｅｄ ｍｅｔｈｏｄ ｃａｎ ｓｏｌｖｅ ｔｈｅ ｐｒｏｂｌｅｍ ｏｆ ｍｏｂｉｌｅ ｒｏｂｏｔ ｐａｔｈ ｐｌａｎｎｉｎｇ ｉｎ ａ ｃｏｍｐｌｅｘ ｅｎｖｉｒｏｎｍｅｎｔ ｍｏｒｅ ｅｆｆｉｃｉｅｎｔｌｙ． Ｋｅｙｗｏｒｄｓ：ｍｏｂｉｌｅ ｒｏｂｏｔ； ｐａｔｈ ｐｌａｎｎｉｎｇ； ｂｉｏｇｅｏｇｒａｐｈｙ⁃ｂａｓｅｄ ｏｐｔｉｍｉｚａｔｉｏｎ （ＢＢＯ）； ｅｆｆｅｃｔｉｖｅ ｖｅｒｔｅｘ； ｇｒｉｄ ｃｏｄｉｎｇ ｍｅｔｈｏｄ 移动机器人路径规划主要解决 ３ 个问题：１）使 机器人能从初始点运动到目标点；２）用一定的算法 使机器人能绕开障碍物，并且经过某些必须经过的 点完成相应的作业任务；３）在完成以上任务的前 (HEUCＦＸ０４１３０６）． 提 下，尽量优化机器人运行轨迹。 移动机器人路径规 划技术从移动机器人路径规划的具体算法与策略可 概括为以下 ４ 类［１］ ：模版匹配路径规划技术、人工 势场路径规划技术、地图构建路径规划技术和人工 智能路径规划技术。 模版匹配技术在环境确定情况下，有较好的应 用效果［２⁃５］ 。 人工势场路径规划将机器人在环境中 的运动视为一种机器人在虚拟的人工受力场中的运 动。 障碍物对机器人产生斥力，目标点对机器人产 生引力，引力和斥力的合力作为机器人的控制力，从 而控制机器人避开障碍物而到达目标位置［６－１２］ 。 地 图构建分为路标法和栅格法，路标法是构造一幅由 ：