扩散强制蚁群算法求解越野机器人路径规划
时间：2023-06-16 09:40:05 来源：雅意学习网 本文已影响 人 
宋阿妮，包贤哲，付 波
（湖北工业大学电气与电子工程学院，湖北 武汉 430068）
随着人工智能与集成技术的不断发展，智能机器人开始运用于制造[1−2]、物流[3−4]、服务[5−6]、医学[7−8]等各行各业中，机器人在工作时需解决的最大问题是如何在复杂环境中找到行进路径并避开障碍物到达指定地点完成相关任务，提升智能机器人寻找最优路径的速度将能够大幅提升机器人工作的效率，为企业生产节省更多时间，具有较高的研究价值。该问题已成为当下人工智能领域研究的热点，国内外学者对其做过相关研究。
如文献[9]采用改进的人工蜂群算法提高了结果的收敛精度；
文献[10]构建有重构性的仓库空间模型并采用改进的A*算法[11]大幅降低机器人行进的路径长度；
文献[12]结合天牛须搜索算法和A*算法提出一种BACA*全局规划算法，并通过仿真证明得到的路径更加平滑，折点数更少；
文献[13]采用图论遍历的方法解决此机器人路径寻优问题；
文献[14]采用非线性策略改进灰狼算法[15]求解该问题，并用实例进行仿真证明了算法稳定性；
文献[16]将人工免疫免疫算法和粒子群算法结合起来强化算法的局部搜索能力并进行了实验仿真；
改进的人工免疫球算法[17]和粒子群算法[18−19]在求解类似路径问题上有着较好的效果。文献[20]提出基于障碍物位置和大小的搜索方法，能够显著提升收敛速度；
文献[21]针对动态环境下的机器人路径规划问题，对栅格进行凹凸化处理防止其陷入U型陷阱，并采用双层蚁群算法寻优，最终通过仿真验证其在动态环境下依旧能准确寻找最优路径；
文献[22]依据RRT算法原理提出一种多优化设计快速扩展随机树算法解决了传统算法收敛慢、路径平滑效果差等问题，实验结果显示其拥有良好的实时性和鲁棒性；
文献[23]结合模拟退火思想改进遗传算法让规划的路径更加安全可靠，实际应用性强；
文献[24]则研究了当工作环境超出机器人的感知范围的路径优化问题，但并未考虑到障碍物体积因素，实际应用性不强；
文献[25]结合栅格法、子区域划分法、模板模型法等策略，运用启发式搜索算法大幅提高了机器人的工作效率；
文献[26]采用改进智能水滴算法寻找路径，并用标准测试函数验证了算法的有效性。很多算法在机器人路径优化问题上都有着不错的效果，但是仍然存在最优路径收敛太慢，不平滑，收敛精度不高的问题。针对这些问题，提出了一种扩散强制蚁群算法（Diffusion Forced Ant Colony Optimization，DFACO），首先算法通过极值策略限制了信息素增长，防止算法陷入停滞，其次通过信息素扩散策略加强了较近蚂蚁的协作和关联，加快了算法的收敛速度，再通过强制刺激策略对陷入停滞的算法进行刺激使其脱离局部最优继续搜寻最优解，提高算法的搜的范围和粒子多样性，最后用DFACO、ACO、GA、FA算法在四个不同实例下求解最优路径，证明了该算法能够快速高效的为机器人规划出一条最短的平滑路径。
为了模拟野外山地的真实情况，将野外山地分割成大小面积相同的S∈[a×b]的栅格区域，共有a×b个区域方块，区域方块坐标由方块中心点代替。
其中黑色区域部分表示岩石、水坑、山峰、树木等障碍物，越野运输机器人以匀速从战场中任意K点向任意L点搬运物资，区域情况示意图，如图1所示。
图1 工厂模拟栅格示意图Fig.1 Schematic Diagram of Factory Simulation Grid
运输机器人在区域S内可以朝着上、下、左、右、左上、左下、右上、右下八个方向移动，若周围八个方向有黑色方块区域存在，则不能向此方向移动，其移动示意图，如图2所示。如图2所示，处于第5块方块区域内的运输机器人可以向除了第1块黑色区域以外的7个方向移动，要求运输机器人在不触碰任何黑色区域的情况下以最短的距离到达指定位置。
图2 运输机器人移动示意图Fig.2 Schematic Diagram of Transport Robot Movement
根据上述对问题的描述可知：
3.1 传统蚁群算法
蚁群算法是由Marco Dorigo于1992年在他的博士论文中提出的一种用来寻找优化路径的概率型算法，它的原理是模仿蚂蚁在寻找食物过程中发现路径的行为。
蚁群算法常用于旅行商问题，蚂蚁依据两个区域之间的信息素浓度和距离选择下一个目标区域，第k只蚂蚁从区域i前往下一个区域j的概率为：
式中：Q—常数；
Lk—蚂蚁k走过的路径总长度；
qij—路径ij；
Q—蚂蚁k走过的路径集合。
3.2 改进蚁群算法
3.2.1 大小极值改进策略
当蚂蚁在一条道路上走过的次数过多时，会导致该线路信息素含量远远超过其他线路，算法会因此进入停滞状态不再搜索其他线路。为了解决这一问题，给信息素浓度做出限制，信息素浓度的最大值为：
3.2.2 信息素扩散策略
蚂蚁释放信息素时往往可以向附近的同伴传递信息，根据这一特征，提出信息素扩散策略来提升距离较近的蚂蚁之间的协作能力，提升算法的收敛速率。信息素等类似挥发物质在空间中扩散近似服从正态分布，如图3所示。
图3 信息素扩散正态分布图Fig.3 Normal Distribution of Pheromone Diffusion
图中：x—距离信号源头O点的距离；
z—信息素浓度水平。
随着与信息素源O点距离的增加，信息素扩散浓度不断降低。将这样一个扩散场域平面模型在空间中展开并简化后，如图4所示。
图4 信息素扩散空间模型图Fig.4 Pheromone Diffusion Space Model Diagram
按照此改进方式，能够提高距离较近的不同蚂蚁之间的信息交流和协作，显著提高算法的收敛速度和精度。
3.2.3 强制刺激策略
蚁群算法很容易在迭代中期陷入停滞而无法得到最优解，为了能让算法能够在陷入停滞后再次启动开始搜索，对信息素迭代公式做如下改进。
其中，α1=0.5，α2=0.8。
假设在迭代次数达到T时种群的个体不再发生变化，此时强制刺激即改变α(t)，促使整个蚁群跳出局部最优解。除此之外，为了让算法能够区分优质、次优以及其他路径，改进其信息素变化量公式：
其中，不同迭代次数下的路径信息素增量不同，且路径总长度与当前最短路径Lbest的差越小，其信息素增量越大，越容易被选择。此改进能够区分不同路径的优劣程度，得到更多优质个体加快算法收敛。强制扩散算法的整体流程图，如图5所示。
图5 DFACO算法流程图Fig.5 DFACO Algorithm Flow Chart
假设存在四个不同野外地形需要用到运输机器人从野外山地某一点（START）到另外一点（GOAL）搬运物资，将四个不同地形空间统一分成S∈[20×20]m2的区域，四个地形中搬运物资的起始和到达位置都不同，需要在不触碰障碍物的情况下以最快的时间将物资送达目的地保证部队的正常运作。选取扩散强制蚁群算法（DFACO）、传统蚁群算法、遗传算法、萤火虫算法求解计算，设蚁群数量N=200，最大迭代次数tmax=100，其他参数，如表1所示。
表1 参数数值表Tab.1 Parameter Value Table
根据表1和上述文字中的参数设定，将四个不同地形的情况带入到四种算法中求解，得到的最终结果，如图6所示。
图6 四种野外地形在四种算法下的运输机器人路径图Fig.6 The Path Map of the Transportation Robot Under Four Algorithms in Four Wild Terrains
根据四种不同情况下四种算法计算出的越野运输机器人的路径曲线可以看到，DFACO算法得到的线路更短且路径更为的平滑连贯，相对于改进前的ACO算法，能够大幅度节省运输机器人运输路程中所花费的时间，其他的几种算法在不同的情况下表现不一。四种算法得到的最终的路径长度、迭代时间、粒子收敛率登结果，如表2，表3所示。
表2 三种基础算法的结果对比表Tab.2 Comparison Results of the Three Basic Algorithms
表3 ACO和DFACO改进效果对比表Tab.3 ACO and DFACO Improvement Effect Comparison Table
图7 情况1下四种算法迭代对比图Fig.7 Comparison of Four Algorithm Iterations in Case 1
根据表2和表3中的数据，对于四种情况下的越野运输机器人路径寻优问题，DFACO算法表现出了更好的性能和适应性，在四种情况下收敛速度和收敛精度以及收敛率相比于传统ACO算法都有了明显提升。针对情况1，四种算法的搜索迭代过程，如图6所示。根据图6迭代图中算法迭代情况可知，改进后的DFACO迭代时间更短且能够得到更优结果，能够为越野运输机器人快速提供最佳运输路径并满足特殊情况下的快速机动能力和物资运输的要求。
针对越野运输机器人运输工件路径优化问题，提出了一种扩散强制蚁群算法（DFACO），先用信息素极值策略给出信息素上限防止算法停滞，其次采用信息素扩散策略增加较近蚂蚁之间的联系和协作加快算法收敛，再结合强制刺激策略，通过改变信息素增量公式刺激陷入停滞后的蚁群让算法摆脱局部最优，提高算法的搜索范围和粒子多样性，最后分别用扩散强制蚁群算法、传统蚁群算法、遗传算法、萤火虫算法求解四种不同地形的野外运输实例，证明了提出算法的有效性，该算法能够快速准确的为越野运输机器人提供运输路径，降低运输时间提高工作效率为企业创造更多的收益，对该问题有良好的适应性，下一步将尝试用其他优化算法与该算法融合进一步提升算法的性能。
猜你喜欢 蚂蚁运输机器人 我们会“隐身”让蚂蚁来保护自己少儿科学周刊·儿童版(2017年5期)2017-06-29蚂蚁学苑创造·A版(2017年3期)2017-04-27受阻——快递运输“快”不起来专用汽车(2016年4期)2016-03-01比甩挂更高效,交换箱渐成运输“新宠”专用汽车(2016年1期)2016-03-01机器人来帮你少儿科学周刊·少年版(2015年4期)2015-07-07认识机器人少儿科学周刊·少年版(2015年4期)2015-07-07机器人来啦少儿科学周刊·少年版(2015年4期)2015-07-07关于道路运输节能减排的思考汽车维护与修理(2015年7期)2015-02-28蚂蚁找吃的等学苑创造·A版(2014年6期)2014-08-04综合运输家教世界·创新阅读(2009年5期)2009-05-26
