CN109945881A - 一种蚁群算法的移动机器人路径规划方法 - Google Patents

Abstract

本发明公开了一种蚁群算法的移动机器人路径规划方法，包括：根据栅格法形成移动机器人的栅格地图，根据起点与终点的障碍物信息形成初始信息素的分布，根据临界障碍物影响因子形成期望启发函数，根据信息素更新公式对信息素的进行更新，根据模糊算法动态调整信息素启发因子和期望启发因子的参数，对信息素挥发系数进行动态调整。本发明提供的技术方案能够获得更好的最优路径解，收敛速度更快。另外，本发明通过仿真实验证明了上述技术方案是可行的以及有效的。

Description

一种蚁群算法的移动机器人路径规划方法

技术领域

本发明涉及机器人技术领域，尤其涉及一种蚁群算法的移动机器人路径规划方法。

背景技术

移动机器人因其在工业应用、制造业、搜索救援、医疗服务、智能物流等领域的巨大潜力和研究价值而受到人们的广泛关注。导航是移动机器人相关技术的研究核心，因为它定义了移动机器人如何感知环境、如何在环境中定位以及如何在已知地图中规划路径。路径规划是导航技术研究中的重要组成部分，其主要目的是在已知环境中为移动机器人构建一条从起始点到目标点的无碰撞最优路径。

路径规划问题一般同时考虑静态环境和动态环境：静态环境是指起始点和目标点的位置是已知，并且障碍物也是静止不动的。然而，在动态环境中，由于障碍物的位置和目标点可能会随着时间的变化而发生改变，移动机器人需要借助传感器的信息做出相应决策。根据机器人对环境的感知不同，路径规划可分为两类：第一类，机器人先对环境信息建立地图，因此路径可以根据已知地图信息离线规划，这类路径规划称为全局路径规划；第二类，机器人不会提前输入环境信息，需要利用传感器实时建立环境地图，避开障碍物找到一条合适的路径，这类路径规划称为局部路径规划。本实施例研究的是静态环境下的全局路径规划问题。

近年来，许多学者对路径规划进行了大量的研究并提出了一些可行的方法，例如人工势场法、模糊算法、DWA算法、遗传算法、免疫算法、神经网络算法等。但是，这些技术方法中存在着一些缺点，如稳定性差、局部最优、适应性不强等。

发明内容

为解决现有技术存在的局限和缺陷，本发明提供一种蚁群算法的移动机器人路径规划方法，包括：

根据栅格法形成移动机器人的栅格地图，所述移动机器人在所述环境地图的序列编码的计算公式为：

其中，机器人的坐标为(x_g，y_g)，Num为序列标号，N_x为所述栅格地图的行数，N_y为所述栅格地图的列数；

根据起点与终点的障碍物信息形成初始信息素的分布；

根据临界障碍物影响因子形成期望启发函数，所述期望启发函数为：

其中，d_ij为两个相邻网格之间的距离，g_i为节点i处的临界障碍物影响因子，A常数；

根据信息素更新公式对信息素的进行更新，所述信息素更新公式为：

其中，Q为信息素增强系数，L_k为第k只蚂蚁在一次迭代中走过的路径总长度，Δτ_ij(t)为t时刻路径ij上增加的信息素，B为常数，n为迭代次数，为所有蚂蚁的可行路径解的平均值；

根据模糊算法动态调整α/β参数；

其中，α为信息素启发因子，β为期望启发因子；

输出最优路径。

可选的，所述根据模糊算法动态调整α/β参数的步骤之后包括：

判断蚁群算法是否陷入局部最优；

若蚁群算法陷入局部最优，根据调整公式对信息素挥发系数进行动态调整，所述调整公式为：

ρ'＝Cρ (12)

其中，C为大于0小于1的常数，ρ∈(0,1)；

若蚁群算法没有陷入局部最优，信息素挥发系数保持不变。

可选的，还包括：输出迭代收敛曲线和最优路径长度。

可选的，α的取值范围为[1,4]，β的取值范围为[7,9]。

本发明具有下述有益效果：

本发明提供的蚁群算法的移动机器人路径规划方法，根据栅格法形成移动机器人的栅格地图，根据起点与终点的障碍物信息形成初始信息素的分布，根据临界障碍物影响因子形成期望启发函数，根据信息素更新公式对信息素的进行更新，根据模糊算法动态调整信息素启发因子和期望启发因子的参数，对信息素挥发系数进行动态调整。本实施例提供的技术方案能够获得更好的最优路径解，收敛速度更快。另外，本实施例通过仿真实验证明了上述技术方案是可行的以及有效的。

附图说明

图1为本发明实施例一提供的栅格地图模型的示意图。

图2为本发明实施例一提供的不同α取值对算法性能的影响示意图。

图3为本发明实施例一提供的不同β取值对算法性能的影响示意图。

图4为本发明实施例一提供的模糊推理框图。

图5为本发明实施例一提供的α模糊控制规则表图形。

图6为本发明实施例一提供的β模糊控制规则表图形。

图7为本发明实施例一提供的简单栅格地图的示意图。

图8为本发明实施例一提供的复杂栅格地图的示意图。

图9为本发明实施例一提供的蚁群算法的流程图。

图10a～图10c为本发明实施例一提供的移动机器人的最优路径轨迹图。

图11a～图11c为本发明实施例一提供的基本蚁群算法与改进蚁群算法的最优路径收敛曲线对比图。

具体实施方式

为使本领域的技术人员更好地理解本发明的技术方案，下面结合附图对本发明提供的蚁群算法的移动机器人路径规划方法进行详细描述。

实施例一

蚁群算法的灵感源于自然界中真实蚂蚁的觅食行为，是一种启发式智能进化算法。如今的蚁群算法因其并行处理、分布式计算和鲁棒性强等优点，已逐渐应用于移动机器人路径规划领域。尽管蚁群算法在路径规划领域中表现出了较好的效果，但仍然不能解决搜索时间长、容易停滞、收敛速度慢、局部优化等缺点。为了提高算法的性能，许多科学家做了相关的研究。Yen和Cheng提出了一种模糊蚁群算法，使蚁群算法在模糊控制下的迭代学习误差降到了最低。Imen等人融合蚁群算法和遗传算法各种的优点，提出了一种新的混合GA-ACO算法。Cheng等人在TSP模型下验证了蚁群算法的高效性。Wu等人通过将回滚策略应用到传统蚁群算法中以改善其性能。Rajput和Kumari将移动机器人在栅格地图中的定向运动与矢量运动结合起来，提出了一种快速蚁群算法。Li等人提出了一种基于动态参数和信息素更新机制的改进蚁群算法。Khaled和Farid提出了一种基于无限步长的蚁群算法。GAN等人提出了一种基于蚁群扩展路径优化的规划方法。Chen等人基于气味扩散原理，提出了一种快速两级蚁群算法，克服了传统蚁群算法固有的问题。Che等人针对防爆移动机器人三维路径问题的特点和传统蚁群算法在路径规划中的不足，提出了一种改进的蚁群优化算法(ACO)。

根据以上研究，本实施例提出了一种基于改进蚁群算法的全局路径规划方法，首先通过栅格法建立机器人环境地图，然后引入障碍物影响因子，提出新的信息素分布和更新策略，利用模糊算法控制关键参数，分段动态调整挥发系数。最后在多种复杂环境中进行仿真实验，结果表明该算法是可行和有效的。

移动机器人环境建模方法主要有栅格法、可视图法和自由空间法。栅格法可以很好的描述任何形式的障碍物，并且产生的二值信息特征又便于计算机的存储和更新，所以选用栅格法进行环境建模具有显著的优势。

图1为本发明实施例一提供的栅格地图模型的示意图。如图1所示，栅格法将移动机器人的工作空间分为网格单元，在栅格地图中，机器人的移动方向不再是任意方向，而是用八叉树所表示的8个行进方向。地图的栅格状态只有两种，即占据或自由，图中黑色栅格表示障碍物信息，白色栅格为机器人可活动区域，蓝色栅格为机器人的起始点，红色栅格为机器人的目标点。假设机器人的坐标为(x_g，y_g),则机器人的在地图序列编码可按下式计算得出：

其中，Num代表序列标号，N_x代表栅格地图行数，N_y代表栅格地图列数。

蚁群算法(ACO)模仿蚁群的觅食行为，在未知环境中寻找最优路径，是一种典型的启发式智能搜索算法。现有的研究结果表明，蚂蚁之间的合作交流是以信息素为基础进行的，信息素的浓度与路径长度成反比。在随机探索环境寻找食物的过程中，蚂蚁倾向于朝信息素浓度较高的路径移动，因为它们可以感知到信息素的强度。随着蚂蚁在同一条路径上行走的次数增加，路径上的信息素浓度也会增加，从而使更多的蚂蚁被路径所吸引，这种行为便代表了蚂蚁选择最优路径的原则。

为了提高路径规划的效率，在人工蚁群模型中引入了启发式函数η和禁忌表tabu_k的概念。在随机搜索算法中，采用启发式函数可以提高算法搜索效率。禁忌表tabu_k用于记录蚂蚁走过的节点，以确保蚂蚁不会返回到之前的节点。

在t时刻，蚂蚁k根据与目标点的距离信息以及路径上的信息素强度从当前节点i移动到一个未被访问的节点j，如果有多个未被访问的节点，蚂蚁k将根据以下公式确定节点之间的状态转移概率

其中，U＝{C-tabu_k}为蚂蚁k下一步可选节点集合；α是信息素启发因子，其值越高，蚂蚁在选择路径时受节点之间的信息素浓度影响越大；β为期望启发因子，其值越高，表示蚂蚁对当前节点与下一个节点之间距离的偏好越强；τ_ij(t)表示t时刻路径ij上的信息素浓度；η_ij(t)是期望启发函数，定义为节点i与节点j之间欧式距离的倒数，即：

其中，d_ij是两个相邻网格之间的距离，定义为：

当所有的蚂蚁完成路径搜索后，信息素随着时间的推移会不断蒸发，同时，蚂蚁经过路径上的信息素会增多，遗留在每条路径上的信息素将会更新，更新公式如下：

τ_ij(t+1)＝(1-ρ)τ_ij(t)+Δτ_ij (4)

其中ρ是信息素挥发系数，避免信息素的过多积累，ρ∈(0,1)；Δτ_ij(t)表示t时刻路径ij上增加的信息素；表示蚂蚁k在t时刻经过路径ij后增加的信息素，定义为：

其中，Q是信息素增强系数，为一常数；L_k为第k只蚂蚁在一次迭代中走过的路径总长度。

根据模糊控制算法的需要，本实施例定义如下变量：

定义1蚁群所得路径解的质量

Value＝L_best(n)-min{L_best(n-1),L_best(n-2),......,L_best(1)},Value∈[-6,6] (7)

定义2蚁群的进化程度

其中，n为当前迭代次数，N为总的迭代次数，L_best当代蚁群中的最短路径。

本实施例所设计模糊控制器是以Value以及Iter的值作为模糊输入，α/β的值为模糊输出的一个双输入双输出的模糊控制器。通过蚁群在不同阶段时期的收敛状态来动态调整α/β参数，使其在提高前期收敛速度的同时避免陷入算法的局部最优。

整个模糊控制算法分为3个阶段。在算法的初始阶段，各条路径上信息素的积累不足，差别不大，此时蚁群选择路径主要与期望启发因子β相关，所以应设置β值较大，α值较小。随着迭代的进行，到了算法的中期阶段，最短路径上的信息素浓度逐渐高于其他的路径，此时要加大信息素的正反馈作用，即增大α的值，相应则减小β的值。算法后期，此时部分路径上的信息素浓度已远高于其他路径，算法陷入局部最优的风险最大，因此应减小信息素浓度在路径选择中所占的比重，增加算法的随机性。所以α再次减小，β应进一步减小。在调整α/β的过程中，Value体现了蚁群的寻优能力，结合每一次计算出的最短路径解，更为精准的控制参数。

传统蚁群算法中的α和β通常从[1,9]中取值，通过大量实验，本实施例对α和β的最优取值进行了相关研究。从图2可以看出，当α＝1,3时蚁群算法在获得较短路径长度的同时也能保证一定的收敛速度，效果较好。为了进一步增强算法的动态性能，本实施例将α的取值范围定为[1,4]。图3的实验结果表明，随着β值的不断增大，蚁群算法的性能有了明显的改善。当β＝7,9时，蚁群算法最后能够稳定收敛，也可以获得最小路径长度，因此本实施例选择β的取值范围是[7,9]。

本实施例提供的模糊控制器采用mamdani推理，模糊推理流程图如图4所示。根据模糊控制算法建立输入输出规则，隶属函数采用对称三角形的均匀分布，模糊规则采用如下形式：

If Iter is A AND Value is B THENα/βis C

模糊推理规则见表1所示，图5和图6是模糊控制规则表图形形式。

表1 α/β取值的模糊规则表

初始信息素的合理分布有利于加快算法初期的搜索效率，本实施例所做的改进是根据起始点与终点的障碍物信息确定初始信息素的分布。在没有障碍物的情况下，最短路径便是起始点与目标点的连线，那么存在障碍物的情况下，只要沿着连线的方向前进并且在躲避障碍物的情况下尽可能的贴近障碍物，这种情况下的路径也是最短的。所以在初始状态，给这些与连线或者离障碍物近的地方赋予相较于其他栅格更大的信息素初始值，这样便能极大的加快前期的搜索效率。

图7和图8分别以不同栅格地图为例说明了如何分布初始信息素，在图中，“1”和“2”代表了临界障碍物影响因子的大小，值越大，初始状态分配的信息素越多。两点连线以及连线穿越过的障碍物四周会相应产生临界障碍物影响因子，而连线上的栅格相较于障碍物四周栅格更为重要，所以取较大值。

期望启发函数是两点之间欧式距离的倒数，表示蚂蚁向距离目标更近的栅格移动的概率更大，改进后的启发函数加入了临界障碍物影响因子，让蚂蚁向目标栅格移动的同时也兼顾障碍物的信息，用式(9)表示：

其中，g_i节点i处的临界障碍物影响因子，A为一常数，可以按照需求适当调整。

在传统蚁群算法中，当所有蚂蚁探寻完成后便会对蚂蚁经过的各条路径上信息素进行更新。但是到了算法的后期，最优路径上信息素的有了一定的积累，蚂蚁对最短路径的选择也已趋于稳定，这时如果仍然对所有路径上一些不必要的信息素进行更新，势必会降低最优值的稳定性，影响算法后期的收敛速度。本实施例提出了一种分阶段更新信息素的方法，可以有效的解决这一问题。为此引入常数B，当迭代次数n<B时，计算这一代中所有蚂蚁得到可行路径解的平均值对小于平均值的蚂蚁经过的路径进行信息素的更新。当n≥B时，仅对蚂蚁经过的最优路径进行信息素的更新。上述的改进机制如公式(10)和公式(11)所示，B是一个与总迭代次数N有关的常数。

从公式(11)可以得知，改进后的更新机制在算法前期只对获得了相对较短路径的部分蚂蚁进行信息素的更新，而在算法后期则只允许蚂蚁经过的最优路径更新信息素，这些改进能够加快算法收敛速度和寻优能力，同时避免了算法早熟。

局部最优指的是当路径上的信息素浓度随着迭代次数的增加而加大，若此时有一只蚂蚁找到了更好的路径，在它之后的蚂蚁由于受到次优路径的强大的信息素浓度干扰，所以它并不会沿着最优路径行走，此时则称为算法的局部最优解，若连续几代都没有找到最优解，则算法出现停滞现象。蚁群算法在迭代后期易陷入局部最优解的困境，因此，为了解决这一现象并加强算法后期的全局搜索能力，本实施例对信息素挥发系数ρ进行了动态调整。

改进的蚁群算法中信息素挥发系数ρ不再是常数，当算法陷入局部最优时，ρ值会相应减小，这会降低信息素浓度的正反馈作用，同时增大了算法的随机性。如公式(12)所示，其中C是大于0小于1的常数。

ρ'＝Cρ (12)

图9为本发明实施例一提供的蚁群算法的流程图。如图9所示，本实施例具体描述改进蚁群算法流程如下：

步骤1：初始化算法各参数，根据周围环境建立栅格地图，蚂蚁数量为m，总迭代次数为N，当前迭代次数为n，信息素启发因子为α，信息素期望因子为β，初始信息素分布按照4.2中方法确定，信息素挥发系数为ρ，信息素强度为Q，设置移动机器人的起始点和目标点。

步骤2：将蚂蚁放置在起始点，并把起始点添加到Tabu列表中。按式(1)计算节点ij之间的转移概率，利用轮盘赌法选择下一个节点j，并将当前节点添加到tabu禁忌表中。

步骤3：判断蚂蚁是否到达目标点，若是则根据禁忌表中记录的路径节点计算其长度，否则继续寻找下一个节点直至到达目标点。循环这一代中的所有蚂蚁，直到所有蚂蚁蚂蚁遍历完成，转到步骤4。

步骤4：根据式(7)(8)计算蚁群的进化程度Iter以及蚁群路径解质量Value，其值作为模糊控制器的输入，调整信息素启发因子α和信息素期望因子β的值。判断算法是否陷入局部最优，若是则按式(12)调整ρ的值，否则ρ值不变。依据式(11)的策略分段更新信息素。

步骤5：确定算法算法的迭代次数是否满足n≥N。若否则转到步骤2，让蚂蚁从起点重新开始迭代。若是则转到步骤6

步骤6：输出最优路径、迭代收敛曲线以及最优路径长度，算法结束。

为了验证本实施例提供的改进算法的正确性，本实施例利用MATALB R2014b搭建了3种不同复杂度的20x20栅格地图，在静态障碍环境中观察移动机器人是否可以找到可行和最优的路径。将改进蚁群算法(IACO)和基本蚁群算法(ACO)的计算结果进行了比较，并给出了相应的分析。该算法的主要参数如表2所示。

表2 算法初始参数设置

在相同参数下对两种算法进行了仿真实验，图10a-图10c是移动机器人的最优路径轨迹图，左图是基本蚁群算法的实验结果，右图是本实施例所提改进蚁群算法的实验结果，图11a-图11c是两种算法最优路径收敛曲线对比图。本实施例提供的技术方案能够获得更好的最优路径解，收敛速度更快。另外，本实施例通过仿真实验证明了上述技术方案是可行的以及有效的。

在图11a中，两种算法找到最优路径的迭代次数相差不大，但改进蚁群算法的找寻到的最短路径要优于基本蚁群算法，而且收敛速度更快，从d图中可以看出，到了迭代后期基本蚁群算法的最优路径仍有轻微波动，而改进蚁群算法因信息素更新机制的变化而能稳定保持最优路径。

在图11b中，改进蚁群算法较基本蚁群算法更早的搜寻到最短路径，算法后期基本蚁群算法陷入了局部最优解，而改进蚁群算法通过动态调整参数的方法跳出了局部最优的陷阱。

在图11c中，基本蚁群算法找到了最优路径并且也能保持稳定，但改进蚁群算法所用迭代次数更短，这意味着我们可以减少迭代次数N，缩短算法运行时间。

表3 算法实验结果对比

如表3中的实验数据所示，本实施例所提改进蚁群算法相较于基本蚁群算法能够获得更好的最优路径解，收敛速度更快。通过仿真实验，验证了本实施例所提算法的有效性，且算法性能要优于基本蚁群算法。

本实施例公开了一种蚁群算法的移动机器人路径规划方法，包括：根据栅格法形成移动机器人的栅格地图，根据起点与终点的障碍物信息形成初始信息素的分布，根据临界障碍物影响因子形成期望启发函数，根据信息素更新公式对信息素的进行更新，根据模糊算法动态调整信息素启发因子和期望启发因子的参数，对信息素挥发系数进行动态调整。本实施例提供的技术方案能够获得更好的最优路径解，收敛速度更快。另外，本实施例通过仿真实验证明了上述技术方案是可行的以及有效的。

可以理解的是，以上实施方式仅仅是为了说明本发明的原理而采用的示例性实施方式，然而本发明并不局限于此。对于本领域内的普通技术人员而言，在不脱离本发明的精神和实质的情况下，可以做出各种变型和改进，这些变型和改进也视为本发明的保护范围。

Claims (4)

1.一种蚁群算法的移动机器人路径规划方法，其特征在于，包括：

根据栅格法形成移动机器人的栅格地图，所述移动机器人在所述环境地图的序列编码的计算公式为：

其中，机器人的坐标为(x_g，y_g)，Num为序列标号，N_x为所述栅格地图的行数，N_y为所述栅格地图的列数；

根据起点与终点的障碍物信息形成初始信息素的分布；

根据临界障碍物影响因子形成期望启发函数，所述期望启发函数为：

其中，d_ij为两个相邻网格之间的距离，g_i为节点i处的临界障碍物影响因子，A常数；

根据信息素更新公式对信息素的进行更新，所述信息素更新公式为：

其中，Q为信息素增强系数，L_k为第k只蚂蚁在一次迭代中走过的路径总长度，Δτ_ij(t)为t时刻路径ij上增加的信息素，B为常数，n为迭代次数，为所有蚂蚁的可行路径解的平均值；

根据模糊算法动态调整α/β参数；

其中，α为信息素启发因子，β为期望启发因子；

输出最优路径。

2.根据权利要求1所述的蚁群算法的移动机器人路径规划方法，其特征在于，所述根据模糊算法动态调整α/β参数的步骤之后包括：

判断蚁群算法是否陷入局部最优；

若蚁群算法陷入局部最优，根据调整公式对信息素挥发系数进行动态调整，所述调整公式为：

ρ'＝Cρ (12)

其中，C为大于0小于1的常数，ρ∈(0,1)；

若蚁群算法没有陷入局部最优，信息素挥发系数保持不变。

3.根据权利要求2所述的蚁群算法的移动机器人路径规划方法，其特征在于，还包括：输出迭代收敛曲线和最优路径长度。

4.根据权利要求1所述的蚁群算法的移动机器人路径规划方法，其特征在于，α的取值范围为[1,4]，β的取值范围为[7,9]。