移动机器人路径规划主要解决3个问题：1)使机器人能从初始点运动到目标点；2)用一定的算法使机器人能绕开障碍物，并且经过某些必须经过的点完成相应的作业任务；3)在完成以上任务的前提下，尽量优化机器人运行轨迹。移动机器人路径规划技术从移动机器人路径规划的具体算法与策略可概括为以下4类^[1]：模版匹配路径规划技术、人工势场路径规划技术、地图构建路径规划技术和人工智能路径规划技术。

模版匹配技术在环境确定情况下，有较好的应用效果^{[2, 3, 4, 5]}。人工势场路径规划将机器人在环境中的运动视为一种机器人在虚拟的人工受力场中的运动。障碍物对机器人产生斥力，目标点对机器人产生引力，引力和斥力的合力作为机器人的控制力，从而控制机器人避开障碍物而到达目标位置^{[6, 7, 8, 9, 10, 11, 12]}。地图构建分为路标法和栅格法，路标法是构造一幅由标志点和连接边线组成的机器人可行路径图，如可视线方法、切线图方法、Voronoi图方法和概率图展开法等^[13]。计算智能路径规划将生物启发的计算方法应用于移动机器人的路径规划中，如人工神经网络、进化计算、蚁群算法生物地理优化算法等^[14]。但上述方法尤其是计算智能方法在复杂环境下都缺乏效率，结果也不够准确。本文针对一类复杂环境下的机器人路径规划问题，提出基于改进的生物地理学优化方法(biogeography-based optimization,BBO)，以期更有效地解决该类问题。

栅格法是将环境离散化为二维(或三维)的基本单元栅格，栅格大小决定了离散化环境的分辨率，通过对这些栅格的标示来完成对机器人环境的建模，若为了节约存储空间可采用四叉树等方法进行建模，也可以从方便访问的角度出发建立逐点扫描的二维环境，最后利用搜索算法得到规划路径。这种方法因离散化的建模思想极其符合计算机的存储运算特点而得到了广泛的应用。基本栅格法包括4个步骤：1)栅格化二维平面；2)障碍物膨胀；3)标记障碍物；4)自由栅格之间的连接信息。这种方法存在以下缺点：

1) 栅格在被选入路径后需要加入禁忌表，即该栅格不能再次被选入路径中，这样当遇到一些U型槽等复杂环境会迅速生成有效的路径；

2) 自由栅格大部分都不是有效栅格，路径规划结果的信息仅包含障碍物顶点附近的部分栅格；

3) 分辨率大小难以确定。分辨率过高，增加搜索算法的运算量；分辨率过小会导致路径规划结果粗糙，在极端情况下会造成本来分开的障碍物连通，最终得不到有效的路径。

本文针对基本栅格法的以上3方面缺点，引入了一种更为有效的方法——基于有效定点的栅格编码法。该方法充分借鉴了可视图法和基本栅格法的特点而提出的方法，有效地解决了基本栅格法因分辨率而增加额外运算规模，搜索规模只与有效顶点个数，即障碍物个数及其轮廓复杂度有关系。该方法从模型上解决了U型槽等障碍物模型机器人路径规划导致的算法陷入局部收敛问题。

在m×n的栅格环境中，定义g(i,j)为{g(i,j)|i∈[1,m－1],j∈[1,n－1],i∈N,j∈N}。若栅格g(i,j)，g(i,i+1)，g (i+1,j)，g(i+1,j+1) 4个栅格中有且只有一个障碍物栅格g_ob(x_ob,y_ob)，那么这个4个栅格中必存在一个有效顶点g_v(x_v,y_v)，g_ob与g_v同时满足以下2个条件：

以图1为例，按照有效顶点法将产生31个有效顶点加入到有效顶点列表S，遍历这31个有效顶点并删除重复的顶点，最后如图1所示10×10的栅格地图描述为27个有效顶点。在路径规划之前，需要将起始顶点和目的顶点加入到有效顶点列表。

图 1 基于有效顶点的栅格示意图Fig. 1 Schematic diagram of grids based on effective vertex

图选项

定义Available_i=∅表示，顶点s_i∈S的直线可达顶点集合。对于每个顶点s_j∈S且i≠j若直线可达检测通过，则向Available_i添加s_j，并记录d_ij=d_ji=

生物地理学是一门研究物种生存的自然学科，物种种群分布的地域(栖息地)各不相同。每个栖息地的生活环境各不相同，而且每个物种根据自身的生活条件也各不相同，所以对每个栖息地的适应程度也不相同，因此就有了物种的各式各样的分布、迁移和灭绝等现象。每个栖息地的适应度指数(habitat suitability index，HSI)的高低根据该栖息地的多种因素称为适应度指数变量(suitability index variable，SIV)相关，如种群类别、降雨量、地质状况、植被和气候等。如果该栖息地的适应度指数较高，那么有以下结果：物种必然呈现多样性，即物种数量大，但每个栖息地容纳物种的数量是有限度的，栖息地会因为物种众多而导致资源匮乏，适应度下降导致了物种选择离开栖息地；进入该栖息地的物种数量小于迁出该栖息地的物种数量；若栖息地的适应度指数较低，那么物种多样性减少，即物种数量稀少，但是由于物种较少，导致物种选择迁入到该栖息地的数量高于迁出该栖息地的物种。任何一个栖息地的环境状况都有一定概率发生变异，导致HIS发生改变。本文提出了基于生物地理优化的旅行商问题求解算法 ^[15]。

设有m个岛屿，那么第i个岛屿的SIV_i=(SIV_i¹,SIV_i²,…,SIV_iⁿ)，对于每一个SIV_i^j有

另外，生成第i个岛屿所代表的路径列表Path_i=∅，令V_s加入到Path_i中，设当前路径顶点列表Path_i有j个顶点，那么第j个顶点s_j的可直线到达列表Available_i，定义集合M_i=Available_i－Path_i，定义n为M_i的个数，那么添加顶点s_j+1到Path_i的队尾直到目的地顶点V_t添加到Path_i。s_j+1选取方法如式(4)所示。

SIV_i需要包含的变量个数需要达到N-1(N为有效顶点列表S的个数)才能够保证机器人路径生成的绝对安全。

对于每一个SIV_i^j，表示岛屿i的第j个适应度指数变量是否被从其他岛屿的SIV_k^j迁入所取代的判定：随机数rand(0,1)<λ_i是否成立，若成立则SIV_i^j将被迁入变量所取代；不成立则不执行迁入操作。

迁入操作描述如下，根据每个岛屿的迁出率μ_i进行贪婪算法选择岛屿k，迁出操作将SIV_k^j迁入到SIV_i^j，如式(5)所示。

设有M个岛屿，根据2.1描述的如何将SIV转换为路径列表Path，计算每个岛屿的所代表的路径的长度 D={D₁,D₂,…，D_m－1,D_m}，D_i越小的代表越高的HIS，所以按照D_i的大小由小到大将集合D排序，排序索引可以表示为 Index={I₁,I₂,…,I_M－1,I_M}，I_i表示M个D_i由小到大排序的岛屿i在排序的中的位置。那么岛屿i的物种数S_i可表示为

生物地理学认为栖息地的物种数量过大和过小都将导致栖息地的SIV变异率较高。定义岛屿i的变异率m_i:

基于生物地理学的路径规划算法流程下：

1)初始化最大循环次数N； 初始化BBO的各个参数：岛屿数 M，最大变异率m_max；最大物种数S_max=M－1，最大迁出率E=1，最大嵌入率I=1；初始化每个岛屿i的SIV，SIV_i^j= rand(0,1)；

2)计算每个岛屿的路径D，并根据D_i确定S_i，以及P_Si；保存最小路径信息和最小路径值到D_min；

3)初始化迭代次数nc=0；

4)执行迁移操作；

5)是否执行变异操作，若不执行则跳过；

6)计算每个岛屿的路径D，并根据D_i确定S_i，以及P_Si；计算当前代数最小路径D_min^nc，若D_min^nc<D_min，则D_min^nc=D_min，保存最小路径信息；

7)nc<N是否成立，若成立，则nc=nc+1，跳到4)；若不成立，则跳到7)；

8)输出最短路径值和最短路径信息。

由2.3可知，m_i为岛屿i的变异率，那么当i=Index(1)时，将得到最大的变异率，也就是说：路径最短的岛屿具有很高的变异率。这一结果将可能导致算法的进化出现退化。因此，精英岛屿具有变异率为0的特性。设算法有n个精英岛屿，那么设置方法如下：

在算法步骤上，只需要将算法流程中所述的算法步骤的2)和6)分别在最末加入式(8)。

根据2.1描述可以看出，SIV_i需要包含的变量个数需要达到N-1(N为有效顶点列表S的个数)，即岛屿的变量需要达到和有效顶点数相同(或在单项搜索的时候少1个变量，双向搜索的时候少2个变量)才能够保证机器人路径生成的绝对稳定。但一般情况下，路径规划的结果只包含整个有效顶点结合中少数个顶点。这说明，若不改进算法，算法将会是一个维数巨大的计算，而且是不必要的大维度计算。

本文尝试提出了一种降维机制描述如下：

对于在t=0时，有效顶点集合S内共有X个顶点，那么所有岛屿的SIV⁰的维数Y=X-2；按照2.1方法生成完整的路径，记录第i个岛屿的正向有效的SIV个数x_i，和反向有效的 SIV个数y_i。在t时刻，定义

t时刻所有岛屿的SIV的维数：

实验加载30×30环境模型路径起始点坐标为(0，0)，目的地坐标为(29，29)。

1)BBO算法岛屿总数M设为30，最大变异率m_max设为0.4。算法1为有精英岛屿的BBO算法，算法2为无精英岛屿的BBO算法。2个算法各运行30次，仿真迭代趋势图，规划结果统计图，规划时间消耗统计图分别如图2~4所示。

图 2 精英岛屿对算法迭代的影响趋势Fig. 2 Influence of the elite island on algorithm iteration

图选项

图 3 精英岛屿对算法结果的影响统计Fig. 3 Statistics of the influence of the elite island on results of algorithm

图选项

图 4 精英岛屿对算法时效的影响统计Fig. 4 Statistics of influence of the elite island on algorithm effectiveness

图选项

从规划结果统计来看，有精英岛屿具有更高的稳定性，标准差为0.941 9而无精英岛屿为1.384 3；有精英岛屿具有更好求解最小路径能力，误差率为2.59%，而无精英岛屿为4.15%。从规划时间统计来看，有精英岛屿的BBO算法具有更小的时间消耗，节省时间平均约1.512 1 s。

2)设BBO算法岛屿总数M设为30，最大变异率m_max设为0.4。算法1为有降维机制的BBO算法，算法2为无降维机制的BBO算法。2个算法各运行30次，仿真迭代趋势图，规划结果统计图，规划时间消耗统计图分别如图5~7所示。

图 5 降维机制对算法迭代影响的趋势图Fig. 5 Influence of the dimensionality reduction mechanism on algorithm iteration

图选项

图 6 降维机制对算法结果影响的统计Fig. 6 Statistics of the influence of dimensionality reduction mechanism on results of algorithm

图选项

图 7 降维机制对算法时效影响的统计Fig. 7 Statistics of the influence of dimensionality reduction mechanism on algorithm effectiveness

图选项

根据仿真统计结果及下降趋势图显示，降维机制对算法寻找最小路径效果上有作用。由图5可以看出降维机制加快了算法的收敛速度。由图6可以得到，降维机制呈现了较好的稳定性，30次结果的标准差为0.941 9，而无降维机制为1.297 4；也呈现了较好的搜索能力，30次结果的误差率为2.59%，而无降维机制为3.35%。在规划时间消耗上图7显而易见的表明了其降维机制的优势。

为了能更好的评价4个算法的性能，现将算法参数设置如下：

BBO：岛屿数M=30，最大变异率m_max=0.3，采用上面提到的降维机制和精英策略，以及双向搜索机制；

PSO：粒子个数M=30，惯性常数ω_max=0.8,ω_mmin=0.4，c₁=0.5,c₂=0.5，采用线性动态ω调整策略、降维机制和双向搜索机制；

AFSA：人工鱼个数M=30，拥挤度因子设为2，感知距离为0.1，最大移动步长0.08，最大试探次数10，同样采用双向搜索机制和降维机制；

ABC：人工蜂个数M=30，最大尝试次数Limit=15，同样采用双向搜索机制和降维机制。

每个算法统一迭代次数为2 000次。

为移动机器人在图8环境下进行路径规划，路径起始点为栅格图的左上角(0,0)点，目的地为栅格图的右下角(N-1，N-1)。

图 8 仿真环境模型Fig. 8 Simulation environment models

图选项

算法运行在不同的环境模型下的复杂度及理论最小路径统计如表1所示。

每个算法在每种栅格环境下重复运行30次得到的规划结果和时间消耗结果统计如下表2所示。

由表2中可见，BBO算法除第1种环境与其他算法结果相同以外，其余5种环境下规划效果均好于其他4种算法。表明本文针对机器人路径规划问题，所提出的生物地理优化算法改进策略对于机器人路径规划问题是有效的。

本文基于BBO的机器人路径规划问题，提出了复杂环境下基于有效顶点降维策略的移动机器人路径规划算法，并提出惯性迁移操作算子。改进的BBO与人工蜂群算法、人工鱼群算法、粒子群算法进行对比，仿真结果表明所提出的生物地理机器人路径优化算法对于机器人路径规划是有效的。在此基础上，继续研究该算法在多目标路径规划、城市交通实际环境下的汽车路径规划等问题。