改进的蚁群算法机器人路径规划研究

2023-12-26黄丰云江仕球许建宁

机械设计与制造 2023年12期

黄丰云，江仕球，许建宁

（武汉理工大学机电工程学院，湖北武汉 430070）

1 引言

移动机器人路径规划是其自主移动完成各种任务的保障，也是所有移动机器人进行智能化应用研究的一切前提。近年来，国内外学者提出一系列算法应用在路径规划研究当中，主要包括蚁群算法［1］、遗传算法［2］、粒子群算法［3-4］、人工势场法［5-6］，但是这些传统算法又存在着不足点，针对蚁群算法的不足点，许多学者从不同的方面对蚁群算法进行改进。文献［7］提出添加双向搜索机制，避免了在搜索过程中选择与终点方向相反的节点。文献［8］通过调整蚁群算法中参数α、β，并且改变ρ，然后提出避障策略以获得最优解。文献［9］通过设置参数的不断调整和建立一种新的信息素机制，仿真结果表明，该方法在最短距离、平均距离、最优路径成功率等方面均优于传统的ACS算法；文献［10］提出增加信息素增益以合理分配初始信息素，还设计了信息素相互引导方法以加快优化速度，引入了混沌干扰来帮助算法跳出局部最优解；文献［11］提出利用刺激概率来帮助蚂蚁选择下一个网格，并采用新的基于无限步长原理的启发式信息来扩展视野，提高可视性精度，采用了新的信息素更新规则和蒸发速率的动态调整，使算法的收敛速度得到了提高。文献［12］首先通过对蚁群系统进行优化，然后通过向蚁群系统中引入单独的变体，使得蚂蚁具有不同的路由策略，大大提高了蚁群算法的性能。文献［13］首先利用刺激概率来选择下一节点同时利用新的启发式信息来拓展视野。

虽然众多学者对蚁群算法进行了相应的改进，但是并没有考虑当前节点与下一节点以及目标节点之间的关系。因此，这里将当前节点与下一节点以及目标节点之间的关系引入到启发函数当中，并且动态调整信息素挥发系数，从而使得蚁群算法收敛速度更快以及避免陷入局部最优解。

2 栅格地图的建立

栅格法是将移动机器人的工作空间离散成一个个的简单的栅格。将栅格中存在障碍物的叫做障碍栅格，常用数字“1”表示，无障碍物栅格叫做可行栅格，通常用数字“0”表示。采用栅格地图法对工作地图完成建模，建立大小为（20×20）的方格，坐标轴从下往上，从左往右。建立的栅格地图，如图1所示。其中各个栅格的坐标与栅格的序号的关系如下：

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

式中：i—对应的栅格序号；N—栅格地图的行数或列数；mod—取余操作；ceil—取整操作。

3 传统蚁群算法

蚁群算法是仿照蚂蚁群体在寻找食物过程中的行为，蚂蚁群体在寻找食物的过程中，会在其走过的路线上留下一种叫做信息素的物质，该信息素的浓度含量与蚂蚁走过的路线长度成反比。蚂蚁更倾向于选择信息素浓度含量高的路线，然后留下一定量的信息素，从而形成一种正反馈机制，使得后期蚂蚁的搜索结果向最优解趋近。

在时刻t下，蚂蚁k由点i转移到点j的概率为：

式中：α—信息启发因子，表示蚂蚁在选择下一个节点时信息素发挥作用的程度；β—期望启发因子，表示节点距离在蚂蚁选择下一个访问节点时的重要程度。allowedk（k=1，2，…，m）为蚂蚁k待访问的节点的集合，由于每个节点仅能访问一次，所以allowedk集合为蚂蚁k在第t次迭代中还没有访问过的节点，开始时allowedk中有（n-1）个元素，随着已访问节点的增加，allowedk的元素不断减少，当其为空时，即表示已访问完所有节点。ηij为启发函数，蚂蚁选择下一节点的概率与启发函数值的大小成正比。

传统蚁群算法中启发函数通常取蚂蚁目前所在节点与下一时刻要选择的节点的距离的倒数，即：

随着时间的推移，蚂蚁在路径上释放信息素的同时，信息素也会逐渐消失，信息素的这一特性被称为挥发性，设参数ρ（0＜ρ＜1）为信息素的挥发因子。因此，在经过一定的时间后需要对各个路径上的信息素进行更新，减去原有信息素挥发的部分，增加蚂蚁新增的信息素，更新规则为：

式中：Q—一只蚂蚁在一次迭代中释放的总信息素，为常数；ρ—信息素挥发系数，ρ值的大小与算法的性能有着直接的关系，信息素挥发快慢与ρ值成正比。ρ值大，影响算法的收敛速度，r值小，算法将陷入局部最优解。

4 改进的蚁群算法

4.1 改进启发函数

在传统的蚁群算法中，启发函数为蚂蚁目前所在节点与下一时刻要选择的节点的距离的倒数，并没有考虑到下一时刻要选择节点与目标节点之间的关系，使得算法易于陷入局部最优解，并且算法的收敛速度也会受到影响。通过将目前所在节点与下一时刻要选择的节点的距离和下一时刻要选择的节点与目标节点之间的距离引入到启发函数当中，并且将目前所在节点与下一时刻要选择的节点的连线和目前所在节点与目标节点的连线之间的角度θ1、目前所在节点与下一时刻要选择的节点之间的连线和下一时刻要选择的节点与目标节点连线的角度θ2引入到启发函数当中，θ1和θ2，如图2所示。

图2 θ1和θ2示意图Fig.2 The Schematic Diagram of θ1 and θ2

图3 信息素挥发系数随迭代次数变化曲线图Fig.3 Variation Curve of Pheromone Volatilization Coefficient with Iteration Times

图4 这里算法流程图Fig.4 Algorithm Flow Chart of this Paper

改进后的蚁群算法的启发函数，如式（8）所示。

式中：i—当前节点；j—下一节点；goal—目标节点。

此启发函数增加了目标节点对当前节点的导向作用，避免了算法中蚂蚁的盲目搜索，从而使得算法的收敛速度得到提高。

4.2 改进信息素挥发系数

在传统的蚁群算法中，ρ通常为一固定的常数，由于这一原因，使得算法的搜索能力有所降低。ρ值的选取对蚁群算法的性能有着重要的关系，ρ值选取得较小，会使得算法陷入局部最优，ρ值选取的较大，路径上的信息素挥发的较快，使得算法的搜索效率降低。对信息素挥发系数进行改进，使其在算法搜索的前期为一个较大的值，可以获得较强的全局搜索能力，而在搜索的后期信息素挥发系数为一个较小的值以获得更快的收敛速度。对信息素挥发系数的改进，如式（11）所示。

式中：k—当前的迭代次数；K—总迭代次数。

4.3 改进算法的步骤

（1）利用栅格法对环境进行建模；（2）初始化蚁群算法的各参数，并且设置好路径的起点和终点；（3）将各代蚂蚁放置在起点中，然后进行路径搜索；（4）在进行选择下一个节点时，先利用新的状态转移概率算出各个相邻节点的选择概率，然后利用轮盘赌的方式选择，已经走过的节点自动加入禁忌表中，直至整个路径搜索完成；（5）蚂蚁完成路径搜索后，根据这里的信息素更新规则对信息素进行更新，并且记录蚂蚁的路线和长度；（6）重复（4），（5）；（7）判断算法是否达到设定的K，若当前迭代次数大于K，则输出最优解。

5 仿真与实验

利用Matlab作为仿真软件，在Matlab上进行仿真实验，设置的算法参数，如表1所示。

表1 算法初始化各参数Tab.1 Algorithm Initialization Parameters

建立（20×20）的栅格地图，设置机器人的起点坐标为（0.5，19.5），机器人的终点坐标为（19.5，0.5），分别利用传统蚁群算法和这里改进的算法对进行路径规划，验证改进算法的有效性。先对简单地图进行路径规划，仿真结果，如图5、图6所示。

图5 基本蚁群算法路径仿真Fig.5 Path Simulation of Basic Ant Colony Algorithm

图6 这里改进蚁群算法路径仿真Fig.6 Path Simulation of Improved Ant Colony Algorithm

算法的收敛曲线，如图7、图8所示。由图5～图8可知，传统蚁群算法和改进的蚁群算法均能搜索出从起点到终点的路径，从路径的长度来看，初始几代蚂蚁出现混乱的状态，搜索路径时长时短，收敛性不好，随着迭代次数的增多，蚂蚁逐渐趋于最优解，但是传统蚁群算法迭代次数为16次，最短路径为31.46，而这里改进的蚁群算法迭代次数为10次，最短路径为28.04，并且能够看出传统蚁群算法陷入了局部最优解。由于上述的仿真实验地图较为简单，为了进一步验证算法的通用性，因此选取更为复杂的地图对算法进行仿真实验，仿真结果，如图9、图10所示。