第4期 蒲兴成，等：分组教学蚁群算法改进及其在机器人路径规划中应用 ·767· 缺陷，本文提出一种新回退机制，即当蚂蚁陷入U 转角。通过简化算子分别简化为图2(a)、图2(b) 型障碍时，将该蚂蚁所处节点直接标记为地图上 和图2(c)中的路径。 障碍节点并实时更新地图，然后将蚂蚁回退到路径 上一节点重新进行路径选择，重复此操作直到另 30 一可达节点出现时结束回退。通过回退机制将U 2.5 型障碍填充为矩形障碍，从而避免后续蚂蚁再次 2.0 陷入同一U型障碍，因此能提高算法收敛速度。 1.2.3信息素更新改进策略 1.0 传统蚁群算法信息素更新策略中，蚂蚁经过 的所有路径均采用相同的信息素更新强度。当蚁 0.5 群完成一轮迭代后，所有可行路径L信息素更新 0 0.5 1.0 1.5 2.0 2.5 3.0 增量相同，这就导致传统蚁群算法路径搜索的盲 x/m 目性增大，蚂蚁无法快速锁定长度更短的路径。 (a)90°转角 因此，在改进的信息素更新策略中，增加一个动态 30 累加参数c,增强蚁群寻找最优路径的引导作用。 25 c用于记录L成为当前最短路径迭代轮数，即累 2.0 加最优路径信息素浓度，当L为当前最短路径时， c将加1。此外，将L分别与当前局部最优路径 1.0 Loe和全局最优路径Lelob进行比较。根据比较结 果，对可行路径信息素浓度采用分级更新强度 0.5 Q和Q2。一般来讲，Q2>Q,本文中，Q2数值为Q数 0 0.51.01.52.02.53.0 值的两倍。这样能使得Lg路径节点信息素增量 x/cm (b)90°转角 更大，进一步扩大全局最优路径在后续迭代中对 蚁群路径搜索引导作用，同时也能避免由于Q导 3.0 致的蚁群陷人局部最优。改进信息素具体更新为 2.5 AT=CuQ.=Lca 2.0 CijQ2/Lk:Lt=Lgobal ∫c+l,Lk=minLe 夏15 c=c,其他 1.0 改进信息素更新策略引导蚁群往最优路径方 0.5 向搜索，可以进一步加快算法收敛速度，增强算 法性能。 0.51.01.52.02.53.0 x/cm 1.2.4路径简化算子 (c)45°转角 若路径存在过多角度较小转角，则机器人在 图13种冗余转角 移动过程中可能会出现失去平衡现象。此外，通 Fig.1 Three redundant corners 过蚁群算法迭代规划出的路径如果存在大量转 角，该路径就不一定是最优路径。因此，如何消 3.0 除冗余转角是路径规划时必须考虑的一个问题。 2.5 路径简化算子”根据三角形两边之和大于第三 2.0 边原理消除冗余转角。改进路径简化算子根据路 径中相邻3个节点构成的夹角角度进行路径简 复15 化。若夹角内节点为可达节点，则将该转角简化 1.0 为直线路径。因此，路径简化算子不仅可以缩短 0.5 路径长度，而且可以增大转角角度，让机器人运 0 0.5 1.0 1.52.02.53.0 动更加平滑。如图1(a)与图1(b)中分别为存在 x/cm 90°冗余转角的两种情况，图1(c)中存在45冗余 (a)90°简化路段缺陷，本文提出一种新回退机制，即当蚂蚁陷入 U 型障碍时，将该蚂蚁所处节点直接标记为地图上 障碍节点并实时更新地图，然后将蚂蚁回退到路径 上一节点重新进行路径选择，重复此操作直到另 一可达节点出现时结束回退。通过回退机制将 U 型障碍填充为矩形障碍，从而避免后续蚂蚁再次 陷入同一 U 型障碍，因此能提高算法收敛速度。 1.2.3 信息素更新改进策略 Lk ci j ci j Lk Lk ci j Lk Llocal Lglobal Q1 Q2 Q2 Q1 Q2 Q1 Lglobal Q1 传统蚁群算法信息素更新策略中，蚂蚁经过 的所有路径均采用相同的信息素更新强度。当蚁 群完成一轮迭代后，所有可行路径 信息素更新 增量相同，这就导致传统蚁群算法路径搜索的盲 目性增大，蚂蚁无法快速锁定长度更短的路径。 因此，在改进的信息素更新策略中，增加一个动态 累加参数 ，增强蚁群寻找最优路径的引导作用。 用于记录 成为当前最短路径迭代轮数，即累 加最优路径信息素浓度，当 为当前最短路径时， 将加 1。此外，将 分别与当前局部最优路径 和全局最优路径 进行比较。根据比较结 果，对可行路径信息素浓度采用分级更新强度 和 。一般来讲， > , 本文中， 数值为 数 值的两倍。这样能使得 路径节点信息素增量 更大，进一步扩大全局最优路径在后续迭代中对 蚁群路径搜索引导作用，同时也能避免由于 导 致的蚁群陷入局部最优。改进信息素具体更新为 ∆τi j = { ci jQ1 / Lk , Lk = Llocal ci jQ2 / Lk , Lk = Lglobal ci j = { ci j +1, Lk = minLk ci j, 其他 改进信息素更新策略引导蚁群往最优路径方 向搜索，可以进一步加快算法收敛速度，增强算 法性能。 1.2.4 路径简化算子 若路径存在过多角度较小转角，则机器人在 移动过程中可能会出现失去平衡现象。此外，通 过蚁群算法迭代规划出的路径如果存在大量转 角，该路径就不一定是最优路径。因此，如何消 除冗余转角是路径规划时必须考虑的一个问题。 路径简化算子[17] 根据三角形两边之和大于第三 边原理消除冗余转角。改进路径简化算子根据路 径中相邻 3 个节点构成的夹角角度进行路径简 化。若夹角内节点为可达节点，则将该转角简化 为直线路径。因此，路径简化算子不仅可以缩短 路径长度，而且可以增大转角角度，让机器人运 动更加平滑。如图 1（a）与图 1（b）中分别为存在 90°冗余转角的两种情况，图 1（c）中存在 45°冗余 转角。通过简化算子分别简化为图 2（a）、图 2（b） 和图 2（c）中的路径。 0.5 1.0 1.5 x/cm 0 2.0 2.5 3.0 0.5 1.0 1.5 2.0 2.5 3.0 0.5 1.0 1.5 x/cm 0 2.0 2.5 3.0 0.5 1.0 1.5 2.0 2.5 3.0 0.5 1.0 1.5 x/cm 0 2.0 2.5 3.0 0.5 1.0 1.5 2.0 2.5 3.0 (b) 90° 转角 (c) 45° 转角 (a) 90° 转角 y/cm y/cm y/cm 图 1 3 种冗余转角 Fig. 1 Three redundant corners 0.5 1.0 1.5 x/cm 0 2.0 2.5 3.0 0.5 1.0 1.5 2.0 2.5 3.0 x/cm x/cm (c) 45° 简化路段 y/cm y/cm y/cm (a) 90° 简化路段 (b) 90° 简化路段 第 4 期 蒲兴成，等：分组教学蚁群算法改进及其在机器人路径规划中应用 ·767·