基于蚁群算法下机器人的优化避障路径

基于蚁群算法下机器人的优化避障路径

赵毅

（山西大同大学，山西省大同市，037000）

摘 要

蚁群算法为MATLAB中一种常见的算法。该算法主要应用于智能机器人的移动规划。其主要作用是对障碍物的排斥以及对不同启发因子的改变再到关于路径选择等一系列计算,来增强机器人的自主避障能力。除此之外增加了多种路径的选择;通过不同的算法分析与比较，选择出一种最为合适的避障路径。局部信息素和全局信息素，轮盘赌阈数等，是影响结果的关键因素。本文则是使用蚁群算法时算出最优解和最差解,旨在降低由于局部最优给该算法造成的影响。根据实验结果显示，该算法找到最优路径的概率最高且能有效降低迭代次数、缩短运行时间，令收敛效果大大提高，搜索能力也有所提升。

关键词：路径规划;智能机器人;蚁群算法;最优解

一、引言

随着科技的进步与发展，云计算机、智能机器人等技术愈发的成熟，而在研发智能机器人的过程中也出现了许多的算法与技术。本文所采用的就是一种常用的机器人的避障算法。该算法用于求解优化问题的群体智能算法[ 1] ，这种算法的设计思路来源于自然界中的多种群体性动物行为活动的模拟。这种具备智能化特征的算法为人们提供了具有更高便利度，且更容易找到最优路径的方法。蚁群算法（AntColonyAlgo- rithm，ACA）提出者系意大利知名的M.Dorigo联合多名科学家在[2]上个世纪90年代初在深入研究蚂蚁的工作状态及团队合作模式、合作期间交互信息的方法之后，模仿蚁群的各种形态提出的一种能够体现常规性、智慧化特征的仿生类群体算法。

二、蚁群算法的原理及模型的建立

2.1算法的原理

通过研究分析，蚂蚁是一种只会进行部分简单性行为的昆虫个体，其独立个体并无强大的思考及行为能力，但组合而成的蚁群其组织性非常明显、自智能性也比较显著。通过该行为特点，可以发现，蚁群之间存在着部分联系，可以使得蚂蚁在分叉路选择时，通过某种信息做出正确的选择。有相关研究表明，蚂蚁沿着路径爬行时，会将一种具备挥发性特征的气体物质留在路上该物质考科一有效的给其他的蚂蚁提供方向，让其选择出正确的路径，学者专家将该物质称之为信息素。路径最短的信息素浓度最高，而随着路径的延长，信息素会不断挥发，加上途中没有其他蚂蚁再次留下信息素，残留于其他路径的信息素就会伴随着时间的推移而变得越来越淡，蚂蚁也将不会选择该路径。对于最短路径，不断地有蚂蚁经过，随着信息素的积累，最后，信息素浓度达到最高，蚁群会直接选择该路径，以达到最短路径的目的。上述的研究也能证明蚂蚁需在感应到残留移路径中的信息素浓度后才能与其他蚂蚁间接沟通，这便是蚂蚁群虽然面对着多条路径，却可找到一条正确的、最优路径的主要原因。

2.2模型的建立

下文将借助基本蚁群算法构建数学模型，再以此分析m个城市的经典TSP问题[5]最终得出如下分析结果:

m个城市的经典TSP问题可以解释为人工蚂蚁在选定某个城市之后，从中挑选出任意一个城市，并将其设为起始点，随后，并基于随机原则对下个城市进行访问，且对剩余的所有城市的访问次数都为一次，最终返回至起始点，其目的是为了找寻出一条距离最短的路径。在该过程中的道路选择的转移概率[3

p(t)=í,j ∈ allowedks ∈ allowdek

p(t) 指的是于t时刻，蚂蚁k从元素（城市）i移动至元素（城市）j的转移几率；α代表的是信息素在蚁群找寻路径区间的相对重要程度，β指的是在蚁群找寻路径期间，启发式信息对于该过程的相对重要程度；τij(t) 代表t时刻，经过城市i和城市j时可能出现的信息量；此处以禁忌表tabuk(k=1, 2, ⋯, m) 代表第k只 蚂蚁目前已探索的元素（城市）集合，证明式中不会再次出现禁忌表内的元素（城市），使得最终计算出的最优路径具备较高的合法性。

假设移动机器人是于二维空间中运行，且空间中不会出现动态障碍物，可利用栅栏法对其的运行环境进行建模。为了保证最终建出的模型具有较高精准度，文中把移动机器人于工作范围内的起始点设为S（图中绿色点所示）终点位置为N（坐标图中红色点所示）、已事先掌握存在于区域中的各种静态障碍物的尺寸与详细位置，图中黑色块所表示障碍物，而黑色块所表示的障碍物代表此障碍物是实体，只得进行绕行方式，不得进行横穿。依据移动机器人的移动范围及其的实际尺寸，把工作区域细分成间隔相同的格子，并在下图环境中把机器人设为质点，其路径用相应的折线所表示。（注：在此算法中黑色障碍物的位置及大小均可以自主设置）

信息素更新是算法中最关键的一步因为蚂蚁是通过分辨同伴的信息素来进行选择路径的，而信息素的分布与多少直接决定了蚂蚁的行径方向。使用对于此算法必须进行信息素的更新检查。

三、仿真实验与分析

为了对经过改进的算法进行验证，以保证其的精准度与可行性，文章将于PC端以内存为416GB的处理器、为Intel（R） Core （TM） i5-10200H的 MATLAB R2018a展开两次仿真实验。

仿真实验一

第一个仿真环境系静态栅格图，其尺寸为20 x 20，当中机器人的起点、终点分别是绿色点及红色点，黑色方块为障碍物。第一次仿真采用了蚁群算法中的RAS算法。所对应的参数取值为启发式因子为5、信息素因子和信息素挥发因此分别是1、0.5，信息素强度与排序蚂蚁的个数则分别为100及6，实验次数为10，显示出10个不同的迭代结果。在相同的参数下，对比其他的算法，可以看出RAS的多样性曲线与动态曲线较为简单，其迭代次数也明显少于其他的算法，例如，与AS算法进行比较，可以看出，AS的算法时间短，但是AS所做出的曲线图较为复杂，迭代次数也较多，所以在效率上，RAS相对于AS算法较高。

图3-1  RAS算法下的路径图

图3-2   AS算法下的路径图

  可以看出相较于AS算法，RAS算法可以更加容易的找到最优解，经过较少次数的迭代就可以将原始的曲线拟合出来，达到最优化，虽然相比于时间上，RAS比AS所需要的时间长，但是效率要比AS更高，同时所做出的结果也比AS做得更加的稳定与贴合。

仿真实验二

   本次实验将采取蚁群算法中的所有算法，将这六种算法进行分析与对比，最终得出选出最为合适的一种。

图3-3  5种算法的路径图

四、结论

   对于蚁群算法，可以得出结论，在该种障碍物的位置下，EAS为最优解，所用的 迭代次数最小，同时与真实值的误差也是最小的，但是在不同障碍物位置，以及不同的参数情况下，这个结论也是有可能不成立的，所以在选择蚁群算法展开计算时，要考虑信息素强度及信息素因子与信息素挥发因子，还有实验次数与排序蚂蚁的实际数量等因素给整个算法造成的影响。

参考文献

【1】李智.智能优化算法研究及应用展望[J].武汉轻工大学学报,2016,35(4):

【2】DorigoM,ManiezzoV,Colorni A.PositiveFeedbackasaSearchStrategy[J].TechnicalReport,1991:91-016.

【3】段海滨,王道波, 朱家强,等.蚁群算法理论及应用研究的进展[J].控制与决策,2004,19(12):1321-1326.

【4】赵娟平，高宪文,符秀辉.改进蚁群优化算法求解移 动机器人路径规划问题[J].南京理工大学学报。

【5】朱庆保，杨志军.基于变异和动态信息素更新的蚁群 优化算法[J].软件学报,2004,15(2):185-192.

【6】王俭,肖金球，赵鹤鸣.目标信号导航的机器人路径 二次优化[J].电子测量与仪器学报,2007,23(5)： 73-76.

【7】曾明茹，徐小勇，罗浩，等.多步长蚁群算法的机器人 路径规划研究[J],小型微型计算机系统，2016, 1(2) ：366-369.

【8】张万绪，张向兰，李莹.基于改进粒子群算法的智能 机器人路径规划[J].计算机应用,2014, 34(2): 510-513.