采用生物地理学算法的移动机器人路径规划研究

罗 丹，蒋兵兵

(1.湖南铁道职业技术学院，湖南 株州 412000；2.湖南铁路科技职业技术学院，湖南 株州 412000)

1 引言

随着人工智能的发展，移动机器人的路径规划成为一个研究的热点。路径规划算法分为两类：一类是传统算法，如人工势场法、可视图法、栅格法、自由空间法、A*算法等，另一类是仿生进化算法，如粒子群算法、蚁群算法、遗传算法等。由于传统算法在机器人路径规划中存在搜索效率低等情况[1]，而仿生进化算法在搜索速度方面有较大的优势。因此，近年来，群智能算法是移动机器人路径规中的一个研究热点[3]。

生物地理学算法[2](Biogeography-Based Optimization，BBO)是美国学者Dan Simon将生物地理学的研究成果与工程研究相结合，提出的一种新型仿生进化算法。BBO算法的全局搜索性能较好，学者们对BBO算法进行了大量的研究，并将其广泛应用到电力系统调度问题、非线性系统、0-1组合问题、PID参数整定等实际问题中，并取得了较好的测试效果，也有少部分学者将其用到路径规划中，并取得了一定的研究效果[4,5,8]。考虑到生物地理学算法的存在收敛速度慢等不足，结合遗传算法具有的快速收敛性，本文提出一种新的改进生物地理学算法。

文中将改进的生物地理学算法应用到机器人路径规划中，其本质是将路径规划问题转变为函数优化问题。选取两种不同静态环境，通过MATLAB进行仿真实验，仿真结果证明，生物地理学算法在路径规划中是具有可行性的。

2 环境模型

常用的环境建模方法有行车图法、势场法、单元分解法。为了编程简单易实现，文中采用一种近似的单元分解法，即栅格法。栅格法是用大小相同的栅格单元对将机器人的工作环境进行划分，形成栅格地图，能够处理任意形状的障碍物。常用的栅格地图表示方法有直角坐标法和序号法，序号法表述简洁易懂，文中采用序号法进行栅格标识。如图1所示，从栅格序号p从栅格地图的左下角开始编号，序号p与每一个栅格一一对应，图中黑色部分为障碍物栅格，黑色方格表示障碍物，白色是可行区间为自由栅格。

图1 采用序号法的栅格地图

3 机器人路径优化的目标评价函数

在机器人路径规划中，选择合适的目标函数对算法获得的优化结果和收敛效果是非常关键的，目标函数的适应度值是评价栖息地好坏的一个依据。文中的研究对象是静态环境中的机器人路径优化，以获得最短路径距离为目标，考虑到同样的路径存在的拐点数不一样，为了更好的达到路径优化的效果，引入平滑度最小的优化目标。文中机器人路径优化的目标评价函数选取如下：

(1)

式(1)中，α和β是路径距离和平滑度的权重因子，d是一组无间断可行路径的路径规划距离，s表示路径的平滑度，即路径的拐点个数。

4 改进生物地理学算法在机器人路径规划中的应用

4.1 机器人路径的编码方式

BBO算法是采用实数进行编码的一种优化算法，而机器人路径规划问题是一个离散问题。因此本研究提出一种改进生物地理学算法应用于求解机器人路径规划问题，以栅格标识号进行编码确定一条可行路径，以图3为例，序号[1，2，3，4，15，24，35，36，46，47，48，50，60，70，80，90，100]够成一条可行路径。

4.2 种群初始化

(1)根据起始点到目标点的最短直线距离，获得需要的自由栅格数，然后从每一行自由栅格中随机选取一个可行的自由栅格，构成一组间断的可行路径。以图3为例，一组间断的可行路径为[1，15，24，35，46，60，70，80，90，100]。

(2)通过按照一定的规律插入自由栅格将上述间断可行路径中的间断节点之间转变成无障碍物的连续可行路径[1，15，24，35，46，60，70，80，90，100]。

4.3 生物地理学算法的改进

为克服生物地理学算法在收敛速度上的不足，引入遗传算法的操作算子，通过相互“取长补短”对算法进行改进，以期获得更好的优化效果。其中，遗传算法的选择算子通常是采用轮盘赌法进行操作，存在较大的随机性，文中采用BBO算法的迁入迁出率完成遗传算法选择和交叉操作，改进操作可以实现生物地理学算法进行离散编码，增强BBO算法在搜索效率和精度上的优化性能。

4.3.1 迁移模型的选择。BBO算法采用的是如图4所示的线性迁移模型计算迁入率和迁出率，而文献[6,7]有提出一种余弦迁移模型，通过数据验证，在算法的优化性能上，余弦迁移模型要优于线性迁移模型。

文中采用余弦迁移模型进行物种迁移，设第s个岛屿拥有的物种数量是s个，余弦迁移模型计算[5]公式为：

(2)

式(2)中，表示岛屿之间物种最大迁入率，表示岛屿之间物种最大迁出率。

4.3.2 迁移操作

BBO算法的迁移操作主要是根据迁入迁出率确定需要迁入的栖息地和迁出的栖息地,然后将选定的两个栖息地进行互换。这种全部信息交换机制容易丢失部分更优的子路径，导致算法的收敛速度下降，文中引入遗传算法的交叉机制，可以保留部分更优的路径，从而使算法的优化性能进行提高。融入遗传算法交叉机制的迁移操作伪代码如下：

1：For i=1 to NP (栖息地数量) do

2: if rand < λithen

3: 选取Xi执行迁入操作

4： For j=1 to NP(栖息地数量)do

5： if rand<μjthen

6： 选取Xi执行迁出操作

7： 确定Xi和Xj存在的相同节点的子路径

8： 根据遗传算法的交叉算子对Xi和Xj进行交叉

9: End if

10： End for

11： End if

12: End for

4.3.3 变异操作

在基本BBO算法中[1,5]，采用的是随机变异。随机变异的随机性较大，能够增加物种跳出局部最优，但是随机变异后获得的路径节点可能构成一条不可行的路径。这将使机器人路径优化的迭代次数增加。文中采用一种新的改进的路径规划变异算子，以减少变异后获得不可行路径的概率。变异操作的改进步骤如下。

(1)根据岛屿物种数量s的突变概率函数，选取需要突变的岛屿Xi，Xi=[x1,x2,x3,…xs]为第i个岛屿栖息的物种，即对应路径规划中的一条可行路径。

(2)为提高种群的多样性，采用基于高斯分布的变异操作。按高斯分布概率选择两个节点，将两节点之间的无间断可行路径删除，然后生成新的可行路径替代。

4.4 求解机器人路径规划的生物地理学算法

将公式(1)作为路径规划的目标函数，每一个岛屿代表一条可行路径，根据改进生物地理学算法的迁移操作和变异操作，可以确定求解机器人路径规划的算法流程如图2所示。

图2 基于BBO算法的机器人路径规划流程

5 仿真分析与比较

为了验证该算法的可行性和有效性，选用简单和复杂两种工作环境，用MATLAB进行仿真验证。

简单环境下：障碍物数量为5，栅格地图为10*10，机器人路径规划的算法参数设置如下：岛屿数量NP=20，迭代次数K=250，最大迁入迁出率I=E=1。采用MATLAB7.11进行仿真，在迭代20次左右可以的到获得最优路径如图3所示(图中绿色点是起始点，红色点是目标点)。

图3 10*10环境下最优路径

复杂环境下：障碍物数量为16，栅格地图为20*20，机器人路径规划的算法参数设置如下：岛屿数量NP=20，迭代次数K=300，最大迁入迁出率I=E=1。采用MATLAB7.11进行仿真，在迭代250次可以的到获得最优路径如图4所示(图中绿色点是起始点，红色点是目标点)。

6 结论

通过上述的仿真结果可以看出，在上述的简单环境下，相同的种群数量下，迭代20次左右就可以找到最优解；复杂环境下，迭代250次左右才能获得最优解。仿真结果表明，BBO算法在机器人路径规划上是具有可行性和有效性的。但是对动态环境机器人路径规划效果还有待研究。

图4 20*20环境下最优路径