基于改进经典蚁群算法的机器人路径规划

2020-12-11

山东电力技术 2020年11期

（齐鲁工业大学（山东省科学院），山东济南 250353）

0 引言

20 世纪70 年代以来，各国学者对移动机器人的研究从未停止［1］。进入21 世纪后，随着生产力的大幅提高，用机器人来代替人工的趋势开始不可逆转，特别是5G 时代的来临，全世界即将迈入万物互联的时代，如何使机器人进行高效的工作成为研究热点。路径规划是移动机器人实现正常工作的重要前提，对于移动机器人路径规划的研究，根据提出时间的前后以及算法的本质，可以分为经典路径规划算法和现代智能路径规划算法［2-3］。经典的路径规划方法有D* 算法［4］、A*算法［5］、人工势场法［6］、栅格法［7］、自由空间法等；智能的路径规划方法有遗传算法［8］、粒子群算法［9］、人工蜂群算法［10］、蚁群算法［11］等。相关学者在这些算法的基础上进行了创新和改进，以便使机器人适应日益复杂的工作环境。

经典的蚁群算法存在着前期搜索时间长、容易陷入局部最优等缺点，难以适应日益复杂的工作环境，因此近年来相关学者针对性地提出了一些改进的方法。董蓉等通过将遗传算法和蚁群算法结合，首先用遗传算法来获取最优解，作为蚁群算法的初始信息素部分，然后利用蚁群算法的正反馈机制进行求解［12］；李旭等利用K-means 聚类的将最优路径问题分成小的TSP 问题，在每个问题中和问题间利用蚁群算法找到最优路径［13］；郭胜国等为了避免使蚁群陷入局部最优值，引入分段函数，利用状态转移概率的组合优化方法来平衡每条路径的信息，并且引入了导引函数来加快蚁群的收敛速度［14］；赵静等通过使挥发因子自适应变化来提高蚁群算法在全局路径搜索时的收敛速度［15］。以上改进算法一定程度上克服了传统算法中存在的不足，但是依旧存在一定的问题，如无法保证蚁群的收敛速度达到最优，路径长度达到最短。

通过重新设计蚁群算法的启发函数，使得路径长度较短的路径更容易被较多的蚂蚁选中，而路径较长的路径被蚂蚁选中的概率变小，以此来提高蚁群选择的路径为最优路径的概率。最后通过MATLAB 的仿真对比可以发现改进后的蚁群算法比经典的蚁群算法具有更短的路径长度和更快的收敛速度，以此来证明改进算法的实用性。

1 经典蚁群算法

蚁群算法是学者Dorigo.M 在20 世纪末观察蚁群觅食而提出的一种智能算法，该算法最初提出是为了解决旅行商问题（Travelling Salesman Problem，TSP），后来学者们发现该算法在解决路径规划问题时可靠性强，主要体现在蚁群算法的正反馈机制、较强的鲁棒性和易于与其他算法结合等特点。

蚂蚁觅食的过程可简要进行如下概括：假设一群蚂蚁开始在蚁穴到食物间路线不明确的情况下寻找食物，当其中一只蚂蚁寻找到食物并返回蚁穴时会在运动经过的路径上面留下一些信息素，信息素的作用是告知其他蚂蚁这是一条可行的路径，以便吸引其他的蚂蚁来这条路径搬运食物。路径上的信息素会随着时间的推移而逐渐挥发，也就是说路径较短的路线上残留的信息素会比路径较长的路线上残留的信息素更多，一段时间后大部分蚂蚁便会沿着路径较短的路线行进，路径上信息素的浓度反映的便是路径的长短。但是个别的蚂蚁会另辟蹊径，同时自身分泌信息素，假设发现的路径比原路径更短，大部分蚂蚁就会沿着新发现的路径进行觅食。这就是蚁群算法正反馈的过程，最后蚂蚁们就会发现一条最短的路径。

蚁群算法解决问题的基本步骤如图1 所示。在算法开始时初始化所有的参数，并将所有的蚂蚁置于出发点，所有蚂蚁按照规则访问未访问的节点，直至访问完所有节点。当所有蚂蚁完成一遍访问后更新路径上的信息素浓度，并且判断是否达到最大迭代次数，如果达到，则输出最优解，如果未达到，则在当前的搜索次数上加1 并且所有的蚂蚁重新进行迭代直至最大迭代次数。

2 蚁群算法解决路径规划基本步骤

蚁群算法解决路径规划问题的主要步骤为：

图1 蚁群算法解决问题基本步骤

1）建立环境地图。假设目标环境已知，首先建立机器人工作环境，用0 和1 组成矩阵，0 表示机器人通行路径，1 表示障碍物。

2）初始化参数。蚁群算法中的参数较多，应在开始规划前进行各种参数的设置，其中初始信息素矩阵设置为100×100 阶全0 矩阵；蚂蚁数量设置为m。

3）构建解空间。首先将所有的蚂蚁置于出发点，蚂蚁将会按规则访问所有的节点，最后计算每个蚂蚁走的路径和长度，求出最优路径。其中蚂蚁访问节点的规则为：蚂蚁k（k∈［1，m］）根据各个节点路径上的信息素浓度和路径距离（权）决定其下一个要访问的节点。t 时刻蚂蚁k 从节点i 访问节点j 的概率为

式中：α 为信息素启发因子；β 为期望启发因子；τij（t）、τis（t）为t 时刻，ij、is连线上信息素的浓度；ηij（t）、ηis（t）为启发函数，，其中dij、dis分别为线路ij、is 的长度；Jk（i）为蚂蚁k 未访问节点集合。

4）更新信息素。在蚂蚁释放信息素的同时，各个节点之间的信息素也会随着时间的推移而逐渐消失，参数ρ 为信息素挥发因子，表示信息素的挥发程度。因此当所有的蚂蚁访问完一遍所有的节点之后，每个节点间的信息素也要进行相对地更新，更新的方式为

单位时间内信息素增量的计算主要依靠3 种模型，即蚁周模型、蚁量模型和蚁密模型。蚁周模型根据蚂蚁行进的总长度来计算增加的信息素浓度；蚁量模型根据蚂蚁行进的局部长度信息来计算增加的信息素浓度；蚁密模型则将一个恒值（信息素增加系数）作为增加信息素的浓度。

蚁周模型计算公式为

式中：Q为信息增加强度系数，为常数；Lk为第k 只蚂蚁访问完所有节点后的路径长度。

蚁量模型计算公式为

式中：dij为ij 连线上的欧几里得距离。

蚁密模型计算公式为

由此可见，蚁周模型的计算方式比其余两种计算方式更科学，故本文采用的蚁周模型来计算单位时间内信息素的增量。

5）判断终止与迭代。所有的蚂蚁完成一次迭代后，判断迭代次数是否达到最大，如果达到最大迭代次数，则输出最优值；否则重复步骤3）和4），直到完成最大迭代次数。

在MATLAB 中进行仿真，并根据多次的仿真实验对比确定各参数的初始数据。仿真使用20 栅格×20 栅格的环境地图，初始信息素矩阵设置为100×100 阶的全0 矩阵；最大迭代次数设置为100；蚂蚁数量m 设置为50；信息素重要程度因子设置α 为1；启发函数重要程度因子β 设置为7；信息素挥发因子ρ 设置为0.3；信息素增加强度系数Q 设置为1。对经典蚁群算法的仿真结果如图2 和图3 所示。其中黑色栅格为障碍物栅格，不可通行；白色栅格为自由栅格，可通行，红色为路线。