·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) 题求解算法[]。标志点和连接边线组成的机器人可行路径图，如可 视线方法、切线图方法、Ｖｏｒｏｎｏｉ 图方法和概率图展 开法等［ １ ３ ］ 。 计算智能路径规划将生物启发的计算 方法应用于移动机器人的路径规划中，如人工神经 网络、进化计算、蚁群算法生物地理优化算法等［１４］ 。 但上述方法尤其是计算智能方法在复杂环境下都缺 乏效率，结果也不够准确。 本文针对一类复杂环境 下的机器人路径规划问题，提出基于改进的生物地 理 学 优 化 方 法 （ ｂｉｏｇｅｏｇｒａｐｈｙ⁃ｂａｓｅｄ ｏｐｔｉｍｉｚａｔｉｏｎ， ＢＢＯ），以期更有效地解决该类问题。 １ 有效顶点栅格环境 栅格法是将环境离散化为二维（或三维） 的基 本单元栅格，栅格大小决定了离散化环境的分辨率， 通过对这些栅格的标示来完成对机器人环境的建 模，若为了节约存储空间可采用四叉树等方法进行 建模，也可以从方便访问的角度出发建立逐点扫描 的二维环境，最后利用搜索算法得到规划路径。 这 种方法因离散化的建模思想极其符合计算机的存储 运算特点而得到了广泛的应用。 基本栅格法包括 ４ 个步骤：１）栅格化二维平面；２）障碍物膨胀；３）标记 障碍物；４）自由栅格之间的连接信息。 这种方法存 在以下缺点： １） 栅格在被选入路径后需要加入禁忌表，即该 栅格不能再次被选入路径中，这样当遇到一些 Ｕ 型 槽等复杂环境会迅速生成有效的路径； ２） 自由栅格大部分都不是有效栅格，路径规划 结果的信息仅包含障碍物顶点附近的部分栅格； ３） 分辨率大小难以确定。 分辨率过高，增加搜 索算法的运算量；分辨率过小会导致路径规划结果 粗糙，在极端情况下会造成本来分开的障碍物连通， 最终得不到有效的路径。 本文针对基本栅格法的以上 ３ 方面缺点，引入 了一种更为有效的方法———基于有效定点的栅格编 码法。 该方法充分借鉴了可视图法和基本栅格法的 特点而提出的方法，有效地解决了基本栅格法因分 辨率而增加额外运算规模，搜索规模只与有效顶点 个数，即障碍物个数及其轮廓复杂度有关系。 该方 法从模型上解决了 Ｕ 型槽等障碍物模型机器人路 径规划导致的算法陷入局部收敛问题。 在 ｍ×ｎ 的栅格环境中，定义 ｇ（ｉ，ｊ）为｛ｇ（ｉ，ｊ） ｜ｉ∈ ［１，ｍ－１］，ｊ∈［１，ｎ－１］，ｉ∈Ｎ，ｊ∈Ｎ｝。 若栅格 ｇ（ ｉ， ｊ），ｇ（ｉ，ｉ＋１），ｇ（ｉ＋１，ｊ），ｇ（ ｉ＋１，ｊ＋１） ４ 个栅格中有 且只有一个障碍物栅格 ｇｏｂ（ ｘｏｂ，ｙｏｂ），那么这个 ４ 个 栅格中必存在一个有效顶点 ｇｖ（ ｘｖ，ｙｖ ），ｇｏｂ与 ｇｖ 同 时满足以下 ２ 个条件： ｘｖ ≠ ｘｏｂ （１） ｙｖ ≠ ｙｏｂ （２） 以图 １ 为例，按照有效顶点法将产生 ３１ 个有效 顶点加入到有效顶点列表 Ｓ，遍历这 ３１ 个有效顶点 并删除重复的顶点，最后如图 １ 所示 １０×１０ 的栅格 地图描述为 ２７ 个有效顶点。 在路径规划之前，需要 将起始顶点和目的顶点加入到有效顶点列表。 定义 Ａｖａｉｌａｂｌｅｉ ＝ ∅表示，顶点 ｓｉ ∈Ｓ 的直线可 达顶点集合。 对于每个顶点 ｓｊ∈Ｓ 且 ｉ≠ｊ 若直线可 达检测通过，则向Ａｖａｉｌａｂｌｅｉ 添加 ｓｊ，并记录 ｄｉｊ ＝ ｄｊｉ ＝ ‖ｓｉ －ｓｊ‖。 图 １ 基于有效顶点的栅格示意图 Ｆｉｇ．１ Ｓｃｈｅｍａｔｉｃ ｄｉａｇｒａｍ ｏｆ ｇｒｉｄｓ ｂａｓｅｄ ｏｎ ｅｆｆｅｃｔｉｖｅ ｖｅｒｔｅｘ ２ ＢＢＯ 生物地理学是一门研究物种生存的自然学科， 物种种群分布的地域（栖息地） 各不相同。 每个栖 息地的生活环境各不相同，而且每个物种根据自身 的生活条件也各不相同，所以对每个栖息地的适应 程度也不相同，因此就有了物种的各式各样的分布、 迁移和灭绝等现象。 每个栖息地的适应度指数 （ｈａｂｉｔａｔ ｓｕｉｔａｂｉｌｉｔｙ ｉｎｄｅｘ，ＨＳＩ）的高低根据该栖息地 的多种因素称为适应度指数变量（ ｓｕｉｔａｂｉｌｉｔｙ ｉｎｄｅｘ ｖａｒｉａｂｌｅ，ＳＩＶ）相关，如种群类别、降雨量、地质状况、 植被和气候等。 如果该栖息地的适应度指数较高， 那么有以下结果：物种必然呈现多样性，即物种数量 大，但每个栖息地容纳物种的数量是有限度的，栖息 地会因为物种众多而导致资源匮乏，适应度下降导 致了物种选择离开栖息地；进入该栖息地的物种数 量小于迁出该栖息地的物种数量；若栖息地的适应 度指数较低，那么物种多样性减少，即物种数量稀 少，但是由于物种较少，导致物种选择迁入到该栖息 地的数量高于迁出该栖息地的物种。 任何一个栖息 地的环境状况都有一定概率发生变异，导致 ＨＩＳ 发 生改变。 本文提出了基于生物地理优化的旅行商问 题求解算法［１５］ 。 ·７０６· 智 能 系 统 学 报 第 １０ 卷