第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ＦＸ０４１３０６）． 提 下，尽量优化机器人运行轨迹。 移动机器人路径规 划技术从移动机器人路径规划的具体算法与策略可 概括为以下 ４ 类［１］ ：模版匹配路径规划技术、人工 势场路径规划技术、地图构建路径规划技术和人工 智能路径规划技术。 模版匹配技术在环境确定情况下，有较好的应 用效果［２⁃５］ 。 人工势场路径规划将机器人在环境中 的运动视为一种机器人在虚拟的人工受力场中的运 动。 障碍物对机器人产生斥力，目标点对机器人产 生引力，引力和斥力的合力作为机器人的控制力，从 而控制机器人避开障碍物而到达目标位置［６－１２］ 。 地 图构建分为路标法和栅格法，路标法是构造一幅由 ：
·706 智能系统学报 第10卷 标志点和连接边线组成的机器人可行路径图，如可 y,≠yb (2) 视线方法、切线图方法、Voronoi图方法和概率图展 以图1为例，按照有效顶点法将产生31个有效 开法等13]。计算智能路径规划将生物启发的计算 顶点加入到有效顶点列表S,遍历这31个有效顶点 方法应用于移动机器人的路径规划中，如人工神经 并删除重复的顶点，最后如图1所示10×10的栅格 网络、进化计算、蚁群算法生物地理优化算法等。 地图描述为27个有效顶点。在路径规划之前，需要 但上述方法尤其是计算智能方法在复杂环境下都缺 将起始顶点和目的顶点加入到有效顶点列表。 乏效率，结果也不够准确。本文针对一类复杂环境 定义Available,=☑表示，顶点s:∈S的直线可 下的机器人路径规划问题，提出基于改进的生物地 达顶点集合。对于每个顶点s∈S且i≠若直线可 理学优化方法(biogeography--based optimization, 达检测通过，则向Available:添加s,并记录d=da= BB0),以期更有效地解决该类问题。 √s:-s‖。 1有效顶点栅格环境 栅格法是将环境离散化为二维（或三维）的基 本单元栅格，栅格大小决定了离散化环境的分辨率， 通过对这些栅格的标示来完成对机器人环境的建 模，若为了节约存储空间可采用四叉树等方法进行 B 建模，也可以从方便访问的角度出发建立逐点扫描 的二维环境，最后利用搜索算法得到规划路径。这 种方法因离散化的建模思想极其符合计算机的存储 运算特点而得到了广泛的应用。基本栅格法包括4 个步骤：1)栅格化二维平面：2)障碍物膨胀：3)标记 9 10 障碍物：4)自由栅格之间的连接信息。这种方法存 在以下缺点： 图1基于有效顶点的栅格示意图 1)栅格在被选入路径后需要加入禁忌表，即该 Fig.1 Schematic diagram of grids based on effective vertex 栅格不能再次被选入路径中，这样当遇到一些U型 2 BBO 槽等复杂环境会迅速生成有效的路径： 2)自由栅格大部分都不是有效栅格，路径规划 生物地理学是一门研究物种生存的自然学科， 结果的信息仅包含障碍物顶点附近的部分栅格： 物种种群分布的地域（栖息地）各不相同。每个栖 3)分辨率大小难以确定。分辨率过高，增加搜 息地的生活环境各不相同，而且每个物种根据自身 索算法的运算量：分辨率过小会导致路径规划结果 的生活条件也各不相同，所以对每个栖息地的适应 粗糙，在极端情况下会造成本来分开的障碍物连通， 程度也不相同，因此就有了物种的各式各样的分布、 最终得不到有效的路径。 迁移和灭绝等现象。每个栖息地的适应度指数 本文针对基本栅格法的以上3方面缺点，引入 (habitat suitability index,HSI)的高低根据该栖息地 了一种更为有效的方法一基于有效定点的栅格编 的多种因素称为适应度指数变量(suitability index 码法。该方法充分借鉴了可视图法和基本栅格法的 variable,SIV)相关，如种群类别、降雨量、地质状况、 特点而提出的方法，有效地解决了基本栅格法因分 植被和气候等。如果该栖息地的适应度指数较高， 辨率而增加额外运算规模，搜索规模只与有效顶点 那么有以下结果：物种必然呈现多样性，即物种数量 个数，即障碍物个数及其轮廓复杂度有关系。该方 大，但每个栖息地容纳物种的数量是有限度的，栖息 法从模型上解决了U型槽等障碍物模型机器人路 地会因为物种众多而导致资源匮乏，适应度下降导 径规划导致的算法陷入局部收敛问题。 致了物种选择离开栖息地：进入该栖息地的物种数 在mxn的栅格环境中，定义g(i,j)为{g(i,j)li∈ 量小于迁出该栖息地的物种数量：若栖息地的适应 [1,m-1],je[1,n-1],ieN,jeN}。若栅格g(i, 度指数较低，那么物种多样性减少，即物种数量稀 ),g(i,+1),g(i+1,),g(i+1,j+1)4个栅格中有 少，但是由于物种较少，导致物种选择迁入到该栖息 且只有一个障碍物栅格g(xb,yb),那么这个4个 地的数量高于迁出该栖息地的物种。任何一个栖息 栅格中必存在一个有效顶点g(x,y.),8与g.同 地的环境状况都有一定概率发生变异，导致HS发 时满足以下2个条件： 生改变。本文提出了基于生物地理优化的旅行商问 x。≠xb (1) 题求解算法[]
标志点和连接边线组成的机器人可行路径图，如可 视线方法、切线图方法、Ｖｏｒｏｎｏｉ 图方法和概率图展 开法等［ １ ３ ］ 。 计算智能路径规划将生物启发的计算 方法应用于移动机器人的路径规划中，如人工神经 网络、进化计算、蚁群算法生物地理优化算法等［１４］ 。 但上述方法尤其是计算智能方法在复杂环境下都缺 乏效率，结果也不够准确。 本文针对一类复杂环境 下的机器人路径规划问题，提出基于改进的生物地 理 学 优 化 方 法 （ ｂｉｏｇｅｏｇｒａｐｈｙ⁃ｂａｓｅｄ ｏｐｔｉｍｉｚａｔｉｏｎ， ＢＢＯ），以期更有效地解决该类问题。 １ 有效顶点栅格环境 栅格法是将环境离散化为二维（或三维） 的基 本单元栅格，栅格大小决定了离散化环境的分辨率， 通过对这些栅格的标示来完成对机器人环境的建 模，若为了节约存储空间可采用四叉树等方法进行 建模，也可以从方便访问的角度出发建立逐点扫描 的二维环境，最后利用搜索算法得到规划路径。 这 种方法因离散化的建模思想极其符合计算机的存储 运算特点而得到了广泛的应用。 基本栅格法包括 ４ 个步骤：１）栅格化二维平面；２）障碍物膨胀；３）标记 障碍物；４）自由栅格之间的连接信息。 这种方法存 在以下缺点： １） 栅格在被选入路径后需要加入禁忌表，即该 栅格不能再次被选入路径中，这样当遇到一些 Ｕ 型 槽等复杂环境会迅速生成有效的路径； ２） 自由栅格大部分都不是有效栅格，路径规划 结果的信息仅包含障碍物顶点附近的部分栅格； ３） 分辨率大小难以确定。 分辨率过高，增加搜 索算法的运算量；分辨率过小会导致路径规划结果 粗糙，在极端情况下会造成本来分开的障碍物连通， 最终得不到有效的路径。 本文针对基本栅格法的以上 ３ 方面缺点，引入 了一种更为有效的方法———基于有效定点的栅格编 码法。 该方法充分借鉴了可视图法和基本栅格法的 特点而提出的方法，有效地解决了基本栅格法因分 辨率而增加额外运算规模，搜索规模只与有效顶点 个数，即障碍物个数及其轮廓复杂度有关系。 该方 法从模型上解决了 Ｕ 型槽等障碍物模型机器人路 径规划导致的算法陷入局部收敛问题。 在 ｍ×ｎ 的栅格环境中，定义 ｇ（ｉ，ｊ）为｛ｇ（ｉ，ｊ） ｜ｉ∈ ［１，ｍ－１］，ｊ∈［１，ｎ－１］，ｉ∈Ｎ，ｊ∈Ｎ｝。 若栅格 ｇ（ ｉ， ｊ），ｇ（ｉ，ｉ＋１），ｇ（ｉ＋１，ｊ），ｇ（ ｉ＋１，ｊ＋１） ４ 个栅格中有 且只有一个障碍物栅格 ｇｏｂ（ ｘｏｂ，ｙｏｂ），那么这个 ４ 个 栅格中必存在一个有效顶点 ｇｖ（ ｘｖ，ｙｖ ），ｇｏｂ与 ｇｖ 同 时满足以下 ２ 个条件： ｘｖ ≠ ｘｏｂ （１） ｙｖ ≠ ｙｏｂ （２） 以图 １ 为例，按照有效顶点法将产生 ３１ 个有效 顶点加入到有效顶点列表 Ｓ，遍历这 ３１ 个有效顶点 并删除重复的顶点，最后如图 １ 所示 １０×１０ 的栅格 地图描述为 ２７ 个有效顶点。 在路径规划之前，需要 将起始顶点和目的顶点加入到有效顶点列表。 定义 Ａｖａｉｌａｂｌｅｉ ＝ ∅表示，顶点 ｓｉ ∈Ｓ 的直线可 达顶点集合。 对于每个顶点 ｓｊ∈Ｓ 且 ｉ≠ｊ 若直线可 达检测通过，则向Ａｖａｉｌａｂｌｅｉ 添加 ｓｊ，并记录 ｄｉｊ ＝ ｄｊｉ ＝ ‖ｓｉ －ｓｊ‖。 图 １ 基于有效顶点的栅格示意图 Ｆｉｇ．１ Ｓｃｈｅｍａｔｉｃ ｄｉａｇｒａｍ ｏｆ ｇｒｉｄｓ ｂａｓｅｄ ｏｎ ｅｆｆｅｃｔｉｖｅ ｖｅｒｔｅｘ ２ ＢＢＯ 生物地理学是一门研究物种生存的自然学科， 物种种群分布的地域（栖息地） 各不相同。 每个栖 息地的生活环境各不相同，而且每个物种根据自身 的生活条件也各不相同，所以对每个栖息地的适应 程度也不相同，因此就有了物种的各式各样的分布、 迁移和灭绝等现象。 每个栖息地的适应度指数 （ｈａｂｉｔａｔ ｓｕｉｔａｂｉｌｉｔｙ ｉｎｄｅｘ，ＨＳＩ）的高低根据该栖息地 的多种因素称为适应度指数变量（ ｓｕｉｔａｂｉｌｉｔｙ ｉｎｄｅｘ ｖａｒｉａｂｌｅ，ＳＩＶ）相关，如种群类别、降雨量、地质状况、 植被和气候等。 如果该栖息地的适应度指数较高， 那么有以下结果：物种必然呈现多样性，即物种数量 大，但每个栖息地容纳物种的数量是有限度的，栖息 地会因为物种众多而导致资源匮乏，适应度下降导 致了物种选择离开栖息地；进入该栖息地的物种数 量小于迁出该栖息地的物种数量；若栖息地的适应 度指数较低，那么物种多样性减少，即物种数量稀 少，但是由于物种较少，导致物种选择迁入到该栖息 地的数量高于迁出该栖息地的物种。 任何一个栖息 地的环境状况都有一定概率发生变异，导致 ＨＩＳ 发 生改变。 本文提出了基于生物地理优化的旅行商问 题求解算法［１５］ 。 ·７０６· 智 能 系 统 学 报 第 １０ 卷
第5期 莫宏伟，等：一种生物地理学移动机器人路径规划算法 ·707. 2.1适应度指数变量SIV与机器人路径的关系 以及P、;保存最小路径信息和最小路径值到Dm; 设有m个岛屿，那么第i个岛屿的SV:= 3)初始化迭代次数nc=0: (SIV,SIV,…,SIV),对于每一个SIV有 4)执行迁移操作： SIV=SIV,()∈(0,1) (3) 5)是否执行变异操作，若不执行则跳过： 另外，生成第i个岛屿所代表的路径列表Path,=☑， 6)计算每个岛屿的路径D,并根据D:确定S, 令V,加入到Path:中，设当前路径顶点列表Path:有 以及P;计算当前代数最小路径D,若D“0 1)初始化最大循环次数N:初始化BBO的各个 (11)） 参数：岛屿数M,最大变异率mmx;最大物种数Sms= 式中：a为降维因子，a≥1，b为常数。 M-1,最大迁出率E=1,最大嵌入率1=1：初始化每 个岛屿i的SV,SV=rand(0,l): 3仿真与分析 2)计算每个岛屿的路径D,并根据D:确定S, 实验加载30×30环境模型路径起始点坐标为
２．１ 适应度指数变量 ＳＩＶ 与机器人路径的关系 设有 ｍ 个 岛 屿， 那 么 第 ｉ 个 岛 屿 的 ＳＩＶｉ ＝ （ＳＩＶ １ ｉ ，ＳＩＶ ２ ｉ ，…，ＳＩＶ ｎ ｉ ），对于每一个 ＳＩＶ ｊ ｉ 有 ＳＩＶ ｊ ｉ ＝ ＳＩＶｉ（ｊ） ∈ （０，１） （３） 另外，生成第ｉ 个岛屿所代表的路径列表Ｐａｔｈｉ ＝∅， 令 Ｖｓ 加入到 Ｐａｔｈｉ 中，设当前路径顶点列表 Ｐａｔｈｉ 有 ｊ 个顶点，那么第 ｊ 个顶点 ｓｊ 的可直线到达列表 Ａｖａｉｌａｂｌｅｉ，定义集合 Ｍｉ ＝Ａｖａｉｌａｂｌｅｉ －Ｐａｔｈｉ，定义 ｎ 为 Ｍｉ 的个数，那么添加顶点 ｓｊ＋１到 Ｐａｔｈｉ 的队尾直到目 的地顶点 Ｖｔ 添加到 Ｐａｔｈｉ。 ｓｊ＋１选取方法如式（４）所 示。 ｓｊ＋１ ＝ Ｍｉ（ｎ × ＳＩＶ ｊ ｉ） （４） ＳＩＶｉ 需要包含的变量个数需要达到 Ｎ－１（Ｎ 为 有效顶点列表 Ｓ 的个数）才能够保证机器人路径生 成的绝对安全。 ２．２ ＢＢＯ 的迁移操作 对于每一个 ＳＩＶ ｊ ｉ，表示岛屿 ｉ 的第 ｊ 个适应度指 数变量是否被从其他岛屿的 ＳＩＶ ｊ ｋ 迁入所取代的判 定：随机数 ｒａｎｄ（０，１） ＜λｉ 是否成立，若成立则 ＳＩＶ ｊ ｉ 将被迁入变量所取代；不成立则不执行迁入操作。 迁入操作描述如下，根据每个岛屿的迁出率 μｉ 进行贪婪算法选择岛屿 ｋ，迁出操作将 ＳＩＶ ｊ ｋ 迁入到 ＳＩＶ ｊ ｉ，如式（５）所示。 ＳＩＶ ｊ ｉ ＝ ＳＩＶ ｊ ｋ （５） ２．３ ＢＢＯ 的变异操作 设有 Ｍ 个岛屿，根据 ２．１ 描述的如何将 ＳＩＶ 转 换为路径列表 Ｐａｔｈ，计算每个岛屿的所代表的路径 的长度 Ｄ＝ ｛Ｄ１ ，Ｄ２ ，…，Ｄｍ－１ ，Ｄｍ ｝，Ｄｉ 越小的代表越 高的 ＨＩＳ，所以按照 Ｄｉ 的大小由小到大将集合 Ｄ 排 序，排序索引可以表示为 Ｉｎｄｅｘ ＝ ｛ Ｉ１ ， Ｉ２ ，…， ＩＭ－１ ， ＩＭ ｝，Ｉｉ 表示 Ｍ 个 Ｄｉ 由小到大排序的岛屿 ｉ 在排序 的中的位置。 那么岛屿 ｉ 的物种数 Ｓｉ 可表示为 Ｓｉ ＝ Ｍ － Ｉｎｄｅｘ（ｉ） （６） 生物地理学认为栖息地的物种数量过大和过小 都将导致栖息地的 ＳＩＶ 变异率较高。 定义岛屿 ｉ 的 变异率 ｍｉ： ｍｉ ＝ ｍｍａｘ １ － ＰＳｉ Ｐｍａｘ æ è ç ö ø ÷ （７） 式中：ｍｍａｘ为算法需要人工设定的最大变异率。 ２．４ 算法流程 基于生物地理学的路径规划算法流程下： １）初始化最大循环次数 Ｎ；初始化 ＢＢＯ 的各个 参数：岛屿数 Ｍ，最大变异率 ｍｍａｘ；最大物种数 Ｓｍａｘ ＝ Ｍ－１，最大迁出率 Ｅ ＝ １，最大嵌入率 Ｉ ＝ １；初始化每 个岛屿 ｉ 的 ＳＩＶ，ＳＩＶ ｊ ｉ ＝ ｒａｎｄ（０，１）； ２）计算每个岛屿的路径 Ｄ，并根据 Ｄｉ 确定 Ｓｉ， 以及 ＰＳｉ ；保存最小路径信息和最小路径值到 Ｄｍｉｎ ； ３）初始化迭代次数 ｎｃ ＝ ０； ４）执行迁移操作； ５）是否执行变异操作，若不执行则跳过； ６）计算每个岛屿的路径 Ｄ，并根据 Ｄｉ 确定 Ｓｉ， 以及 ＰＳｉ ；计算当前代数最小路径 Ｄ ｎｃ ｍｉｎ ，若 Ｄ ｎｃ ｍｉｎ＜Ｄｍｉｎ ， 则 Ｄ ｎｃ ｍｉｎ ＝Ｄｍｉｎ ，保存最小路径信息； ７）ｎｃ＜Ｎ 是否成立，若成立，则 ｎｃ ＝ ｎｃ＋１，跳到 ４）；若不成立，则跳到 ７）； ８）输出最短路径值和最短路径信息。 ２．５ 算法的改进 ２．５．１ 精英策略 由 ２．３ 可知，ｍｉ 为岛屿 ｉ 的变异率，那么当 ｉ ＝ Ｉｎｄｅｘ（１）时，将得到最大的变异率，也就是说：路径 最短的岛屿具有很高的变异率。 这一结果将可能导 致算法的进化出现退化。 因此，精英岛屿具有变异 率为 ０ 的特性。 设算法有 ｎ 个精英岛屿，那么设置 方法如下： ｍＩｎｄｅｘ（ｉ） ＝ ０，（ｉ ＝ １，２，…，ｎ） （８） 在算法步骤上，只需要将算法流程中所述的算 法步骤的 ２）和 ６）分别在最末加入式（８）。 ２．５．２ 降维 根据 ２．１ 描述可以看出，ＳＩＶｉ 需要包含的变量个 数需要达到 Ｎ－１（Ｎ 为有效顶点列表 Ｓ 的个数），即岛 屿的变量需要达到和有效顶点数相同（或在单项搜索 的时候少 １ 个变量，双向搜索的时候少 ２ 个变量）才 能够保证机器人路径生成的绝对稳定。 但一般情况 下，路径规划的结果只包含整个有效顶点结合中少数 个顶点。 这说明，若不改进算法，算法将会是一个维 数巨大的计算，而且是不必要的大维度计算。 本文尝试提出了一种降维机制描述如下： 对于在 ｔ ＝ ０ 时，有效顶点集合 Ｓ 内共有 Ｘ 个顶 点，那么所有岛屿的 ＳＩＶ ０ 的维数 Ｙ ＝ Ｘ－２；按照 ２．１ 方法生成完整的路径，记录第 ｉ 个岛屿的正向有效 的 ＳＩＶ 个数 ｘｉ，和反向有效的 ＳＩＶ 个数 ｙｉ。 在 ｔ 时 刻，定义 ω（ｔ） ＝ ｍｉｎ｛ｘ１（ｔ） ＋ ｙ１（ｔ），ｘ２（ｔ） ＋ ｙ２（ｔ），…，ｘＭ（ｔ） ＋ ｙＭ（ｔ）｝ （９） ωｍｉｎ ＝ ｍｉｎ｛ω（０），ω（１），…，ω（ｔ － １）｝ （１０） ｔ 时刻所有岛屿的 ＳＩＶ 的维数： Ｙ（ｔ） ＝ Ｘ － ２，ｔ ＝ ０ {α·ｍａｘ｛ωｍｉｎ ，ω（ｔ）｝ ＋ ｂ， ｔ ＞ ０ （１１） 式中：α 为降维因子，α≥１，ｂ 为常数。 ３ 仿真与分析 实验加载 ３０×３０ 环境模型路径起始点坐标为 第 ５ 期 莫宏伟，等：一种生物地理学移动机器人路径规划算法 ·７０７·
·708 智能系统学报 第10卷 (0,0),目的地坐标为(29,29)。 2.59%,而无精英岛屿为4.15%。从规划时间统计 1)BB0算法岛屿总数M设为30，最大变异率 来看，有精英岛屿的BBO算法具有更小的时间消 mm设为0.4。算法1为有精英岛屿的BB0算法， 耗，节省时间平均约1.5121s。 算法2为无精英岛屿的BB0算法。2个算法各运 2)设BB0算法岛屿总数M设为30，最大变异 行30次，仿真迭代趋势图，规划结果统计图，规划时 率m设为0.4。算法1为有降维机制的BB0算 间消耗统计图分别如图2~4所示。 法，算法2为无降维机制的BB0算法。2个算法各 运行30次，仿真迭代趋势图，规划结果统计图，规划 65 时间消耗统计图分别如图5~7所示。 70 60 651 55 一有降维机制 60 ·一无降维机制 55 45- 50 100 200300 400500 次数 图2精英岛屿对算法迭代的影响趋势 Fig.2 Influence of the elite island on algorithm iteration 00 100 200300400500 次数 48.5 48.0 图5降维机制对算法迭代影响的趋势图 47.5 Fig.5 Influence of the dimensionality reduction mecha- 47.0 nism on algorithm iteration 46.5 48.5 46.0 48.0 45.5 47.5 45.0 47.0 44.5 兰 46.5 44.0 无精英岛屿 46.0 有精英岛屿 45.5 图3精英岛屿对算法结果的影响统计 45.0 Fig.3 Statistics of the influence of the elite island on 44.5 results of algorithm 44.0 有降维机制 无降维机制 9 图6降维机制对算法结果影响的统计 Fig.6 Statistics of the influence of dimensionality re- duction mechanism on results of algorithm 14 6 5 10 9 如 8 有精英岛屿 无精英岛屿 6 图4精英岛屿对算法时效的影响统计 4 Fig.4 Statistics of influence of the elite island on algo- rithm effectiveness 有降维机制 无降维机制 从规划结果统计来看，有精英岛屿具有更高的 图7降维机制对算法时效影响的统计 稳定性，标准差为0.9419而无精英岛屿为1.3843： Fig.7 Statistics of the influence of dimensionality re- 有精英岛屿具有更好求解最小路径能力，误差率为 duction mechanism on algorithm effectiveness
（０，０），目的地坐标为（２９，２９）。 １）ＢＢＯ 算法岛屿总数 Ｍ 设为 ３０，最大变异率 ｍｍａｘ设为 ０．４。 算法 １ 为有精英岛屿的 ＢＢＯ 算法， 算法 ２ 为无精英岛屿的 ＢＢＯ 算法。 ２ 个算法各运 行 ３０ 次，仿真迭代趋势图，规划结果统计图，规划时 间消耗统计图分别如图 ２～４ 所示。 图 ２ 精英岛屿对算法迭代的影响趋势 Ｆｉｇ．２ Ｉｎｆｌｕｅｎｃｅ ｏｆ ｔｈｅ ｅｌｉｔｅ ｉｓｌａｎｄ ｏｎ ａｌｇｏｒｉｔｈｍ ｉｔｅｒａｔｉｏｎ 图 ３ 精英岛屿对算法结果的影响统计 Ｆｉｇ．３ Ｓｔａｔｉｓｔｉｃｓ ｏｆ ｔｈｅ ｉｎｆｌｕｅｎｃｅ ｏｆ ｔｈｅ ｅｌｉｔｅ ｉｓｌａｎｄ ｏｎ ｒｅｓｕｌｔｓ ｏｆ ａｌｇｏｒｉｔｈｍ 图 ４ 精英岛屿对算法时效的影响统计 Ｆｉｇ．４ Ｓｔａｔｉｓｔｉｃｓ ｏｆ ｉｎｆｌｕｅｎｃｅ ｏｆ ｔｈｅ ｅｌｉｔｅ ｉｓｌａｎｄ ｏｎ ａｌｇｏ⁃ ｒｉｔｈｍ ｅｆｆｅｃｔｉｖｅｎｅｓｓ 从规划结果统计来看，有精英岛屿具有更高的 稳定性，标准差为 ０．９４１ ９ 而无精英岛屿为 １．３８４ ３； 有精英岛屿具有更好求解最小路径能力，误差率为 ２．５９％，而无精英岛屿为 ４．１５％。 从规划时间统计 来看，有精英岛屿的 ＢＢＯ 算法具有更小的时间消 耗，节省时间平均约 １．５１２ １ ｓ。 ２）设 ＢＢＯ 算法岛屿总数 Ｍ 设为 ３０，最大变异 率 ｍｍａｘ设为 ０．４。 算法 １ 为有降维机制的 ＢＢＯ 算 法，算法 ２ 为无降维机制的 ＢＢＯ 算法。 ２ 个算法各 运行 ３０ 次，仿真迭代趋势图，规划结果统计图，规划 时间消耗统计图分别如图 ５～７ 所示。 图 ５ 降维机制对算法迭代影响的趋势图 Ｆｉｇ．５ Ｉｎｆｌｕｅｎｃｅ ｏｆ ｔｈｅ ｄｉｍｅｎｓｉｏｎａｌｉｔｙ ｒｅｄｕｃｔｉｏｎ ｍｅｃｈａ⁃ ｎｉｓｍ ｏｎ ａｌｇｏｒｉｔｈｍ ｉｔｅｒａｔｉｏｎ 图 ６ 降维机制对算法结果影响的统计 Ｆｉｇ．６ Ｓｔａｔｉｓｔｉｃｓ ｏｆ ｔｈｅ ｉｎｆｌｕｅｎｃｅ ｏｆ ｄｉｍｅｎｓｉｏｎａｌｉｔｙ ｒｅ⁃ ｄｕｃｔｉｏｎ ｍｅｃｈａｎｉｓｍ ｏｎ ｒｅｓｕｌｔｓ ｏｆ ａｌｇｏｒｉｔｈｍ 图 ７ 降维机制对算法时效影响的统计 Ｆｉｇ．７ Ｓｔａｔｉｓｔｉｃｓ ｏｆ ｔｈｅ ｉｎｆｌｕｅｎｃｅ ｏｆ ｄｉｍｅｎｓｉｏｎａｌｉｔｙ ｒｅ⁃ ｄｕｃｔｉｏｎ ｍｅｃｈａｎｉｓｍ ｏｎ ａｌｇｏｒｉｔｈｍ ｅｆｆｅｃｔｉｖｅｎｅｓｓ ·７０８· 智 能 系 统 学 报 第 １０ 卷
第5期 莫宏伟，等：一种生物地理学移动机器人路径规划算法 ·709. 根据仿真统计结果及下降趋势图显示，降维机 为了能更好的评价4个算法的性能，现将算法 制对算法寻找最小路径效果上有作用。由图5可以 参数设置如下： 看出降维机制加快了算法的收敛速度。由图6可以 BB0:岛屿数M=30,最大变异率mm=0.3,采用上 得到，降维机制呈现了较好的稳定性，30次结果的 面提到的降维机制和精英策略，以及双向搜索机制： 标准差为0.9419，而无降维机制为1.2974：也呈现 PS0:粒子个数M=30,惯性常数ωms=0.8, 了较好的搜索能力，30次结果的误差率为2.59%， min=0.4,C1=0.5,c2=0.5,采用线性动态w调整策 而无降维机制为3.35%。在规划时间消耗上图7显 略、降维机制和双向搜索机制； 而易见的表明了其降维机制的优势 AFSA:人工鱼个数M=30,拥挤度因子设为2， 感知距离为0.1，最大移动步长0.08，最大试探次数 ■ ■ 10,同样采用双向搜索机制和降维机制： ■ ■ ABC:人工蜂个数M=30,最大尝试次数Limit= 15,同样采用双向搜索机制和降维机制。 ■ 每个算法统一迭代次数为2000次。 为移动机器人在图8环境下进行路径规划，路 (a)20x20 (b)30×30 径起始点为栅格图的左上角(0,0)点，目的地为栅 格图的右下角(N-1,N-1)。 算法运行在不同的环境模型下的复杂度及 ◆ ” 理论最小路径统计如表1所示。 t ◆ ◆ 每个算法在每种栅格环境下重复运行30次得 到的规划结果和时间消耗结果统计如下表2所示。 ■ ■ 表1仿真环境参数指标 (c)40x40 Table 1 The performance of parameters in simulation en- (d)50x50 vironment 栅格地图 有效顶点数 理论最小值 20×20 141 28.8122 30×30 321 43.9030 40×40 575 58.9938 ■ 50x50 903 73.9526 (e)60x60 (f)70×70 60X60 1305 88.8205 图8仿真环境模型 70×70 1781 103.6884 Fig.8 Simulation environment models 表24种算法路径规划统计结果 Table 2 Statistical results of four path planning algorithms 栅格规模 算法 最小值 最大值 均值 中间值 标准差 误差率/% BBO 29.3487 29.3762 29.3498 29.3487 0.0051 1.87 20×20 PSO 29.3487 35.6218 30.7914 30.3988 1.5300 6.87 (141) AFSA 29.3487 29.3487 29.3487 29.3487 0 1.86 ABC 29.3487 29.4045 29.3506 29.3487 0.0102 1.87 BBO 44.2166 45.5596 44.5585 44.5552 0.2939 2.58 30×30 PSO 47.0589 58.5309 51.7983 51.4951 3.4188 17.98 (321) AFSA 44.3882 48.0344 46.1360 45.8763 1.0564 5.09 ABC 44.5828 52.0776 49.1158 49.3841 2.0587 11.87
根据仿真统计结果及下降趋势图显示，降维机 制对算法寻找最小路径效果上有作用。 由图 ５ 可以 看出降维机制加快了算法的收敛速度。 由图 ６ 可以 得到，降维机制呈现了较好的稳定性，３０ 次结果的 标准差为０．９４１ ９，而无降维机制为１．２９７ ４；也呈现 了较好的搜索能力，３０ 次结果的误差率为 ２．５９％， 而无降维机制为 ３．３５％。 在规划时间消耗上图 ７ 显 而易见的表明了其降维机制的优势。 （ａ）２０×２０ （ｂ）３０×３０ （ｃ）４０×４０ （ｄ）５０×５０ （ｅ）６０×６０ （ｆ）７０×７０ 图 ８ 仿真环境模型 Ｆｉｇ．８ Ｓｉｍｕｌａｔｉｏｎ ｅｎｖｉｒｏｎｍｅｎｔ ｍｏｄｅｌｓ 为了能更好的评价 ４ 个算法的性能，现将算法 参数设置如下： ＢＢＯ：岛屿数 Ｍ＝３０，最大变异率 ｍｍａｘ ＝０．３，采用上 面提到的降维机制和精英策略，以及双向搜索机制； ＰＳＯ：粒子个数 Ｍ ＝ ３０，惯性常数 ωｍａｘ ＝ ０． ８， ωｍｍｉｎ ＝ ０．４，ｃ１ ＝ ０．５，ｃ２ ＝ ０．５，采用线性动态 ω 调整策 略、降维机制和双向搜索机制； ＡＦＳＡ：人工鱼个数 Ｍ ＝ ３０，拥挤度因子设为 ２， 感知距离为 ０．１，最大移动步长 ０．０８，最大试探次数 １０，同样采用双向搜索机制和降维机制； ＡＢＣ：人工蜂个数 Ｍ＝ ３０，最大尝试次数 Ｌｉｍｉｔ ＝ １５，同样采用双向搜索机制和降维机制。 每个算法统一迭代次数为 ２ ０００ 次。 为移动机器人在图 ８ 环境下进行路径规划，路 径起始点为栅格图的左上角（０，０）点，目的地为栅 格图的右下角（Ｎ－１，Ｎ－１）。 算法运行在不同的环境模型下的复杂度及 理论最小路径统计如表 １ 所示。 每个算法在每种栅格环境下重复运行 ３０ 次得 到的规划结果和时间消耗结果统计如下表 ２ 所示。 表 １ 仿真环境参数指标 Ｔａｂｌｅ １ Ｔｈｅ ｐｅｒｆｏｒｍａｎｃｅ ｏｆ ｐａｒａｍｅｔｅｒｓ ｉｎ ｓｉｍｕｌａｔｉｏｎ ｅｎ⁃ ｖｉｒｏｎｍｅｎｔ 栅格地图 有效顶点数 理论最小值 ２０×２０ １４１ ２８．８１２ ２ ３０×３０ ３２１ ４３．９０３ ０ ４０×４０ ５７５ ５８．９９３ ８ ５０×５０ ９０３ ７３．９５２ ６ ６０×６０ １ ３０５ ８８．８２０ ５ ７０×７０ １ ７８１ １０３．６８８ ４ 表 ２ ４ 种算法路径规划统计结果 Ｔａｂｌｅ ２ Ｓｔａｔｉｓｔｉｃａｌ ｒｅｓｕｌｔｓ ｏｆ ｆｏｕｒ ｐａｔｈ ｐｌａｎｎｉｎｇ ａｌｇｏｒｉｔｈｍｓ 栅格规模 算法 最小值 最大值 均值 中间值 标准差 误差率／ ％ ２０×２０ （１４１） ＢＢＯ ２９．３４８ ７ ２９．３７６ ２ ２９．３４９ ８ ２９．３４８ ７ ０．００５ １ １．８７ ＰＳＯ ２９．３４８ ７ ３５．６２１ ８ ３０．７９１ ４ ３０．３９８ ８ １．５３０ ０ ６．８７ ＡＦＳＡ ２９．３４８ ７ ２９．３４８ ７ ２９．３４８ ７ ２９．３４８ ７ ０ １．８６ ＡＢＣ ２９．３４８ ７ ２９．４０４ ５ ２９．３５０ ６ ２９．３４８ ７ ０．０１０ ２ １．８７ ３０×３０ （３２１） ＢＢＯ ４４．２１６ ６ ４５．５５９ ６ ４４．５５８ ５ ４４．５５５ ２ ０．２９３ ９ ２．５８ ＰＳＯ ４７．０５８ ９ ５８．５３０ ９ ５１．７９８ ３ ５１．４９５ １ ３．４１８ ８ １７．９８ ＡＦＳＡ ４４．３８８ ２ ４８．０３４ ４ ４６．１３６ ０ ４５．８７６ ３ １．０５６ ４ ５．０９ ＡＢＣ ４４．５８２ ８ ５２．０７７ ６ ４９．１１５ ８ ４９．３８４ １ ２．０５８ ７ １１．８７ 第 ５ 期 莫宏伟，等：一种生物地理学移动机器人路径规划算法 ·７０９·
·710 智能系统学报 第10卷 续表2 栅格规模 算法 最小值 最大值 均值 中间值 标准差 误差率/% BBO 59.4232 65.7921 63.2292 63.6003 1.2753 7.18 40×40 PSO 70.0582 92.2953 77.5198 77.2684 4.7363 31.40 (575) AFSA 62.9414 73.5154 68.6060 68.7704 2.4336 16.29 ABC 64.9736 81.5214 74.4139 74.0518 3.7850 26.14 BBO 81.7994 92.4076 88.6129 88.7333 3.2713 19.84 50×50 PSO 90.7017 126.7720 109.3243 108.2610 11.2698 47.85 (903) AFSA 87.0084 100.6210 95.7521 96.8591 3.9315 29.50 ABC 92.5656 116.3110 105.5514 106.2935 7.3535 42.75 BBO 103.7410 120.9830 114.7915 116.3125 5.9180 29.24 60×60 PSO 121.0120 156.3720 136.0672 136.0080 10.6057 53.19 (1305) AFSA 117.0590 136.8080 128.6301 131.9730 6.4555 44.82 ABC 125.8070 154.7890 142.2899 143.0705 10.7569 60.20 BBO 147.2240 174.2860 158.4930 157.7410 8.4019 52.86 70×70 PSO 141.5770 219.5680 181.4305 177.8595 25.6275 74.98 (1781) AFSA 132.9760 170.4080 149.9002 148.4045 12.9951 54.21 ABC 164.9980 234.3240 194.0634 191.7700 24.8290 87.16 由表2中可见，BB0算法除第1种环境与其他 Columbus,USA,1994:160-165 算法结果相同以外，其余5种环境下规划效果均好 [3]LIU Yu,ZHU Shiqiang,JIN Bo,et al.Sensory navigation 于其他4种算法。表明本文针对机器人路径规划问 of autonomous cleaning robots[C]//The 5th World Confer- 题，所提出的生物地理优化算法改进策略对于机器 ence on Intelligent Control Automation.Hangzhou,China, 人路径规划问题是有效的。 2004:4793-4796. [4]RAM A,SANTAMARIA J C.Continuous case-based rea- 5结束语 soning[]]Artificial Intelligence,1997,90(1/2):25-77. [5]ARLEO A,SMERALDI F,GERSTNER W.Cognitive navi- 本文基于BBO的机器人路径规划问题，提出了 gation based on nonuniform Gabor space sampling,unsuper- 复杂环境下基于有效顶点降维策略的移动机器人路 vised growing Networks,and reinforcement learning[]. 径规划算法，并提出惯性迁移操作算子。改进的 IEEE Transactions on Neural Network,2004,15(3):639- BBO与人工蜂群算法、人工鱼群算法、粒子群算法 652. 进行对比，仿真结果表明所提出的生物地理机器人 [6]FUJIMURA K,SAMET H.A hierarchical strategy for path 路径优化算法对于机器人路径规划是有效的。在此 planning among moving obstacles[mobile robot][J].IEEE 基础上，继续研究该算法在多目标路径规划、城市交 Transactions on Robotic Automation,1989,5(1):61-69. 通实际环境下的汽车路径规划等问题。 [7]KO N Y,LEE B H.Avoidability measure in moving obsta- cle avoidance problem and its use for robot motion planning 参考文献： [C]//IEEE International Conference on Intelligent Robots [1]朱大奇，颜明重.移动机器人路径规划技术综述[J].控 and System.Osaka,1996:1296-1303. 制与决策.2010,25(7)：961-967. [8]GE S S,CUI Y J.New potential functions for mobile robot ZHU Daqi,YAN Mingzhong.Survey on technology of mo- path planning[J].IEEE Transactions on Robotics and Auto- bile robot path planning[J].Control and Decision,2010, mation,.2000,16(5):615-620. 25(7):961-967. [9]陈清阳，张小波，孙振平，等.非结构化环境下自主车 [2]VASUDEVAN C,GANESAN K.Case-based path planning 辆轨迹规划方法[J].中南大学学报：然科学版.2011， for autonomous underwater vehicles[C]//Proceedings of the 42(11)：3377-3383. 1994 IEEE International Symposium on Intelligent Control. CHEN Qingyang,ZHANG Xiaobo,SUN Zhenping,et al
续表 ２ 栅格规模 算法 最小值 最大值 均值 中间值 标准差 误差率／ ％ ４０×４０ （５７５） ＢＢＯ ５９．４２３ ２ ６５．７９２ １ ６３．２２９ ２ ６３．６００ ３ １．２７５ ３ ７．１８ ＰＳＯ ７０．０５８ ２ ９２．２９５ ３ ７７．５１９ ８ ７７．２６８ ４ ４．７３６ ３ ３１．４０ ＡＦＳＡ ６２．９４１ ４ ７３．５１５ ４ ６８．６０６ ０ ６８．７７０ ４ ２．４３３ ６ １６．２９ ＡＢＣ ６４．９７３ ６ ８１．５２１ ４ ７４．４１３ ９ ７４．０５１ ８ ３．７８５ ０ ２６．１４ ５０×５０ （９０３） ＢＢＯ ８１．７９９ ４ ９２．４０７ ６ ８８．６１２ ９ ８８．７３３ ３ ３．２７１ ３ １９．８４ ＰＳＯ ９０．７０１ ７ １２６．７７２ ０ １０９．３２４ ３ １０８．２６１ ０ １１．２６９ ８ ４７．８５ ＡＦＳＡ ８７．００８ ４ １００．６２１ ０ ９５．７５２ １ ９６．８５９ １ ３．９３１ ５ ２９．５０ ＡＢＣ ９２．５６５ ６ １１６．３１１ ０ １０５．５５１ ４ １０６．２９３ ５ ７．３５３ ５ ４２．７５ ６０×６０ （１３０５） ＢＢＯ １０３．７４１ ０ １２０．９８３ ０ １１４．７９１ ５ １１６．３１２ ５ ５．９１８ ０ ２９．２４ ＰＳＯ １２１．０１２ ０ １５６．３７２ ０ １３６．０６７ ２ １３６．００８ ０ １０．６０５ ７ ５３．１９ ＡＦＳＡ １１７．０５９ ０ １３６．８０８ ０ １２８．６３０ １ １３１．９７３ ０ ６．４５５ ５ ４４．８２ ＡＢＣ １２５．８０７ ０ １５４．７８９ ０ １４２．２８９ ９ １４３．０７０ ５ １０．７５６ ９ ６０．２０ ７０×７０ （１７８１） ＢＢＯ １４７．２２４ ０ １７４．２８６ ０ １５８．４９３ ０ １５７．７４１ ０ ８．４０１ ９ ５２．８６ ＰＳＯ １４１．５７７ ０ ２１９．５６８ ０ １８１．４３０ ５ １７７．８５９ ５ ２５．６２７ ５ ７４．９８ ＡＦＳＡ １３２．９７６ ０ １７０．４０８ ０ １４９．９００ ２ １４８．４０４ ５ １２．９９５ １ ５４．２１ ＡＢＣ １６４．９９８ ０ ２３４．３２４ ０ １９４．０６３ ４ １９１．７７０ ０ ２４．８２９ ０ ８７．１６ 由表 ２ 中可见，ＢＢＯ 算法除第 １ 种环境与其他 算法结果相同以外，其余 ５ 种环境下规划效果均好 于其他 ４ 种算法。 表明本文针对机器人路径规划问 题，所提出的生物地理优化算法改进策略对于机器 人路径规划问题是有效的。 ５ 结束语 本文基于 ＢＢＯ 的机器人路径规划问题，提出了 复杂环境下基于有效顶点降维策略的移动机器人路 径规划算法，并提出惯性迁移操作算子。 改进的 ＢＢＯ 与人工蜂群算法、人工鱼群算法、粒子群算法 进行对比，仿真结果表明所提出的生物地理机器人 路径优化算法对于机器人路径规划是有效的。 在此 基础上，继续研究该算法在多目标路径规划、城市交 通实际环境下的汽车路径规划等问题。 参考文献： ［１］朱大奇， 颜明重． 移动机器人路径规划技术综述［ Ｊ］． 控 制与决策， ２０１０， ２５（７）： ９６１⁃９６７． ＺＨＵ Ｄａｑｉ， ＹＡＮ Ｍｉｎｇｚｈｏｎｇ． Ｓｕｒｖｅｙ ｏｎ ｔｅｃｈｎｏｌｏｇｙ ｏｆ ｍｏ⁃ ｂｉｌｅ ｒｏｂｏｔ ｐａｔｈ ｐｌａｎｎｉｎｇ［ Ｊ］． Ｃｏｎｔｒｏｌ ａｎｄ Ｄｅｃｉｓｉｏｎ， ２０１０， ２５（７）： ９６１⁃９６７． ［２］ＶＡＳＵＤＥＶＡＮ Ｃ， ＧＡＮＥＳＡＮ Ｋ． Ｃａｓｅ⁃ｂａｓｅｄ ｐａｔｈ ｐｌａｎｎｉｎｇ ｆｏｒ ａｕｔｏｎｏｍｏｕｓ ｕｎｄｅｒｗａｔｅｒ ｖｅｈｉｃｌｅｓ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １９９４ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｃｏｎｔｒｏｌ． Ｃｏｌｕｍｂｕｓ， ＵＳＡ， １９９４： １６０⁃１６５． ［３］ＬＩＵ Ｙｕ， ＺＨＵ Ｓｈｉｑｉａｎｇ， ＪＩＮ Ｂｏ， ｅｔ ａｌ． Ｓｅｎｓｏｒｙ ｎａｖｉｇａｔｉｏｎ ｏｆ ａｕｔｏｎｏｍｏｕｓ ｃｌｅａｎｉｎｇ ｒｏｂｏｔｓ［Ｃ］ ／ ／ Ｔｈｅ ５ｔｈ Ｗｏｒｌｄ Ｃｏｎｆｅｒ⁃ ｅｎｃｅ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｃｏｎｔｒｏｌ Ａｕｔｏｍａｔｉｏｎ． Ｈａｎｇｚｈｏｕ， Ｃｈｉｎａ， ２００４： ４７９３⁃４７９６． ［４］ ＲＡＭ Ａ， ＳＡＮＴＡＭＡＲÍＡ Ｊ Ｃ． Ｃｏｎｔｉｎｕｏｕｓ ｃａｓｅ⁃ｂａｓｅｄ ｒｅａ⁃ ｓｏｎｉｎｇ［Ｊ］． Ａｒｔｉｆｉｃｉａｌ Ｉｎｔｅｌｌｉｇｅｎｃｅ， １９９７， ９０（１ ／ ２）： ２５⁃７７． ［５］ＡＲＬＥＯ Ａ， ＳＭＥＲＡＬＤＩ Ｆ， ＧＥＲＳＴＮＥＲ Ｗ． Ｃｏｇｎｉｔｉｖｅ ｎａｖｉ⁃ ｇａｔｉｏｎ ｂａｓｅｄ ｏｎ ｎｏｎｕｎｉｆｏｒｍ Ｇａｂｏｒ ｓｐａｃｅ ｓａｍｐｌｉｎｇ， ｕｎｓｕｐｅｒ⁃ ｖｉｓｅｄ ｇｒｏｗｉｎｇ Ｎｅｔｗｏｒｋｓ， ａｎｄ ｒｅｉｎｆｏｒｃｅｍｅｎｔ ｌｅａｒｎｉｎｇ ［ Ｊ ］． ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｎｅｕｒａｌ Ｎｅｔｗｏｒｋ， ２００４， １５（３）： ６３９⁃ ６５２． ［６］ＦＵＪＩＭＵＲＡ Ｋ， ＳＡＭＥＴ Ｈ． Ａ ｈｉｅｒａｒｃｈｉｃａｌ ｓｔｒａｔｅｇｙ ｆｏｒ ｐａｔｈ ｐｌａｎｎｉｎｇ ａｍｏｎｇ ｍｏｖｉｎｇ ｏｂｓｔａｃｌｅｓ［ｍｏｂｉｌｅ ｒｏｂｏｔ］ ［Ｊ］． ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｒｏｂｏｔｉｃ Ａｕｔｏｍａｔｉｏｎ， １９８９， ５（１）： ６１⁃６９． ［７］ＫＯ Ｎ Ｙ， ＬＥＥ Ｂ Ｈ． Ａｖｏｉｄａｂｉｌｉｔｙ ｍｅａｓｕｒｅ ｉｎ ｍｏｖｉｎｇ ｏｂｓｔａ⁃ ｃｌｅ ａｖｏｉｄａｎｃｅ ｐｒｏｂｌｅｍ ａｎｄ ｉｔｓ ｕｓｅ ｆｏｒ ｒｏｂｏｔ ｍｏｔｉｏｎ ｐｌａｎｎｉｎｇ ［Ｃ］ ／ ／ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｒｏｂｏｔｓ ａｎｄ Ｓｙｓｔｅｍ． Ｏｓａｋａ， １９９６： １２９６⁃１３０３． ［８］ＧＥ Ｓ Ｓ， ＣＵＩ Ｙ Ｊ． Ｎｅｗ ｐｏｔｅｎｔｉａｌ ｆｕｎｃｔｉｏｎｓ ｆｏｒ ｍｏｂｉｌｅ ｒｏｂｏｔ ｐａｔｈ ｐｌａｎｎｉｎｇ［Ｊ］． ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｒｏｂｏｔｉｃｓ ａｎｄ Ａｕｔｏ⁃ ｍａｔｉｏｎ， ２０００， １６（５）： ６１５⁃６２０． ［９］陈清阳， 张小波， 孙振平， 等． 非结构化环境下自主车 辆轨迹规划方法［ Ｊ］． 中南大学学报： 然科学版． ２０１１， ４２（１１）： ３３７７⁃３３８３． ＣＨＥＮ Ｑｉｎｇｙａｎｇ， ＺＨＡＮＧ Ｘｉａｏｂｏ， ＳＵＮ Ｚｈｅｎｐｉｎｇ， ｅｔ ａｌ． ·７１０· 智 能 系 统 学 报 第 １０ 卷
第5期 莫宏伟，等：一种生物地理学移动机器人路径规划算法 ·711. Trajectory planning for autonomous driving in unstructured [14]MO Hongwei,MENG Longlong.Robot path planning based environments[J].Journal of Central South University:atu- on differential evolution in static environment[J.Interna ral and Technology,2011,42(11):3377-3383. tional Journal of Digital Content Technology and its Appli- [10]王鸿鹏，杨云，刘景泰.高速移动机器人的研究现状与 cations,2012,6(20):122-129. 发展趋势[J].自动化与仪表，2011,26(12)：1-4. [15]MO Hongwei,XU Lifang.Biogeography migration algo- WANG Hongpeng,YANG Yun,LIU Jingtai.Research and rithm for traveling salesman problem[J].International development trend of high-speed mobile robot[].Automa- Journal of Intelligent Computing and Cybernetics,2011,4 tion and Instrumentation,2011,26(12):1-4. (3):311-330. [11]谭民，王硕.机器人技术研究进展[J].自动化学报， 作者简介： 2013,39(7):963-972 莫宏伟，男，1973年生，教授，主要 TAN Min,WANG Shuo.Research progress on robotics 研究方向为自然计算理论与应用、机器 [J].Acta Automatica Sinica,2013,39(7):963-972. 人、机器学习与数据挖掘。主持完成国 [12]JARADAT M A K,GARIBEH M H,FEILAT E A.Dy- 家自然科学基金等国家、省部级及横向 namic motion planning for autonomous mobile robot using 课题16项，获得省科技进步奖2项，发 fuzzy potential field [C]//Proceeding of the 6th Interna- 表学术论文60余篇，其中被SCI检索 tional Symposium on Mechatronics and its Applications. 11篇，EI检索40篇。 Sharjah,UAE,2009:24-26. [13]LINGELBACH F.Path planning using probabilistic cell de- 马靖雯，女，1988年生，硕士研究 composition[C]//IEEE International Conference on Ro- 生，主要研究方向为自然计算及其 botics and Automation.New Orleans,USA,2004:467- 应用。 472. 2016年第21届亚洲和南太平洋设计自动化大会 2016 21st Asia and South Pacific Design Automation Conference (ASP-DAC) ASP-DAC 2016 is the twenty-first annual international conference on VLSI design automation in Asia and South Pacific region, one of the most active regions of design and fabrication of silicon chips in the world.The conference aims at providing the Asian and South Pacific CAD/DA and Design community with opportunities of presenting recent advances and with forums for future directions in technologies related to Electronic Design Automation (EDA).The format of the meeting intends to cultivate and promote an instructive and productive interchange of ideas among EDA researchers/developers and system/circuit/device designers.All scientists,engineers, and students who are interested in theoretical and practical aspects of VISI design and design automation are welcomed to ASP-DAC. Areas of Interest: Original papers in,but not limited to,the following areas are invited. 1)System-Level Modeling and Design Methodology; 2)Embedded System Architecture and Design; 3)On-chip Communication and Networks-on-Chip: 4)Embedded Software: 5)Device/Circuit-Level Modeling,Simulation and Verification; 6)Analog,RF and Mixed Signal; 7)System-Level Power and Thermal Management; 8)Device/Circuit/Gate-Level Low Power Design: 9)Logic/Behavioral/High-Level Synthesis and Optimization; 10)Physical Design; 11)Design for Manufacturability and Reliability; 12)Timing and Signal/Power Integrity; 13)Test and Design for Testability; 14)Security and Fault-Tolerant System; 15)Emerging Technology; 16)Emerging Application. Website:http://www.amsv.umac.mo/aspdac2016/
Ｔｒａｊｅｃｔｏｒｙ ｐｌａｎｎｉｎｇ ｆｏｒ ａｕｔｏｎｏｍｏｕｓ ｄｒｉｖｉｎｇ ｉｎ ｕｎｓｔｒｕｃｔｕｒｅｄ ｅｎｖｉｒｏｎｍｅｎｔｓ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｃｅｎｔｒａｌ Ｓｏｕｔｈ Ｕｎｉｖｅｒｓｉｔｙ： ａｔｕ⁃ ｒａｌ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ， ２０１１， ４２（１１）： ３３７７⁃３３８３． ［１０］王鸿鹏， 杨云， 刘景泰． 高速移动机器人的研究现状与 发展趋势［Ｊ］． 自动化与仪表， ２０１１， ２６（１２）： １⁃４． ＷＡＮＧ Ｈｏｎｇｐｅｎｇ， ＹＡＮＧ Ｙｕｎ， ＬＩＵ Ｊｉｎｇｔａｉ． Ｒｅｓｅａｒｃｈ ａｎｄ ｄｅｖｅｌｏｐｍｅｎｔ ｔｒｅｎｄ ｏｆ ｈｉｇｈ⁃ｓｐｅｅｄ ｍｏｂｉｌｅ ｒｏｂｏｔ［Ｊ］． Ａｕｔｏｍａ⁃ ｔｉｏｎ ａｎｄ Ｉｎｓｔｒｕｍｅｎｔａｔｉｏｎ， ２０１１， ２６（１２）： １⁃４． ［１１］谭民， 王硕． 机器人技术研究进展［ Ｊ］． 自动化学报， ２０１３， ３９（７）： ９６３⁃９７２． ＴＡＮ Ｍｉｎ， ＷＡＮＧ Ｓｈｕｏ． Ｒｅｓｅａｒｃｈ ｐｒｏｇｒｅｓｓ ｏｎ ｒｏｂｏｔｉｃｓ ［Ｊ］． Ａｃｔａ Ａｕｔｏｍａｔｉｃａ Ｓｉｎｉｃａ， ２０１３， ３９（７）： ９６３⁃９７２． ［１２］ ＪＡＲＡＤＡＴ Ｍ Ａ Ｋ， ＧＡＲＩＢＥＨ Ｍ Ｈ， ＦＥＩＬＡＴ Ｅ Ａ． Ｄｙ⁃ ｎａｍｉｃ ｍｏｔｉｏｎ ｐｌａｎｎｉｎｇ ｆｏｒ ａｕｔｏｎｏｍｏｕｓ ｍｏｂｉｌｅ ｒｏｂｏｔ ｕｓｉｎｇ ｆｕｚｚｙ ｐｏｔｅｎｔｉａｌ ｆｉｅｌｄ ［ Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇ ｏｆ ｔｈｅ ６ｔｈ Ｉｎｔｅｒｎａ⁃ ｔｉｏｎａｌ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｍｅｃｈａｔｒｏｎｉｃｓ ａｎｄ ｉｔｓ Ａｐｐｌｉｃａｔｉｏｎｓ． Ｓｈａｒｊａｈ， ＵＡＥ， ２００９： ２４⁃２６． ［１３］ＬＩＮＧＥＬＢＡＣＨ Ｆ． Ｐａｔｈ ｐｌａｎｎｉｎｇ ｕｓｉｎｇ ｐｒｏｂａｂｉｌｉｓｔｉｃ ｃｅｌｌ ｄｅ⁃ ｃｏｍｐｏｓｉｔｉｏｎ ［ Ｃ］ ／ ／ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｒｏ⁃ ｂｏｔｉｃｓ ａｎｄ Ａｕｔｏｍａｔｉｏｎ． Ｎｅｗ Ｏｒｌｅａｎｓ， ＵＳＡ， ２００４： ４６７⁃ ４７２． ［１４］ＭＯ Ｈｏｎｇｗｅｉ， ＭＥＮＧ Ｌｏｎｇｌｏｎｇ． Ｒｏｂｏｔ ｐａｔｈ ｐｌａｎｎｉｎｇ ｂａｓｅｄ ｏｎ ｄｉｆｆｅｒｅｎｔｉａｌ ｅｖｏｌｕｔｉｏｎ ｉｎ ｓｔａｔｉｃ ｅｎｖｉｒｏｎｍｅｎｔ［ Ｊ］． Ｉｎｔｅｒｎａ⁃ ｔｉｏｎａｌ Ｊｏｕｒｎａｌ ｏｆ Ｄｉｇｉｔａｌ Ｃｏｎｔｅｎｔ Ｔｅｃｈｎｏｌｏｇｙ ａｎｄ ｉｔｓ Ａｐｐｌｉ⁃ ｃａｔｉｏｎｓ， ２０１２， ６（２０）： １２２⁃１２９． ［１５］ ＭＯ Ｈｏｎｇｗｅｉ， ＸＵ Ｌｉｆａｎｇ． Ｂｉｏｇｅｏｇｒａｐｈｙ ｍｉｇｒａｔｉｏｎ ａｌｇｏ⁃ ｒｉｔｈｍ ｆｏｒ ｔｒａｖｅｌｉｎｇ ｓａｌｅｓｍａｎ ｐｒｏｂｌｅｍ ［ Ｊ ］． Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｊｏｕｒｎａｌ ｏｆ Ｉｎｔｅｌｌｉｇｅｎｔ Ｃｏｍｐｕｔｉｎｇ ａｎｄ Ｃｙｂｅｒｎｅｔｉｃｓ， ２０１１， ４ （３）： ３１１⁃３３０． 作者简介： 莫宏伟，男，１９７３ 年生，教授，主要 研究方向为自然计算理论与应用、机器 人、机器学习与数据挖掘。 主持完成国 家自然科学基金等国家、省部级及横向 课题 １６ 项，获得省科技进步奖 ２ 项，发 表学术论文 ６０ 余篇，其中被 ＳＣＩ 检索 １１ 篇，ＥＩ 检索 ４０ 篇。 马靖雯，女，１９８８ 年生，硕士研究 生， 主 要 研 究 方 向 为 自 然 计 算 及 其 应用。 ２０１６ 年第 ２１ 届亚洲和南太平洋设计自动化大会 ２０１６ ２１ｓｔ Ａｓｉａ ａｎｄ Ｓｏｕｔｈ Ｐａｃｉｆｉｃ Ｄｅｓｉｇｎ Ａｕｔｏｍａｔｉｏｎ Ｃｏｎｆｅｒｅｎｃｅ （ＡＳＰ⁃ＤＡＣ） ＡＳＰ⁃ＤＡＣ ２０１６ ｉｓ ｔｈｅ ｔｗｅｎｔｙ⁃ｆｉｒｓｔ ａｎｎｕａｌ ｉｎｔｅｒｎａｔｉｏｎａｌ ｃｏｎｆｅｒｅｎｃｅ ｏｎ ＶＬＳＩ ｄｅｓｉｇｎ ａｕｔｏｍａｔｉｏｎ ｉｎ Ａｓｉａ ａｎｄ Ｓｏｕｔｈ Ｐａｃｉｆｉｃ ｒｅｇｉｏｎ， ｏｎｅ ｏｆ ｔｈｅ ｍｏｓｔ ａｃｔｉｖｅ ｒｅｇｉｏｎｓ ｏｆ ｄｅｓｉｇｎ ａｎｄ ｆａｂｒｉｃａｔｉｏｎ ｏｆ ｓｉｌｉｃｏｎ ｃｈｉｐｓ ｉｎ ｔｈｅ ｗｏｒｌｄ． Ｔｈｅ ｃｏｎｆｅｒｅｎｃｅ ａｉｍｓ ａｔ ｐｒｏｖｉｄｉｎｇ ｔｈｅ Ａｓｉａｎ ａｎｄ Ｓｏｕｔｈ Ｐａｃｉｆｉｃ ＣＡＤ／ ＤＡ ａｎｄ Ｄｅｓｉｇｎ ｃｏｍｍｕｎｉｔｙ ｗｉｔｈ ｏｐｐｏｒｔｕｎｉｔｉｅｓ ｏｆ ｐｒｅｓｅｎｔｉｎｇ ｒｅｃｅｎｔ ａｄｖａｎｃｅｓ ａｎｄ ｗｉｔｈ ｆｏｒｕｍｓ ｆｏｒ ｆｕｔｕｒｅ ｄｉｒｅｃｔｉｏｎｓ ｉｎ ｔｅｃｈｎｏｌｏｇｉｅｓ ｒｅｌａｔｅｄ ｔｏ Ｅｌｅｃｔｒｏｎｉｃ Ｄｅｓｉｇｎ Ａｕｔｏｍａｔｉｏｎ （ＥＤＡ）． Ｔｈｅ ｆｏｒｍａｔ ｏｆ ｔｈｅ ｍｅｅｔｉｎｇ ｉｎｔｅｎｄｓ ｔｏ ｃｕｌｔｉｖａｔｅ ａｎｄ ｐｒｏｍｏｔｅ ａｎ ｉｎｓｔｒｕｃｔｉｖｅ ａｎｄ ｐｒｏｄｕｃｔｉｖｅ ｉｎｔｅｒｃｈａｎｇｅ ｏｆ ｉｄｅａｓ ａｍｏｎｇ ＥＤＡ ｒｅｓｅａｒｃｈｅｒｓ／ ｄｅｖｅｌｏｐｅｒｓ ａｎｄ ｓｙｓｔｅｍ／ ｃｉｒｃｕｉｔ ／ ｄｅｖｉｃｅ ｄｅｓｉｇｎｅｒｓ． Ａｌｌ ｓｃｉｅｎｔｉｓｔｓ， ｅｎｇｉｎｅｅｒｓ， ａｎｄ ｓｔｕｄｅｎｔｓ ｗｈｏ ａｒｅ ｉｎｔｅｒｅｓｔｅｄ ｉｎ ｔｈｅｏｒｅｔｉｃａｌ ａｎｄ ｐｒａｃｔｉｃａｌ ａｓｐｅｃｔｓ ｏｆ ＶＬＳＩ ｄｅｓｉｇｎ ａｎｄ ｄｅｓｉｇｎ ａｕｔｏｍａｔｉｏｎ ａｒｅ ｗｅｌｃｏｍｅｄ ｔｏ ＡＳＰ⁃ＤＡＣ． Ａｒｅａｓ ｏｆ Ｉｎｔｅｒｅｓｔ： Ｏｒｉｇｉｎａｌ ｐａｐｅｒｓ ｉｎ， ｂｕｔ ｎｏｔ ｌｉｍｉｔｅｄ ｔｏ， ｔｈｅ ｆｏｌｌｏｗｉｎｇ ａｒｅａｓ ａｒｅ ｉｎｖｉｔｅｄ． １） Ｓｙｓｔｅｍ⁃Ｌｅｖｅｌ Ｍｏｄｅｌｉｎｇ ａｎｄ Ｄｅｓｉｇｎ Ｍｅｔｈｏｄｏｌｏｇｙ； ２） Ｅｍｂｅｄｄｅｄ Ｓｙｓｔｅｍ Ａｒｃｈｉｔｅｃｔｕｒｅ ａｎｄ Ｄｅｓｉｇｎ； ３） Ｏｎ⁃ｃｈｉｐ Ｃｏｍｍｕｎｉｃａｔｉｏｎ ａｎｄ Ｎｅｔｗｏｒｋｓ⁃ｏｎ⁃Ｃｈｉｐ； ４） Ｅｍｂｅｄｄｅｄ Ｓｏｆｔｗａｒｅ； ５） Ｄｅｖｉｃｅ ／ Ｃｉｒｃｕｉｔ⁃Ｌｅｖｅｌ Ｍｏｄｅｌｉｎｇ， Ｓｉｍｕｌａｔｉｏｎ ａｎｄ Ｖｅｒｉｆｉｃａｔｉｏｎ； ６） Ａｎａｌｏｇ， ＲＦ ａｎｄ Ｍｉｘｅｄ Ｓｉｇｎａｌ； ７） Ｓｙｓｔｅｍ⁃Ｌｅｖｅｌ Ｐｏｗｅｒ ａｎｄ Ｔｈｅｒｍａｌ Ｍａｎａｇｅｍｅｎｔ； ８） Ｄｅｖｉｃｅ ／ Ｃｉｒｃｕｉｔ ／ Ｇａｔｅ⁃Ｌｅｖｅｌ Ｌｏｗ Ｐｏｗｅｒ Ｄｅｓｉｇｎ； ９） Ｌｏｇｉｃ ／ Ｂｅｈａｖｉｏｒａｌ ／ Ｈｉｇｈ⁃Ｌｅｖｅｌ Ｓｙｎｔｈｅｓｉｓ ａｎｄ Ｏｐｔｉｍｉｚａｔｉｏｎ； １０） Ｐｈｙｓｉｃａｌ Ｄｅｓｉｇｎ； １１） Ｄｅｓｉｇｎ ｆｏｒ Ｍａｎｕｆａｃｔｕｒａｂｉｌｉｔｙ ａｎｄ Ｒｅｌｉａｂｉｌｉｔｙ； １２） Ｔｉｍｉｎｇ ａｎｄ Ｓｉｇｎａｌ ／ Ｐｏｗｅｒ Ｉｎｔｅｇｒｉｔｙ； １３） Ｔｅｓｔ ａｎｄ Ｄｅｓｉｇｎ ｆｏｒ Ｔｅｓｔａｂｉｌｉｔｙ； １４） Ｓｅｃｕｒｉｔｙ ａｎｄ Ｆａｕｌｔ⁃Ｔｏｌｅｒａｎｔ Ｓｙｓｔｅｍ； １５） Ｅｍｅｒｇｉｎｇ Ｔｅｃｈｎｏｌｏｇｙ； １６） Ｅｍｅｒｇｉｎｇ Ａｐｐｌｉｃａｔｉｏｎ． Ｗｅｂｓｉｔｅ： ｈｔｔｐ： ／ ／ ｗｗｗ．ａｍｓｖ．ｕｍａｃ．ｍｏ ／ ａｓｐｄａｃ２０１６ ／ 第 ５ 期 莫宏伟，等：一种生物地理学移动机器人路径规划算法 ·７１１·