龙珊珊，高 倩，高曼曼

（石家庄理工职业学院，河北 石家庄 050000）

1 引言

机器人可以辅助或者代替人类完成重复性强、危险性高的活动，但是移动机器人的工作环境一般较为复杂，对机器人行走路线的最优化和安全性提出了较高要求。行走路径的优劣决定了机器人的行驶安全性和工作效率的高低[1]，因此研究机器人路径规划问题具有重要意义。

路径规划是指在含有不同障碍物的环境中，按照一定的评价准则（长度最短、安全性最高、平滑性最好等），规划出一条从起点到终点的最优无碰路径[2]。机器人路径规划可以分为环境建模和路径搜索两个方面的内容。环境建模是指将机器人实际的工作场景抽样为机器人可以识别的数学模型，常见方法包括栅格法、连通图法、拓扑图法等[3]。路径搜索可以分为传统路径搜索算法和仿生搜索算法两类，其中传统路径搜索算法包括人工势场法、模拟退火法、模糊逻辑法等，仿生搜索算法包括蚁群算法、遗传算法、粒子群算法等。人工势场法根据障碍物斥力和目标引力规划出路径，路径的平滑性较好，但是当障碍物较多时容易出现“死点”[4]。模拟退火法可以解决大规模组合优化问题，但是却需要较长的退火时间，使算法收敛速度慢。模糊逻辑针对驾驶员的驾驶行为形成专家系统，根据路径查表获得驾驶路径，此方法在环境突变时可能失效，因此灵活性较差[5]。仿生搜索算法是对生物优化的某个过程进行模拟，实现算法的智能化，是当前机器人路径规划的研究热点，。文献[6]使用人工势场法对蚁群算法的启发信息进行改进，此方法提高了算法的收敛速度，并减小了路径的转弯次数。文献[7]在遗传算法中引入新的遗传因子，提出了协同进化遗传算法，该方法加快了算法的收敛速度，并改善了解的质量。文献[8]可以根据地图的不同情况自适应地调节蚁群算法参数，在保证解的质量同时提高了优化效率。仿生搜索算法存在的共性问题是算法优化能力的深化，当前关于仿生搜索算法的研究均集中在这一问题上。

针对机器人在栅格环境下的路径规划问题，提出了复合启发信息蚁群算法的路径规划策略。该方法以蚁群算法为基础，融入了两种启发信息，给出了基于改进蚁群算法的规划策略，实现了减小路径长度、提高规划效率的目的。

2 问题描述与建模

2.1 问题描述

这里研究的问题为栅格环境下机器人的路径规划问题，包括3个方面的内容：（1）栅格环境模型的建立；（2）规划目标的设定；（3）规划算法，其中规划算法是核心内容。栅格模型的建立是指使用一定尺寸的方形栅格对工作环境进行分割，机器人行驶时以栅格为基本单元。栅格尺寸的设定需参考机器人直径、环境中障碍物尺寸及复杂程度，一般来讲，机器人尺寸较大、障碍物尺寸较大、障碍物分布较简单时，栅格尺寸设置值较大。

为了保证行驶路径的绝对安全，对障碍物一般使用膨化处理方法，即当某栅格中存在障碍物时，则让障碍物充满该栅格[9]，如图1所示。

图1 障碍物膨化Fig.1 Obstacles Expansion

另外，机器人对实际的工作环境是无法识别的，为了将实际工作环境转化为机器人可以识别的模式，根据栅格特性为其赋不同的属性值，当栅格中存在障碍物时为其赋值为1，当栅格中不存在障碍物时为其赋值为0。按照以上规则，图1的工作环境可以转化为0-1矩阵，为：

对于属性为0的可自由行驶栅格，为了对走过的自由栅格和未走过的自由栅格进行区分，将走过的自由栅格赋值为-1，未走过的自由栅格属性不变。则机器人可明确区分障碍物栅格、已走过的自由栅格和未走过的自由栅格。

在栅格环境下，路径规划的目标为机器人从起始栅格到达目标栅格的路径最短，即目标函数为：

式中：LSG—起始栅格S与目标栅格G之间的路径长度。

2.2 传统蚁群算法与分析

传统蚁群算法中，蚂蚁对栅格的选择包括8方向搜索和4方向搜索两种，因8方向搜索的路径平滑性更好、搜索效率更高，这里使用8方向搜索法。蚂蚁对栅格的选择是在启发信息和信息素的双重引导下实现的。启发信息由目标栅格对蚂蚁的启发作用而设定，信息素是模拟蚁群协作时的交流介质而给出的。蚂蚁对邻域内自由栅格的选择概率为[10]：

式中：i—蚂蚁所在的当前栅格；j—邻域内的待选自由栅格；k—蚂蚁编号；t—迭代次数—蚂蚁k由栅格i选择栅格j的概率；τij(t)—蚂蚁择栅格j的启发信息，τij(t)=，LjG—栅格j与目标栅格G的距离；α—启发因子；ηij(t)—路径ij间的信息素浓度；β—信息素因子；allowedi—栅格i邻域的自由栅格。

在传统蚁群算法中规定，每完成一次算法迭代，则进行一次信息素更新。信息素更新包括信息素挥发和信息素残留两个方面，即：

式中：ρ—挥发系数；Δτij(t)—蚂蚁在路径ij上残留的信息素；M—蚂蚁数量—蚂蚁k在路径ij上残留的信息素；Lk—蚂蚁k的路径长度。

蚁群算法存在路径多样性与路径收敛的矛盾，当路径多样性较好时，说明蚂蚁搜索的范围较大，但同时也说明蚂蚁搜索的随机性较大，路径的收敛性较差。当路径收敛性较好时，说明蚂蚁搜索的方向性较好，但是同时说明蚂蚁容易陷入某一局部最优路径，蚂蚁的探索能力较差。上述问题是传统蚁群算法存在的共识问题。

3 复合启发信息蚁群算法

3.1 复合启发信息

为了平衡蚁群算法的路径多样性与收敛性，基于目标栅格的引导作用提出了两种启发信息。在传统蚁群算法中，一般将待选栅格j与目标栅格G的距离倒数作为启发信息，也就是说将待选栅格与目标栅格的远近作为一种启发。但是，直观地讲，蚂蚁由当前栅格沿直线到达目标栅格是最佳路径，因此将目标栅格与当前栅格的连线方向作为启发信息，其启发性必然强于距离信息的启发性。按照这一思路，使用待选栅格j与目标栅格G间的向量夹角θ构造启发信息。夹角示意图，如图2所示。

图2 待选栅格向量与目标栅格向量夹角Fig.2 Angle Between Selected Grid Vector and Target Grid Vector

在图2 中，当前栅格坐标记为(xi，yi)，待选栅格坐标记为(xj，yj)，目标栅格坐标记为(xG，yG)。由直观理解可知，蚂蚁搜索的最佳方向为D→iG=(xG-xi，yG-yi)，实际搜索方 向为D→ij=(xj-xi，yj-yi)，在此将两个向量的夹角定义为两者之间的真角，因此取值范围为θ∈[0，π]。以夹角θ为基础，构造两种启发信息。启发信息1为：

启发信息2为：

对于启发信息1 和启发信息2，当θ∈[0，π]范围内，ηij1和ηij2均为单调递减函数，这意味着夹角θ越小（此时待选栅格越靠近最优方向），对应栅格对蚂蚁的启发能力越强，蚂蚁更容易选择这一栅格；夹角θ越大（此时待选栅格越远离最优方向），对应栅格对蚂蚁的启发能力越弱，蚂蚁越不容易选择这一栅格。以上分析表明，2种启发信息的构造方法是合理的。启发信息1和启发信息2的ηij值随夹角θ的变化趋势，如图3所示。

图3 启发信息变化趋势Fig.3 Changing Tendency of Inspiration Information

经计算图3中的交点A横坐标为148.1°，这意味着几乎在整个θ的取值范围内，当ηij值相同时，相应的有θ1>θ2。也就是说，在相同启发信息范围的情况下，夹角θ1的变化范围大于夹角θ1的变化范围，说明启发信息1可以指导蚂蚁进行更大角度范围的搜索，而启发信息2的方向性较强，可以指导蚂蚁沿着最佳方向进行搜索。为了对上述分析进行更加直观的解释，设置ηij1=ηij2>0.5，则夹角θ1∈(0，90°)，θ2∈(0，39.7°)，如图4所示。由图4可直观看出，启发信息1的搜索范围更广，而启发信息2的搜索方向性更强。

图4 启发信息1和启发信息2对比Fig.4 Comparison of Inspiration Information 1 and Inspiration Information 2

3.2 复合启发信息蚁群算法

根据蚁群算法的路径规划需求，算法前期需要较大的搜索范围，以便对工作区域的最优路径进行广泛搜索；算法后期需要较强的方向性搜索，以便算法收敛于最优路径附近，并进行最优路径附近的细致搜索。按照算法上述的需求分析，提出的改进蚁群算法思想为：前期设置较大数量的启发信息1蚂蚁，以便进行大范围搜索；后期设置较大数量的启发信息2蚂蚁，以便进行方向性强的小范围细致搜索。

根据算法的需求分析，算法前期蚁群中设置更多的启发信息1类的蚂蚁，随着算法的迭代，启发信息1类的蚂蚁数量逐渐减少，而增加启发信息2类的蚂蚁。这种设置方法兼顾了前期大范围搜索需求和后期方向性较强的搜索需求。蚁群规模记为N，算法的最大迭代次数记为tmax，启发信息1类的蚂蚁数量记为N1，启发信息2类的蚂蚁数量记为N2，则两类蚂蚁的数量设置为：

式中：t—当前迭代次数。

分析式（6）可知，随着算法的迭代，启发信息1类的蚂蚁逐渐减少，启发信息2类的蚂蚁逐渐增多，满足前文的构造需求。

两类蚂蚁之间的交流通过信息素实现，即通过路径上残留的信息素浓度可以实现蚂蚁之间的交流与协作。

3.3 基于复合启发信息蚁群算法的路径规划步骤

根据复合启发信息蚁群算法的原理，结合栅格环节下机器人路径规划的特点，设置基于复合启发信息蚁群算法的机器人路径规划步骤为：

（1）设置栅格环境规模、起点栅格、终点栅格；设置算法参数，包括蚂蚁数量、信息素因子、启发因子、信息素挥发系数、算法最大迭代次数等；（2）将蚂蚁放置在起始栅格，开始路径规划；（3）两类蚂蚁按照各自的启发信息进行栅格选择，得到各自规划出的路径；（4）判断是否所有蚂蚁完成了一次迭代，若否则等待；若是则迭代i次数＋1；（5）判断是否达到最大迭代次数，若否则转至（2）；若是则输出最优路径，算法结束。

4 仿真验证

4.1 启发信息效果验证

首先在（30×30）规模的栅格环境下验证路径规划效果，工作环境中障碍物栅格的比例设置为10%和20%两种情况，起始栅格设定为左上角栅格，目标栅格设置为右下角栅格。算法的参数设置为：蚂蚁规模为50，信息素因子为1.5，启发因子为4.0，信息素挥发系数为0.4，算法的最大迭代次数为100，计算环境为Win⁃dowsl0、i5CPU、内存8GB，仿真软件为Matlab2017。

在障碍物栅格占比为10%和20%两种情况下，分别使用启发信息1蚁群算法和启发信息2蚁群算法进行10次路径规划，障碍物占比为10%的最优路径，如图5所示。障碍物占比为20%的最优路径，如图6 所示。在一些实验中得到的最优路径是重合的，因此图中给出的最优路径数量小于10。

图5 障碍物占比10%的规划结果Fig.5 Planning Result of 10% Barrier Environment

图6 障碍物占比20%的规划结果Fig.6 Planning Result of 20% Barrier Environment

对比图5和图6中两种启发信息蚁群算法的规划结果可以看出，10次规划得到的路径中，启发信息1蚁群算法规划的路径范围更加广泛，这意味着启发信息1 蚁群算法的搜索全局性更好；而启发信息2蚁群算法规划的路径范围相对较小，这意味着启发信息2蚁群算法搜索的路径方向性更好。该实验现象与3.1节的设计原理完全一致，验证了两种启发信息设置的合理性。

4.2 与传统蚁群算法比较

为了进一步验证复合启发信息蚁群算法在栅格环境中路径规划的可行性，设置（30×30）规模的栅格工作环境，分别使用复合启发信息蚁群算法和传统蚁群算法进行10次路径规划，统计10次最优路径的最短距离、标准差、迭代次数，如表1所示。复合启发信息蚁群算法和传统蚁群算法搜索的最短路径，如图7所示。

表1 传统蚁群与复合启发蚁群对比Tab.1 Comparison of Compound Inspiration Ant Colony and Traditional Ant Colony

图7 复合启发蚁群与传统蚁群规划结果Fig.7 Planning Result of Compound Inspiration Ant Colony and Traditional Ant Colony

结合表1和图7可以看出，10次规划的最优路径中，传统蚁群算法规划的最优路径长度为68.021，路径的标准差为4.251，复合启发信息蚁群算法规划的最优路径长度为52.545，路径标准差为2.211，这说明复合启发信息蚁群算法规划的最优路径比传统蚁群算法规划结果更优，且路径规划的稳定性更强，这是因为复合启发信息蚁群算法中引入了两种启发信息，启发信息1搜索的全局性好，而启发信息2搜索的方向性好，这样兼顾了算法的优化能力和稳定性，因此复合启发信息蚁群算法的规划结果优于传统蚁群算法。

4.3 与其余改进蚁群算法比较

为了进一步对比规划策略与其余规划策略的路径优劣，选择文献[11]的改进蚁群算法进行比较。在（30×30）规模的栅格环境中，分别使用复合启发信息蚁群算法和文献[11]蚁群算法进行10次路径规划，得到的最短路径，如图8所示。

图8 复合启发蚁群与文献蚁群规划结果Fig.8 Planning Result of Compound Inspiration Ant Colony and Ant Colony in Essay

经统计，复合启发蚁群算法规划的最短路径长度为43.355，规划出最优路径的迭代次数为41；文献[11]参数优化蚁群算法规划的最短路径长度为46.113，规划出最短路径的迭代次数为57。以上数据表明，复合启发信息蚁群算法规划的路径更短，且规划效率更高。这是因为文献[11]只是使用粒子群算法对蚁群算法的参数进行了优化，并未从原理上解决多样性和收敛性之间的矛盾。而这里提出的复合启发信息蚁群算法在算法中引入了两种启发信息，一个启发信息具有更大的搜索范围，另一个启发信息具有更好的搜索方向性，因此兼顾了算法的多样性和收敛性，从根本上改善了算法性能。综合以上分析，本文提出的复合启发信息蚁群算法在栅格环境路径规划中是有效的，可以得到更短路径，且规划效率较高。

5 结论

研究了机器人在栅格环境下的路径规划方法，提出了两种启发信息，将两种启发信息融入到蚁群算法中，得到了兼顾多样性和收敛性的蚁群算法。将复合启发信息蚁群算法应用于路径规划中，得到以下结论：

（1）提出的两种启发信息中，启发信息1具有较大的搜索范围，启发信息2具有更强的搜索方向性；

（2）复合启发信息蚁群算法规划的路径优于传统蚁群算法，且规划效率更高。