机器人避障路径规划的改进蚁群算法

摘要

路径规划中的避障问题是移动机器人控制中的一个热点问题，已经得到了广泛的研究。然而，现有的蚁群算法仍然存在工作区域通道狭窄、计算量大等缺点。针对上述技术问题，提出了一种改进的蚁群算法进行路径规划。本文提出了一种新的加权邻接矩阵来确定步行方向，通过重新设计步行规则避免了狭窄的通道。并引入最佳蚁群和最差蚁群进行信息素调整，以促进搜索过程。该算法保证了机器人在存在狭窄通道的情况下能够找到满意的路径。仿真结果表明了该算法的有效性。

1.介绍

在过去的几十年里，机器人控制技术得到了迅速的发展。如今，人们期望机器人能够完成各种任务，如收集环境信息、准确避开障碍物、快速路径规划等。在路径规划方面，大量的工作集中在人工势场法[1]，蚁群算法[2]和遗传算法[3.］．针对蚁群算法的收敛速度和容易陷入局部最优的问题，[4]提出在蚁群算法搜索过程中针对特定问题增加人工局部潜在优化算法，减少了蚁群算法的盲目性，提高了搜索能力。文献[5]中加入环境中的局部路径信息来初始化信息素和路径选择概率，提高了算法的收敛性，克服了算法的早熟问题。在[6，提出了一种新的动态搜索诱导因子来改变蚁群算法的性能。动态搜索模型提高了最优解的质量，提高了算法的收敛速度。文献[7]提出了自适应模型，并在最大最小蚂蚁系统的基础上引入了适者生存的进化策略，实现了参数调整和信息素更新，加快了算法的收敛速度。回顾已有的文献，尽管蚁群算法在处理路径规划方面取得了巨大的成就，但仍然存在一些缺陷，包括指数爆炸[8]及未能绕过狭窄通道[9］．指数爆炸是指精细网格划分以指数方式增加搜索范围，导致计算时间较长。有些文章简单地把机器人看成一个质点，没有考虑狭窄的通道。窄通道问题是指机器人由于自身体积、刚性结构和轨迹的限制，无法通过窄通道。为了解决这一问题，一些文章提出了环境地图重建的方法，即有意地将障碍物映射到一个或多个网格中。具体来说，如果它小于一个网格，则将其计算为一个网格。亦建议将障碍物的边界扩展至适当的大小[7，10.］．这些方法除了存在一些缺陷外，都是相当有效的。研究表明，当障碍物间距大于机器人宽度且小于机器人宽度的两倍时，模拟路径效果良好。然而，当两个障碍物距离很近且实际距离小于或等于机器人本身的宽度时，模拟路径无效。另外，还提出了绕行的方法。文献[9]通过向外扩展障碍物构建网格地图，并相应地采用直角绕过和对角行进的方法避开障碍物。直角绕过的方法本质上是通过在安全网格中心之间行走来远离障碍物。文献[11.]向外扩展六个可选择的方向:上、下、左、右、下左和上右。在这六个方向上，机器人倾向于倾斜前进[12.，13.］．根据障碍物位置的不同，分别定义了相应的旁路模式。虽然两种方法都是为了绕过狭窄的通道，但其性能都是保守的。可以看出，这些方法规划的路径相对较长。如何在有效避免狭窄通道的同时减小路径总长度是本文研究的重点。本文将机器人的运动方向扩展到8个，并分析了不同位置下机器人的运动方向，通过设置新的行走规则，提出了一种改进的蚁群算法。

本文的贡献可以总结为以下方面。（a）网格向外扩展到八个方向，以获得更好的路径计划。（b）建议新的行走规则绕过狭窄的过道。（c）通过提出分析计算方法减少了计算量。

2.算法的基本原理

２.１.基于网格的环境地图建模

为了准确采集环境并对狭窄通道进行检测，[14.使用用于构造地图，可以获得环境形状信息并确保结果的准确性。安全区域和危险区域在网格中定义，其中安全区域由没有障碍物的区域表示，危险区域由障碍物表示[15.］．用直角坐标绘制网格时，黑色区域表示作物生长区域(危险区域)，白色区域表示开放区域(安全区域)。危险区域(黑色部分)的网格中心坐标为障碍物的中心点，安全区域(白色部分)的网格中心坐标为机器人的可行路径点[16.］．

２.２.环保配方

众所周知，障碍物的分布决定了机器人的通过性，这一点在图中很容易说明1．可以看出，分布A、B、C保证了一个机器人的高通过性。而分布D为机器人旁路通道较窄的情况，通过性较低。

从全局来看，机器人在网格中的位置不同，方向也不同。通常情况下，这些位置可以分为9种不同的情况，如图所示2所示。

根据位置将机器人的运动细分为不同的方向，消除了不必要的计算，加快了搜索过程。

3.改进的蚁群算法

３.１.行走的规则

如前所述，在现有的蚁群算法中，当只有狭窄的通道可通过时，很难找到满意的路径。解决方案将在本小节中提出，它遵循以下两个步骤。

步骤1。考虑机器人运动的方向是八：左上角，左下角，右上角，右下方，较低，左，左右。 我表示当前网格在x轴上的坐标，和j表示当前网格在y轴上的坐标。为了计算任意两个网格之间的距离，米表示周围网格的x轴坐标，n表示周围网格的y轴坐标。当条件(1)满足时，下一个运动的方向将是上、下、左、右方向。当条件(2）持有，它将是左上角，左下角，右上方或右下方。

在图中3.，我_米表示任意两个网格在x轴和上的距离j_n表示y轴上任意两个网格的距离。当两个安全网格并排时，横向距离我_米1和纵向距离是多少j_n是0;当两个安全栅格并置时，横向距离我_米是0;纵向距离j_n是1;如果两个安全网格是对角线，则横向距离我_米是1，纵向距离是多少j_n是1。两个距离都是0。

步骤2。根据机器人的八个运动方向[17.，我们可以标记当前网格的八个方向，见图4，根据公式(3.), (4), (5)和(6)．然后我们可以计算每个方向上的距离。

下式给出了窄通道存在的准则: 在标量G (m, n) R表示障碍物的指示物，也是环境矩阵中的一个元素。当值为1时，表示障碍;否则等于0。

当情况在(3.满足），它表明狭窄的过道是左上方的方向。同样，这种情况（4）与左下角相对应;（5)对应右下;（6)对应于右上角。

３．２．全球运动方向

摘要基于栅格图的蚁群算法路径规划在计算加权邻接矩阵时存在指数爆炸问题，且加权邻接矩阵的含义过于单一。针对这一问题，本文提出了一种解析计算的优化方法。与前一种方法相比，该方法更加灵活，可以根据需要定义不同的行走原理，同时也可以处理和计算更高精度的网格。

如前所述，用9个不同的位置，机器人的运动分别表示出来。例如，位置5的机器人有八个不同的运动方向。根据图1，可以看出，狭窄的通道可能出现在左上、右上、左下、右下方向。当(3.）-(6)是真的，意思是周围没有狭窄的通道;除此之外，还有一条狭窄的通道。通过这种方法，可以很容易地识别出窄通道和非窄通道。

为了计算栅格中相邻两个安全栅格之间的距离，需要有以下公式: 在矩阵用于存储网格之间的距离;表示环境矩阵的大小。右边的…7)为距离公式，左侧为新的加性群邻接矩阵，其中矩阵的水平和垂直坐标表示编号方法定义的环境矩阵的网格。

３．3.启发式函数设计

众所周知，在基本蚁群算法中，不考虑全局信息，只局部求解下一步的方向。因此，它得到的是局部最优解而不是全局最优解。

为了使用全局信息，客观指导因子被引入启发式功能。可以获得从电网-i到网格j的机器人-k的概率 在哪里τ_ij(t)为路径上信息素浓度（I，J）在时间t;η_ij表示网格-i到网格-j的可见度;λ_乔表示网格-j向目标点o延伸的程度;α为信息启发式因子系数;β为期望启发式因子系数;γ为引导因子系数;禁忌_k表示ant-k的禁忌列表。有关禁忌列表的更多信息，请参阅[18.］．- 表示ant-k当前可以选择的网格集合，其中N表示所有光栅的集合[19.］．

目标引导因子由蚂蚁在路径规划过程中，根据当前位置从全局方向进行下一步。给出了目标制导因子的计算公式 在哪里年代_乔表示通过搜索新的加权邻接矩阵得到的当前网格-j与目标网格-o之间的最短安全距离D．λ_乔表示当前网格与目标网格之间的最短安全距离的倒数。最短安全距离越大，引导因子越小，最短安全距离越小，引导因子越大，选择的可能性越大。

3．4．最优最差信息素更新功能的设计

在路径搜索过程中，路径上的信息素不仅会随着时间的推移而挥发减少，而且还会随着通过路径的蚂蚁数量的增加而增加。由于蚁群算法中的信息素受到所有蚂蚁的影响，许多蚂蚁对信息素的更新产生影响，这会加速进化过程，加快搜索速度。因此，设计信息素更新功能，如公式(10.), (11.)和(12.)． 在哪里ρ（τ(i, j))为全局信息素挥发系数;l_gb为机器人的最佳路径长度;l_吉瓦为蚂蚁所走的最坏路径的长度;和问就是信息素的强度增加。

3.5。所提出的算法的流程

具体来说，改进后的蚁群算法的步骤可归纳为:

步骤1。收集环境信息，得到环境网格图。然后，设定起点和终点;初始化蚁群参数。

步骤2。从(1）-(6)，确定当前位置以及网格周围是否有狭窄通道。

第3步。根据图中网格的不同位置，计算所有网格与周围网格之间的距离2并构造了一个新的加权邻接矩阵。

第四步。在开始处设置m只蚂蚁，根据图中新加权邻接矩阵与信息素在不同位置分布的距离选择下一个节点j2．

第5步。将node-j添加到ant-k的Tabu列表中。

第6步。重复步骤4到5. ant到达目标点，并保存每个蚂蚁的路径（n，m）和路径长度（n，m），从中获得最佳路径（n，m）和最佳路径长度选择（长度），平均路径长度均匀_n。计算该循环中的M蚂蚁。

第7步。根据公式更新路径信息素(10.), (11.)和(12.)．

第8步。判断算法是否达到最大迭代次数，则算法终止并输出最优路径routh_best，否则重复步骤3到步骤7。

改进后的蚁群算法路径规划流程图如图所示5．

4.仿真结果

为了验证所提出的算法的有效性和优越性，MATLAB平台进行以下仿真。在这个模拟中，每代机器人数量，米,为30;迭代时间K=200;此外，(8,11)中的参数设置为α= 1，β= 7,ρ= 0.43，γ= 3,和Q = 100。在这个模拟中考虑的环境是一个狭窄的通道。

仿真结果如图所示6- - - - - -9．从图中可以看出6(一)在相同的窄通道环境下，三种不同算法生成的三条路径是不同的。通过与[7，可以看出，本文方法规划的路径绕过了两条狭窄通道而到达目标点，而[7]没有避免狭窄的过道。和....相比 [11.]，建议方法的两种途径及[11.避免狭窄的过道，但前者相对较短。

为了比较收敛速度，选择了两种没有狭窄通道的工作环境。从图7，人们可能看到三种算法的路径在图中基本相同7（a）图。从图7（b），但可以观察到所提出的算法收敛于20代左右的点。[的算法7汇聚了大约40代人，[11.大约30代。通过仿真可以看出，该算法的收敛速度比[7，11.］．

此外，[7]也用于模拟。数字8（a）表明本文算法生成的路径与[11.)是相同的。但两者的收敛速度不同;从图中可以看出，前者更快8（b）．

选择与20的相同尺寸的环境信息矩阵20.现在，比较这两种方法计算新的邻接矩阵。不同的方法成本不同的持续时间。结果显示在表格中1．

为了进一步验证所提出的解析计算方法的优越性，图中给出了不同尺寸环境矩阵的比较9．

从图中可以看出9本文提出的分析方法消耗了比全局方法更少的时间。随着环境矩阵的增加，全局方法的消耗时间呈指数增长，而分析方法所消耗的时间与较小的系数成比例地增加，这更有效，耗时较少。

5.结论

利用二维sdf - slam，考虑狭窄通道，实现了环境信息的采集;得到一个精确的环境光栅图。同时，通过改变行走规则，可以绕过狭窄的通道。基于行走规则，从各方面不同位置得到新的窄通道加权邻接矩阵，减少了计算量和计算时间。该方法通过选择细网格来提高精度。虽然搜索范围呈指数增长，但搜索时间并不是呈指数增长，而是系数很小的比例增长。与现有算法相比，该算法能在最短时间内找到一条到达狭窄通道的满意路径。

数据可用性

用于支持本研究发现的数据可由通讯作者要求提供。

的利益冲突

作者声明没有利益冲突。

致谢

根据专家的建议，我们对论文进行了修改，提高了论文的质量。天津市科技计划重大项目(15ZXZNGX00290)资助;天津市科技计划(重大项目)项目(17ZXYENC00080);天津市科技计划(重大项目)，18YFZCNC01120。

参考文献

1. S. S.Ge和Y.J.Cui，“移动机器人路径规划的新潜在功能”机器人和自动化的IEEE交易，第16卷，第5期。5，页615 - 6202,2000。视图:出版商网站|谷歌学术
2. M. Dorigo, M. Birattari，和T. Stützle，《蚁群优化》，IEEE计算智能杂志， vol. 1, no. 14，第28-39页，2006。视图:出版商网站|谷歌学术
3. A. Tuncer和M. Yildirim，“基于改进遗传算法的移动机器人动态路径规划”，计算机与电气工程，卷。38，不。6，pp。1564-1572，2012。视图:出版商网站|谷歌学术
4. J.H·刘，J.G.杨，H.P.Liu等，“基于潜在场蚁群算法的移动机器人的全球路径规划方法”中国农业机械学会交易，卷。46，没有。09，pp。18-27,2015（中文）。视图:谷歌学术
5. Q. Zhang，J. C. MA，W.X等，基于改进蚁群算法的移动机器人路径规划，东北大学学报(自然科学版)第34卷第3期11, pp. 1521-1524, 2013。视图:谷歌学术
6. X. M. You，S. Liu和J.Q.1V，“基于动态搜索策略的蚁群算法及其在机器人路径规划中的应用”，“控制与决策，第32卷，第2期3，页552-556,2017。视图:谷歌学术
7. 张建民，“基于优化蚁群算法的机器人路径规划”，“基于优化蚁群算法的机器人路径规划”，自动化技术及应用第35期11，第10-29页，2016。视图:谷歌学术
8. “基于改进蚁群算法的机器人路径规划，”测控技术，第37卷，第2期4，第28-31页，2018。视图:谷歌学术
9. B. F. Zhang，Y.王和X. L. Zhang，“移动机器人路径规划基于人工潜在田间方法”应用力学与材料， vol. 577, pp. 350-353, 2014。视图:出版商网站|谷歌学术
10. 张伟，马勇，赵海东等，“基于改进蚁群算法的智能移动避障路径规划”，控制与决策， pp. 1-10, 2019(中文)。视图:出版商网站|谷歌学术
11. “基于蚁群优化算法的机器人路径规划”，刊于国际创新计算技术会议论文集，ICICT 2016，页1-6，哥印拜陀，印度，2016年8月。视图:谷歌学术
12. y . Z. C. Yee和S. G. Ponnambalam，“基于蚁群优化的移动机器人路径规划”2009 IEEE/ASME国际先进智能机电一体化会议论文集，AIM 2009，第851-856页，新加坡，2009年7月。视图:谷歌学术
13. 郭建平，“基于蚁群系统的移动机器人路径规划”第四届遗传与进化计算国际会议论文集(ICGEC 2010)，PP。2010年12月，深圳210-213。视图:出版商网站|谷歌学术
14. j。fosel, K. Tuyls，和J. Sturm，“2D-SDF-SLAM:基于符号距离函数的激光扫描仪SLAM前端”智能机器人技术与应用，2015,29 (5):758 - 762，pp。1949-1955，德国，2015年10月。视图:谷歌学术
15. 陈建军，叶飞，蒋涛，“基于蚁群优化算法的避障路径规划”第17届IEEE国际通信技术会议论文集，ICCT 2017， pp. 1434-1438，成都，2017年10月。视图:谷歌学术
16. j·g·刘,基于改进蚁群算法的移动机器人路径规划研究，东北大学，辽宁，2009。
17. R. Rashid, N. Perumal, I. Elamvazuthi, M. K. Tageldeen, M. K. A. Khan，和S. Parasuraman，“使用蚁群优化的移动机器人路径规划”第二届IEEE国际机器人和制造自动化研讨会研讨会，罗马2016年，第1-6页，怡保，马来西亚，2016年9月。视图:谷歌学术
18. F. Glover，“整数编程的未来路径和人工智能链接”，计算机和运营研究，卷。13，不。5，pp。533-549,1986。视图:出版商网站|谷歌学术|Mathscinet.
19. 白建林，“基于负反馈机制的蚁群算法及其在机器人路径规划中的应用”，计算机集成制造系统(中文)。视图:谷歌学术

版权

版权所有©2019王洪军等。这是一篇发布在知识共享署名许可协议，允许在任何媒介上不受限制地使用、传播和复制，但必须正确引用原作。