【www.zhangdahai.com--其他范文】
王子扬 ,夏学文
（1.闽南师范大学计算机学院,福建漳州 363000；
2.闽南师范大学物理与信息工程学院,福建漳州 363000）
路径规划技术是目前自主导航规划研究的核心技术之一.路径规划指的是在起点和终点间找到一条路径，该路径不仅需要躲避所有的障碍物，且其长度为两点间的最优路径解或近似最优解，并做到用时消耗较少.近年来，国内外学者对机器人的路径规划问题进行了很多研究，并提出多种算法用于解决路径规划问题.包括人工势场法、A*算法、Dijkstra算法等.随着机器人领域的发展，对移动机器人的工作环境、工作效率和稳定性要求逐步提升，传统的路径搜索算法在路径规划问题中缺乏实用性和有效性.现在大多数采用群智能优化算法去解决路径规划问题，例如粒子群优化算法、遗传算法、鱼群算法、蚁群算法等.因蚁群算法(ant colony optimization,ACO)在机器人路径规划问题上具有算法收敛速度快、鲁棒性强等优势，因此ACO 在路径规划问题上被广泛应用.但因传统的蚁群算法存在搜索时间较长，得到的解为次优解等问题，各学者近年也提出很多蚁群改进算法.周之平等[1]在蚁群算法中通过动态调整启发式信息和信息素浓度的影响因子，提高算法搜索效率，增强算法自适应能力.马飞宇等[2]通过利用差异化种群间的相互协作，使蚁群具有全局视野的自适应步长，解决蚁群算法因视野的局部性导致无法搜索到最优步长的问题.Khaled 等[3]提出一种用刺激概率来诱导蚂蚁选择下一个网格，并基于无限步长的原理构造新的启发式信息函数，提高蚂蚁的视野能见度，扩大搜索空间.张天瑞等[4]提出信息素挥发因子随迭代过程动态更新策略,同时利用遗传算法的交叉操作对蚁群算法求得的解进行再次提优，提高算法效率并减少移动路径的无效拐点.Gao等[5]提出了4种增强启发式蚁群算法(EH-ACO),设计了新的信息素扩散机制，使蚂蚁以较大的概率向目标方向搜索，从而提高搜索效率.并利用路径合并策略优化最优解.
虽然上述改进算法从不同方面弥补蚁群算法缺陷，但并未考虑算法在前期搜索阶段的盲目性.通过对上述改进算法分析，蚁群算法的启发式信息函数和状态转移规则应动态满足蚁群在不同阶段的需求.本文通过评估函数改变算法初始信息素浓度分布，对后续蚂蚁起到引导作用，改进启发式函数增强蚁群的局部可见性，同时引入阻尼系数动态调整启发式信息权值，从而控制启发式信息的影响程度，并引入自适应状态转移规则，提高算法收敛速度和寻优能力，弥补传统蚁群算法的缺陷.最后通过对比实验验证自适应蚁群算法(adaptive ant colony optimization,AACO)的可行性和优越性.
通过对机器人工作环境进行建模，才能更清晰直观的研究机器人路径规划的过程.现大多数研究采用可视图法[6]、栅格地图法[7].其中栅格地图法在该问题中具有易实现、数据结构简单、简单直观的优点，故本文选取栅格法对移动机器人工作环境进行建模[8].
栅格法是把工作环境均匀的划分成大小相同的方形栅格.栅格模型图如图1所示，对各个栅格赋值0和1 以代表栅格不同的状态，黑色栅格代表障碍物，机器人只能在白色栅格区域内行走.机器人的下一步可选栅格是其相邻的八个方位的空白栅格，移动方位图如图2所示.每个栅格有对应的编号，从左向右、从上至下编号分别为{1，2，3，4，…，n}，栅格的编号S和其对应坐标(x,y)有如下关系：
图1 栅格模型图Fig.1 Grid model diagram
图2 机器人移动方位图Fig.2 Robot movement orientation
其中：ceil为向上取整运算；
mod为求余运算；
x是工作环境的行数；
y是工作环境的列数.
受蚂蚁觅食行为的启发，意大利学者M.Dorigo 于1991 年提出了ACO[9]，并用该方法成功应用于旅行商问题(TSP)的求解.此后，该算法便引起了许多研究者的广泛关注，在优化各类路径规划问题中均取得了不俗的表现[10].
蚂蚁在觅食过程中，会在走过的路径上释放一种信息素，该信息素会吸引其他的蚂蚁，信息素含量越大，对别的蚂蚁吸引程度越强.路径上的信息素会挥发和堆积，最终各个路径上会形成信息素浓度差，越来越多的蚂蚁前往信息素浓度较高的路径上，形成一条最优路径.
以往的研究表明，ACO 中，每个蚂蚁下一节点的确定和信息素浓度的更新是影响算法性能的两个关键因素.下一节点的确定与启发式函数值和信息素浓度有关，信息素浓度的更新对蚂蚁的探索领域有影响[11].假设蚂蚁k从节点i前往下一个节点j，则状态转移公式[12]为
其中：C是下一个可选节点的集合；
τij(t)是信息素浓度；
ηij(t)是启发式信息函数值；
α的值表示信息素浓度对蚂蚁的吸引程度，值越大，蚂蚁向信息素浓度高的路径移动的概率越大；
β是启发式信息重要因子，β值越大，蚂蚁会更倾向于移动至启发式函数评价较好的路径，即β是启发式函数值对路径选择的影响；
ηij(t)是当前节点到下一节点的期望程度[13]；
其表达为
式(3)中，djg为下一节点j与目标节点g之间的欧氏距离.
蚂蚁在探索过程中会在其走过的路径上分泌信息素，使其探索过的路径上的信息素浓度高于未探索的区域.在探索完成后，路径上的信息素会根据挥发系数ρ挥发，形成负反馈[14-15].信息素更新策略为
其中：ρ是信息素挥发系数；
Δτij(t)是路径〈i,j〉上信息素增量，其更新过程如式（5）所示.
其中：Q是信息素总含量，一般取固定值；
Lk是蚂蚁k行走路径的总长度.
3.1 初始信息素分布
在ACO地图中每个栅格的信息素初始浓度值为同一固定值.该初始化方法的优点是每个蚂蚁初始的搜索方向完全随机，搜索行为多样，但这会也使得算法初期搜索较为盲目，降低了算法的搜索效率.针对这一问题，根据起点、终点、当前节点和下一节点的相对位置关系计算初始信息素浓度.具体实现如下：
式(6)中：d为两点间的欧氏距离（其下标S、E、i、j分别代表起点、终点、当前节点和下一节点）；
参数a0是用来控制初始信息浓度的大小.从式（6）可以知道，当dSi+dij+djE的值越接近dSE的值，路径〈i,j〉上的信息浓度越大；
反之，路径〈i,j〉上的信息浓度越小.通过有效利用地图信息，例如起点、终点、当前节点和下一节点之间的相对位置信息，构建初始信息素浓度的差异化分布，可使算法在初期的搜索更具有启发性，蚁群在初期的搜索效率也更高.
3.2 启发式函数
从式（3）可知，ACO 中的启发式信息值和下一可选节点到目标点距离成反比.换言之，蚂蚁在选择下一节点时会以更大概率选择距离目标点更近的节点.而在实际问题中，当前节点的相邻节点到目标点的距离差异很小，所以各个相邻节点的启发式函数值差异也很小，即当前节点的局部可见性较弱.这也将大大降低启发式信息对蚂蚁状态转移的影响，这一现象在大规模栅格环境中尤为突出.在蚁群算法搜索的初期，各个栅格的信息素浓度差异较小，这时局部可见性对算法的搜索能力有较大的影响.在搜索后期，应减少启发式函数值在状态转移公式（2）中的权重占比，从而提升算法收敛速度.为了增强目标的启发式信息，同时动态地控制启发式信息对路径选择的影响，本文引入一个阻尼系数ε来控制启发式信息性能的方法.新的增强启发式局部可见性公式，如下：
式中:Ncmax 为最大迭代次数；
Nc是当前的迭代次数，其中λ为一个大于零的常数，用来确保分母不为零，同时也可以控制启发式信息的影响性.ε可理解为一缩放因子，是一个随着迭代次数逐渐变小的参数.搜索初期，参数ε更大，因此启发式信息对个体搜索行为的影响更大，使蚂蚁不易陷入局部最优解，提高局部搜索能力；
随着搜索过程的不断推进，ε值也不断减小，因此启发式信息对搜索行为的影响也逐渐降低，加快算法收敛速度.
3.3 改进状态转移规则
在ACO 中，采用传统的状态转移规则和轮盘赌选择方式，促使蚂蚁选择当前解中的较优值.但随着迭代的进行，种群容易陷入局部最优解，出现算法停滞的现象.为了提高算法的搜索效率和质量，现采用了伪随机状态转移规则.新的状态转移公式如下：
从式(9)可知，当q≤q0时，蚂蚁将从其当前所在节点i的相邻节点中选择启发式函数值和信息素浓度积最大值的节点作为移动的下一节点.当q＞q0时，该蚂蚁则首先计算出下一可选节点集合中各节点启发式函数值和信息素浓度的积，再利用轮盘赌的方式确定下一节点.可以看出，蚂蚁选择下一节点是采用确定性模式还是概率模式取决于q0的值.当q0较大时，蚂蚁以确定性方式选择下一节点的概率更大，可加快收敛速度，但易陷入局部最优，降低蚁群的全局搜索能力；
相反，当q0较小时，蚂蚁以概率模式，即轮盘赌模式，选择下一节点的概率更大，因此，蚁群跳出局部最优的能力更强，算法的全局搜索能力更高.
在利用ACO 求解路径规划问题时，一般希望蚁群在搜索初期具有更加随机、多样的搜索行为和更强的全局搜索能力.到搜索后期时，为了提高算法的求解精度，希望蚁群能确定地选择距离目标节点更近的节点作为下一节点.因此，为了满足蚁群在不同搜索阶段的需求，本文设计了一种自适应调整的q0.其定义如下
其中，C是一个[0,1]之间的常数.设Nc为当前迭代次数，Lbest为(Nc-1)代最短路径长度，为(Nc-2)代最短路径长度.若(Nc-1)代最短路径长度大于(Nc-2)代最短路径长度，则说明该搜索领域继续探索的价值不大，应扩展搜索空间，所以q0的值应该减小，此时应更倾向用轮盘赌方式选择，提高全局的搜索能力；
若(Nc-1)代最短路径长度小于(Nc-2)代最短路径长度，说明搜索的解朝好的方向发展，说明此区域具有探索价值，所以q的值应该增大，更倾向用确定性选择模式，加大搜索力度.
3.4 AACO算法实现流程
步骤1利用栅格法构建移动机器人的二维静态环境地图，并对改进蚁群算法的参数进行初始化.
步骤2利用式（6）计算出各个栅格的信息素浓度，对全局初始信息素浓度进行差异化处理.蚂蚁从起点出发，利用改进的状态转移规则计算出下一步节点，前往下一节点，将蚂蚁的上一节点加入禁忌表tabu中.
步骤3判断蚂蚁是否到达终点，若到达，则对全局信息素浓度值进行更新，并存储该蚂蚁行走的路径长度及路径上的栅格序号.
步骤4循环往复步骤2和步骤3，直至所有蚂蚁完成搜索到达终点.
步骤5若当前迭代已经完成，则退出循环，给出算法的求解结果。若没有达到最大迭代次数，则转至步骤（2）.
AACO算法的伪代码如下：
为了验证本算法的综合性能，本文利用仿真平台MATLAB2020b 对自适应算法在两种不同规模的地图上进行了实验.
第一组实验采用的地图为10×10 的栅格地图，地图设置见图3 所示，其中左上角栅格为起始点，右下角栅格为目标点.算法的参数为：蚂蚁数量m=20，信息素浓度影响权值α=1，启发式信息影响权值β=7，最大迭代次数Ncmax=100，信息素挥发系数ρ=0.4.用ACO 和AACO 分别运行同一机器人工作环境，实验结果见图3～4和表1所示.
图3 和图4 分别是算法得到的最优路径及算法的收敛过程.由图3～4 可以看出，传统蚁群算法在路径规划过程中路径出现了无效的拐点，导致无法获取最优解，且随着该路径上信息素浓度的不断增加，ACO无法跳出局部最优，进行收敛，导致运行结果为次优解；
而AACO 并未出现无效拐点，得到的最优路径解优于ACO的解.由结果对比表1得，相比于ACO，AACO在收敛迭代次数方面提升78.85%，在算法效率上更优.由此可知：对比ACO，AACO更高效可行，具有优越性.
图3 ACO与AACO优化得到的路径对比Fig.3 Optimized path comparisons between ACO and AACO
图4 ACO与AACO的收敛曲线Fig.4 Convergence processes between ACO and AACO
表1 ACO与AACO的仿真结果对比Tab.1 Simulation results between ACO and AACO
在第二组实验中，为了进一步验证AACO在规模更大地图的可靠性和优越性，构建了和文献[16]中相同的工作空间，即20×20的栅格地图进行建模，起始点和目标点依然是左上角栅格和右下角栅格，对比算法为文献[16]提出的算法.算法的参数为：蚂蚁数量m=30，信息素浓度影响权值α=1，启发式信息影响权值β=8，最大迭代次数Ncmax=100，信息素挥发系数ρ=0.3.图5 和图6 是两种算法的最优路径和收敛过程图，相关的数据结果如表2 所示.从表中可看出，相比于文献[16]算法，AACO 在寻找最优路径方面提升了3.85%，说明AACO的寻优能力强于文献[16]中算法.从算法的收敛速度上来看，文献[16]中算法经过运行21 代后收敛于其最优路径，而AACO 在第8 代即收敛到最优路径解，收敛速度得到明显提升.AACO 在改进的启发式信息函数作用下，有较好的跳出局部最优解作用，使得算法不至于陷入局部最优解，由此验证了算法的有效性.
表2 AACO与文献[16]中算法的仿真结果对比Tab.2 Comparison of simulation results between AACO and the algorithm in literature[16]
图5 AACO与文献[16]中算法优化得到的路径对比Fig.5 Optimized path comparisons between AACO and the algorithm in literature[16]
图6 AACO与文献[16]中算法的收敛曲线Fig.6 Convergence processes between AACO and the algorithm in literature[16]
另外，为了验证算法的通用性和其快速收敛能力，还建立了和文献[17]中相同的地图环境进行对比实验.算法的参数为：蚂蚁数量m=20，信息素浓度影响权值α=1，启发式信息影响权值β=7，最大迭代次数Ncmax=100，信息素挥发系数ρ=0.4.图7和图8是两种算法的最优路径和收敛过程图，相关数据结果如别表3所示.从表3可看出，文献[17]和AACO均可找到最优路径，但文献[17]算法需迭代19次才收敛于最优路径，而AACO 迭代10 次即收敛于最优路径，相比于文献[17]算法，AACO 在收敛迭代次数上提升47.36%.即AACO在算法收敛速度方面有较大提升.
表3 AACO与文献[17]中算法的仿真结果对比Tab.3 Comparison of simulation results between AACO and the algorithm in literature[17]
图7 AACO与文献[17]中算法优化得到的路径对比Fig.7 Optimized path comparisons between AACO and the algorithm in literature[17]
图8 AACO与文献[17]中算法的收敛曲线Fig.8 Convergence processes between AACO and the algorithm in literature[17]
为提升ACO 性能，弥补其搜索效率低、过早停滞局部最优解等缺陷，本文对ACO 进行改进.首先，在种群初始化阶段，利用地图信息，如起点、终点、当前节点和下一节点之间的相对位置信息等，构建了初始信息素浓度的差异化分布，使算法的初期搜索更具启发性，搜索效率也更高.其次，设计了一个新的启发式函数，用来增强本地的可见性，并通过引入阻尼系数控制启发式信息在算法运行过程中的影响.最后，提出自适应状态转移规则，通过动态控制算法的空间搜索状态，满足不同搜索阶段对搜索能力的需求.仿真实验验证了AACO在机器人路径规划方面的有效性和优越性.
猜你喜欢 栅格蚂蚁节点 栅格环境下基于开阔视野蚁群的机器人路径规划重庆理工大学学报(自然科学)(2022年1期)2022-02-18超声速栅格舵/弹身干扰特性数值模拟与试验研究北京航空航天大学学报(2021年5期)2021-06-09概念格的一种并行构造算法河南科技学院学报(自然科学版)(2020年2期)2020-05-22结合概率路由的机会网络自私节点检测算法小型微型计算机系统(2020年5期)2020-05-14采用贪婪启发式的异构WSNs 部分覆盖算法*火力与指挥控制(2020年1期)2020-03-27Crosstalk between gut microbiota and antidiabetic drug actionWorld Journal of Diabetes(2019年3期)2019-04-16反恐防暴机器人运动控制系统设计大科技·C版(2018年11期)2018-10-21我们会“隐身”让蚂蚁来保护自己少儿科学周刊·儿童版(2017年5期)2017-06-29蚂蚁学苑创造·A版(2017年3期)2017-04-27基于栅格地图中激光数据与单目相机数据融合的车辆环境感知技术研究汽车文摘(2016年1期)2016-12-10本文来源：http://www.zhangdahai.com/shiyongfanwen/qitafanwen/2023/0608/608564.html
