贝塞尔曲线融合ACO的移动机器人路径规划

徐 梁，高宏力，宋兴国

（西南交通大学机械工程学院，四川 成都 610031）

1 引言

移动机器人路径规划是机器人研究领域的重要组成部分，是指在给定的有障碍物的运动空间中，根据一定的性能指标（路径最短、时间最少），寻找一条从初始状态到目标状态的最优或近似最优的无碰撞路径。移动机器人路径规划问题是一种典型的NP-hard（非典型性多项式困难）问题[1]，针对移动机器人路径规划，传统方法主要有栅格法[2]、模拟退火法、模糊逻辑法等，栅格法适用于结构简单的环境中，当空间结构变复杂时，存在计算效率低，存储空间大的问题；模拟退火法计算量大、效率低等问题。随着环境复杂程度的增加，出现了免疫算法、遗传算法[3]、人工鱼群算法、A*算法、ACO等智能仿生算法，这类算法在移动机器人路径规划中取得了显著的成果。

ACO最初是由M.Dorigo等人根据蚁群觅食行为中受到启发提出的，用于解决旅行商问题的一种仿生智能优化算法，最近这些年在机器人路径规划方面取得了很好的效果。它具有较好的鲁棒性、良好的分布式计算体制、易于与其他方法相互结合等优点[4-5]。但是ACO规划出来的路径收敛速度慢、易陷入局部最优等、折线多、转角偏大，连接不够平滑，为了提高算法的最优性，必须对基本蚁群算法进行改进，同时为了机器人运动的柔顺性，有必要对路径进行平滑处理。

在此，针对以上问题，给出一种将贝塞尔曲线[6-7]与ACO融合的规划算法。仿真实验结果表明，经过贝塞尔曲线优化后的路径更适合机器人实际的运动规划。

2 环境地图的表示

环境地图建模的过程就是实现现实空间到抽象空间的一个映射过程，环境中的障碍物映射成不可通过的区域。栅格法创建的环境地图简单有效，数据方便处理。假定移动机器人在二维平面RS上运动，平面上分布着随机可数数量，形状不确定的障碍物。栅格模型的建立采用序号法结合直角坐标法的方式。栅格地图中栅格信息直接与环境信息相对应，其中白色栅格为可通过自由区域，黑色栅格为障碍区域。移动机器人在每个栅格中下一个可移动位置为八个相邻栅格。

从实际环境地图到栅格模型地图转换的过程中，对移动机器人和障碍物环境做出以下约定：

（1）在描述障碍物时把障碍物外扩1个机器人的最大直径。

（2）障碍物占用不满一个栅格时，扩充该障碍物，占满栅格。

划分后的机器人工作空间，如图1所示。

图1 栅格地图模型Fig.1 Grid Map Model

设栅格模型为M行N列，按从左到右，从上到下的顺序，左上角第一个栅格坐标为（1,1），序号为R的栅格坐标为（xR，yR），则有：

式中：mod—取余运算；int—取整运算。

3 改进蚁群算法

蚁群算法基本定义如下：

当算法完成一次搜索循环后，对相应路径上的信息素进行更新：

式中：ρ∈（0,1）—信息素挥发系数；

（1-ρ）—信息素残留系数；

驻τij（t）—节点i到节点j的信息素增量；

驻τkij（t）—第k只蚂蚁在路径上留下的信息素。

信息素更新有三种模型，蚁周（Ant-Cycle）模型、蚁量（Ant-Quantity）模型、蚁密（Ant-Density）模型。这里拟采用蚁周（Ant-Cycle）模型：

式中：Q—正整数；Lk—第k只蚂蚁在一次循环中走的路径总长度。

为了避免算法陷入局部最优解和提高算法的收敛性，对算法做出以下改进：

3.1 信息素取值范围

在算法完成一次迭代后，最优路径上的信息素做出如下改变：

通过将信息素限制在一个确定的范围内，可减少算法的过早收敛和保证每个路径点上的信息素差异不会比较大。

3.2 挥发系数

在经典蚁群算法中，挥发系数是一个恒定不变的值，信息素挥发系数跟蚁群算法的全局搜索能力和算法的收敛速度有着紧密的联系；因为ρ的存在，从未被搜索到的路径上的信息素会逐渐减为0，当ρ较大时，再一次选择之前搜索到的路径的可能性较大，算法的全局搜索能力和随机搜索性能也会受到影响；虽然减小ρ可以通过提高算法的全局搜索能力和随机搜索性能，但同时会使得算法的收敛速度降低。

通过以上分析结果，提出了一种自适应改变信息素挥发系数的蚁群算法改进方略，意在通过自适应调整信息素挥发因子ρ来提高算法的全局性。在蚁群算法初期，算法的全局搜索能力需要提高，ρ需要比较大，随着算法的执行，为了提高算法的收敛速度，ρ的取值需要比较小。

式中：ρmin—ρ的最小值，可以避免ρ过小从而降低算法的收敛速度，a和b为系数。

4 路径平滑处理

在栅格环境下蚁群算法规划出来的路径转折次数多，折线多，路径不够平滑，机器人实际运动效率低。所以有必要对规划后的路径进行平滑处理。

贝塞尔曲线是基于伯恩斯坦多项式发展而来的，由于控制简单却有极强的图形描述能力，位置点连接平滑，贝塞尔曲线在工业上得到了广泛的应用。

一条n次贝塞尔曲线表达式为：

式中：P（u）—贝塞尔曲线的运动控制点；u—独立变量；P（i）—位置点；P（0）、P（1）—起点和终点。所有位置点 P（i）构成了一个特征多边形；Bi，n（u）—n 次伯恩斯坦多项式，并且满足：

当n=1时，一阶贝塞尔曲线为一条直线，位置点有两个；当n=2时，二阶贝塞尔曲线为抛物线，位置点有三个；当n≥3时，曲线为高阶贝塞尔曲线，位置点有n+1个。

对贝塞尔曲线求导有：

贝塞尔曲线具有以下性质：

（1）贝塞尔曲线的起点和终点也是特征多边形的起点和终点。

（2）贝塞尔曲线的起点和终点的切线与特征多边形的起始线和结尾线方向一致。

（3）贝塞尔曲线起始于 P（0）结束于 P（1）。

（4）贝塞尔曲线特征多边形一旦确定，曲线的形状也就唯一确定，不依赖选取的参考系。

通过以上两个算法的分析，下面将融合贝塞尔曲线和改进蚁群算法完成移动机器人的路径规划。

5 基于平滑蚁群算法的路径规划

具体的机器人平滑路径规划算法基本步骤如下：

（1）栅格法建立环境地图，确定初始化蚁群算法参数以及移动机器人起始点S和目标点T。

（2）蚂蚁k从点S开始运动，将S放置在禁忌表tabuk中，根据（2）式得到下个移动位置，添加到相应禁忌表中。

（3）判断目标点T是否到达，如果已到达，则令k=k+1，然后转到（2），直到这次迭代过程所有的蚂蚁都完成路径搜索任务。

（4）根据禁忌表tabuk中相关信息，可以计算蚁群的路径长度，进而比较得到最短路径。调整最短路径上各个节点全局信息素值。

（5）判断算法是否满足退出条件，如果满足条件，输出最短路径，否则转至（2）。

（6）对规划的路径进行平滑处理。

对应的流程图，如图3所示。

图2 蚁群算法流程图Fig.2 Flow Chart of Ant Colony Algorithm

6 仿真实验及其分析

本课题用Matlab 2014a对算法进行仿真研究，硬件条件为CPU 2.6 GHz、内存 8 GB。

在仿真环境中中各个参数设定如下，实验环境地图栅格模型为15×15，蚁群算法蚂蚁数目为40，最大迭代次数为50，挥发因子中系数a和b与分别为-0.8，25，改进蚁群算法中重要参数α=1，β=7。当机器人起始序号S为211，终点序号G为15时，仿真图中坐标系的x轴方向正向向右，y轴方向向上，黑色方块为障碍物。基于改进蚁群算法的移动机器人路径规划的仿真过程路径图，如图4所示。

图3 改进蚁群算法最终寻优路径Fig.3 Final Path of Improved ACO

算法均采用运行50次的平均值，对基本的蚁群算法和改进后的蚁群算法做了仿真实验比较，两种算法的寻优路径长度和迭代次数，如表2所示。

表1 算法性能比较Tab.1 Algorithm Performance Comparison

由仿真对比结果可知，和基本蚁群算法相比，改进优化后的蚁群算法能避免搜索陷入局部最优，收敛速度也更快。通过贝塞尔曲线平滑过后的路径，如图5所示。

图4 路径平滑Fig.4 Path Smoothing

通过平滑过后的路径可知，优化过后的路径转折次数大幅减少，更有利于机器人实际的运动，机器人运动更加平滑，对移动机器人自身的冲击也越小。

在随机生成的（20×20）的地图中运行改进蚁群算法规划出的最优路径，如图6所示。通过大量仿真实验结果证明了该改进算法能够有效的解决机器人的路径规划问题。

图5 寻优路径Fig.5 Optimization Path

6 结论

针对移动机器人路径规划问题上，提出了一种基于改进蚁群算法的方法，主要结论如下。（1）通过限制信息素的取值范围，扩大了搜索结果，从而避免了路径陷入局部最优。（2）同时还提出了一种自适应调节信息素挥发因子的蚁群算法改进方针，通过自适应的信息素挥发因子来提高算法的全局性和算法的收敛速度，设置禁忌栅格，防止搜索时路径死锁。（3）针对蚁群算法在栅格环境中规划出来的路径为折线图，提出了用贝塞尔曲线优化路径的方法，优化后的路径更有利于实际机器人运动情况。最后利用本研究提出的算法完成了路径规划任务，仿真实验验证了该方法具有可行性和有效性。