平滑的移动机器人路径规划基于改进蚁群算法

文摘

针对问题的收敛速度慢,容易陷入局部最优,穷人和平滑的传统蚁群算法在移动机器人路径规划,提出了一种改进蚁群算法提出了基于路径平滑因子。首先,环境地图构建是基于网格的方法,并且每个网格使蚁群的初始网格到目标网格路径搜索。然后,改进的启发式信息指的是起点和终点的方向信息,结合转向角。通过改进的启发式信息,搜索的方向是增加,机器人的转向角降低。最后,提高了信息素更新规则,被认为是二维的平滑路径,机器人的转动时间减少,引入了一种新的路径评价函数来提高有效路径的信息素分化。同时,极大极小蚂蚁系统(mma)算法被用来限制信息素浓度,以避免陷入局部最优路径。仿真结果表明,改进的蚁群算法可以搜索最优路径长度和计划顺畅和安全的道路快速收敛速度,有效地解决了全球移动机器人的路径规划问题。

1。介绍

移动机器人的快速发展,路径规划已成为基础和核心的移动机器人的研究领域。移动机器人的路径规划技术是找到一个最优或次优的无碰撞路径从开始到结束在复杂环境中按照一定的评价标准,如最短的路线,至少转动,最少的能耗等。1]。传统的算法来解决路径规划问题主要包括人工势场算法(2[],迪杰斯特拉算法3),和一个算法(4]。近年来,一些研究人员采用仿生智能优化算法来解决路径规划的问题。这些仿生智能优化算法主要包括蚁群算法(5)、遗传算法(6),粒子群优化算法(7),免疫算法(8),模拟退火算法(9),和之间的组合优化算法算法(10- - - - - -12]。

在上面的路径规划方法,蚁群算法具有较强的鲁棒性和搜索能力,由意大利著名学者首次提出民宿(1992年13]。作为一种启发式算法,它模拟了蚁群的觅食过程和获得解决方案的路径共同计划的蚂蚁。它有积极的反馈的特点,并行计算,简单的融合。然而,仍然有问题,如收敛速度慢,容易陷入局部最优的机器人路径规划。许多学者改进传统的蚁群算法。曹等人提出的建立一个初始信息素模型,以避免盲目搜索和改善传统蚁群算法的收敛速度14]。白等人设计了蚁群算法与负面的反馈机制来避免陷入局部最优解(15]。张等人提出了构建一个新的启发式函数信息素挥发因子的适应变化,确保快速收敛的蚂蚁即使全面搜索路径(16]。马和梅集成的蚁群算法的搜索策略和跳搜索算法,介绍了降低势场合力系数,介绍了简化跳搜索算法来更新初始信息素,并提出了基于势场跳的蚁群算法(17]。

最上面的改进蚁群算法用于优化路径长度,提高寻路的效率。一些学者认为太大等问题转向角和太多的把整个路径的时候,导致机器人运行时间和能源消耗的增加,当寻找下一个移动节点。针对这一点,本文提出了一种改进的蚁群算法基于二维路径平滑因子对移动机器人路径规划。

2。环境建模和基本的蚁群算法

2.1。环境建模

常用的机器人环境建模方法包括网格方法,可视空间方法,自由空间法,几何信息方法和拓扑映射方法(18]。摘要网格方法选择模型的二维运动空间移动机器人,如图1。

为了确保移动机器人不会撞上障碍物的边缘在运动的顺利进行,确保每一转,障碍是正确的大小扩大,然后保留一定的安全距离。安全距离是移动机器人的半径,和机器人可以简化为一个粒子处理(19]。

网格数是用来表示机器人的具体位置和障碍,白色网格的自由网格,代表通行的区域,而黑色网格障碍区,这对移动机器人是不可逾越的。机器人的运动可以被视为从当前网格的中心转移到下一个网格的中心。八个方向相邻的可转让的网格是网格当前网格。八个相邻网格转向标签如图2。

在网格环境中,假设网格和网格G是机器人运动的起点和终点,分别。路径规划要解决的问题是搜索的一系列命令自由网格节点从S g .为了简化建设的路径搜索算法,下列规定了网格环境,如图1。(1)以网格地图的左上角为起点,网格编号的顺序从上到下,从左到右。此时,每个网格都有一个相应的坐标称为网格坐标,和网格位置的行和列被标记 。然后,障碍矩阵表示如下: (2)以网格地图的左下角为坐标原点,x设在正方向被定义为从左到右,和y设在正方向被定义为从下到上。此时,相应的坐标网格的称为原点的坐标网格。假设网格地图上的行数 ,原点坐标之间的映射关系 和网格坐标 表示如下:

2.2。基本蚁群算法

蚁群算法是模拟蚂蚁群体的过程从起点到找到目标点来获取食物。蚂蚁在寻找食物的过程中,会释放一定量的路径信息素,和蚁群使用这些信息素相互通信。当越来越多的蚂蚁通过一定的路径,这个路径的信息素浓度高,和其他蚂蚁将有更大的概率选择这条路,扮演了一个积极的反馈作用,但它也很容易导致局部最优或死锁的发生20.]。

如果有多个既无网格,蚂蚁的概率选择下一个网格从当前网格是取决于它们之间的距离和信息素浓度(21,22]。状态转移概率 在哪里是代表了从电网信息素浓度我网格j在时间t;从电网启发式信息吗我网格j蚂蚁从电网,表示期望的程度我网格j;它通常是两个网格之间的距离的倒数, 。 信息素因子和吗是启发式因子,分别表示的浓度信息素和启发式信息的相对重要性。代表了网格设置可以选择的蚂蚁k在下一步t时间。

当所有蚂蚁完成一次遍历,路径上的信息素浓度将蒸发最初的信息素进行更新和增加蚂蚁的信息素积累。信息素更新公式 在哪里信息素波动系数, 。 代表的信息素增量网格我网格j在这个迭代。代表了蚂蚁的信息素释放量k从网格我网格j在这个迭代。问表示信息素强度,它是一个常数。代表了蚂蚁的路径长度k在这个迭代。

3所示。路径规划的改进蚁群算法

在传统的蚁群算法中,每个网格的初始信息素值是相同的,和启发式值没有明显的区别,所以搜索时间通常是长,算法收敛速度慢,很难找到全局最优解(23]。同时,网格地图的基本蚁群算法的路径规划可能更多,可怜的路径的平滑,消耗了大量的能量的机器人。为了提高原蚁群算法的性能,克服其缺陷,本文做了以下改进。

3.1。改进启发式信息

在传统的蚁群算法,启发式信息相邻网格之间的距离的倒数,所以蚂蚁在相邻网格的启发式重量差异不明显,这使得启发式函数不发挥明显作用蚂蚁转移的决定,使算法的搜索效率相对较低。此外,当机器人通过一组障碍,如果只有最短路径被认为是主要的因素,它会导致机器人的转向角太大,容易偏离标点符号,这将大大增加的时间和能源消耗。

因此,本文将转向角添加到蚁群算法的启发式信息,结合方向信息的起始点和目标点的改进启发式信息,以便移动机器人可以移动到目标点和选择一个路径与转向角尽可能小。通过改进启发式函数,蚁群搜索的目的是增加了,落入局部最优解的概率降低。改进的启发式信息如下: 在哪里代表了蚂蚁的方向信息米从网格我网格j在时间t和导游蚂蚁移动到相邻的网格在终点的方向, 。 表示当前网格的距离我到下一个网格j,表示当前网格的距离j到最后网格 。 代表了蚂蚁的转角米从网格我网格j在时间t、指导蚂蚁选择路径与小角, 。 代表了蚂蚁的把标签从之前的网格p当前的网格我,表示蚂蚁的把标签从当前网格我到下一个网格j。当 , ,启发式信息是最大的,这表明机器人不转身移动终端与最优路径。

3.2。提高信息素更新规则

3.2.1之上。改进信息素增量

当传统的蚁群算法是用来解决机器人路径规划问题,通常需要的路径长度作为唯一的参考评估质量的路径。然而,在机器人行走的实际场景,为了提高机器人的灵活性和安全行走,不仅路径的长度,而且机器人的转动时间应考虑在整个路径。此外,当障碍一定区域人口分布,机器人的频繁将在短时间内应该避免。因此,考虑机器人的二维路径的平滑度,引入了一种新的路径评价函数来提高信息分化的有效路径,以提高搜索路径的平滑度,提高机器人的安全,减少能源消耗。 在哪里的评价函数是由蚂蚁路径旅行吗k,信息素分配根据评价函数。评价函数越小,更好的路径,这个路径上信息素释放越多,吸引更多蚂蚁寻找这条路。是蚂蚁的路径长度k。将蚂蚁的时候吗k的道路上,代表的平滑路径;越小 ,更好的平滑路径。在哪里x路径长度调整系数和吗y次的调整系数,适当的价值根据所需的路径属性。

3.2.2。信息素的限制

若干次迭代后,在一条路径上信息素的价值可能远大于或远小于其他路径,使搜索无法继续和导致过早收敛。为了防止这种极端情况,信息素的值范围是有限的来通过引用mma算法(24,25]。

4所示。改进的蚁群算法在路径规划中的应用

改进的蚁群算法应用于路径规划。具体步骤如下:步骤1。环境建模:机器人的运动空间环境是由网格建模方法。起点、终点和障碍位置的机器人是由网格坐标,和所有的蚂蚁都放置在机器人的起始点。步骤2。初始化参数。起始位置,目标位置G,蚂蚁的数量米迭代的最大数量 ,当前的迭代次数 ,信息素的重要因素 ,启发式信息重要性的因素 ,信息素波动系数 ,信息素的强度问,路径长度调整系数x,把时间调整系数y。步骤3。计算启发式信息。根据当前位置的蚂蚁,启发式信息计算根据方程(6),结合回转角度和方向的信息。步骤4。选择路径。蚂蚁从当前的概率计算网格non-tabu网格根据方程(3),选择下一个网格通过轮盘赌方法和禁忌表更新。步骤5。确定所有的蚂蚁已经达到目标网格。如果是这样,记录每只蚂蚁的路径,路径的长度,和时间。否则,返回步骤3。步骤6。计算信息素增量。评价函数的路径是根据公式计算(9),根据信息素增量计算公式(8)。步骤7。更新信息素。根据方程(更新信息素5),由方程(信息素的数量是有限的10)。步骤8。记录所有蚂蚁的路径的信息。比较每个迭代的最优路径寻找当前全局最优路径。步骤9。确定迭代的算法达到最大数量;最优路径算法终止和输出;否则,重复步骤3到8。

改进的蚁群算法路径规划的流程图如图3。

5。实验结果和分析

为了验证改进的蚁群算法的有效性(IACA),本文在MATLAB R2016A进行仿真实验。计算机操作系统是Windows10, AMD处理器,主频率为2.0 GHz, 8 g内存。移动机器人的移动环境20×20 30×30日分别和50×50网格地图。同时,为了验证该算法的优越性,该算法获得的结果与通过蚂蚁系统算法()(13)算法和蚁群系统(ACS) (26- - - - - -28在相同的环境中。此外,为了验证改进的蚁群算法的稳定性,10倍的三个算法模拟和实验结果如表所示1。相关参数设置如下:α= 1,β= 6,ρ= 0.1,问= 10,x= 1,y= 1,蚂蚁的数量米= 50,迭代的最大数量 。的起点是在左上角和右下角的终点G。

5.1。20×20网格环境

首先,在一个简单的20×20的网格环境中,三种算法的仿真结果如图路径规划研究4。

在实验中,发现在20×20网格环境中,所有三个算法可以搜索最短可行路径在运行过程中,使移动机器人可以移动安全从起点到终点。然而,路径规划的算法和ACS算法有一个很大的圈数和路径的平滑度差,导致多个当机器人移动很短的距离,和频繁的在短时间内并不有利于机器人的安全。数量的改进算法具有明显的优势,规划路径平滑,收敛速度快。

5.2。30×30网格环境

为了进一步验证本文改进算法的可靠性,网格地图是扩大到30×30多障碍,并再次进行了仿真。三种算法的仿真结果如图路径规划研究5。

从图可以看出5当网格地图的规模扩张和障碍的增加,算法和ACS算法不能很好的适应全局路径规划这种相对复杂的环境和最优路径长度计划是50.8和51.2,分别。然而,本文算法仍然可以表现良好,和最优路径发现49.6,有效地缩短了路径长度与前两种算法。图5 (c)显示了三种算法的收敛曲线(30×30);可以看出,本文算法在收敛速度和最短路径长度时,环境是复杂的。图5 (b)显示了变倍曲线的三个算法(30×30);可以看出,的把时间的最优路径算法本文明显低于作为ACS算法和算法。

5.3。50×50网格环境

为了进一步验证改进算法的适应性的大规模网格地图(50×50),这种规模的三个算法模拟地图。路径规划是如图6。

从图可以看出6 (c)在大规模网格地图,所有三个算法时间消耗的增加,算法和ACS算法容易陷入局部最优。从图可以看出6 (b)网格地图的许多障碍,算法和ACS算法赚很多当搜索最优路径。从图可以看出6(一)改进的算法具有明显的优势,这不仅降低了匝数和增加了平滑的路径,但也有更快的收敛速度比算法和ACS算法,可以找到最优路径。

从表中的数据可以看出1计划的路径长度的改进蚁群算法较短的大规模的环境,更多的障碍和相对复杂的(50×50)。与作为算法相比,收敛于最优解所需的迭代次数减少了约61。此外,《纽约时报》将在最优路径是减少来自37个算法和53 ACS算法4。路径的平滑度显著提高,有效地避免了大规模机器人的行为。

总之,当环境变得相对复杂,传统算法的搜索路径变得更加曲折,优化能力并不理想,很容易陷入局部最优解。有一些局限性在复杂环境中的路径规划。改进的算法可以快速、有效地找到最优路径,即使在复杂的环境中,和计划路径少和更好的路径平滑。算法的有效性和优越性得到进一步证实。

6。结论

路径规划是机器人的关键技术在复杂环境中移动。作为仿生算法,蚁群算法可以有效地实现机器人的路径规划。针对收敛速度慢的问题,搜索效率低,穷人和路径平滑传统蚁群算法在路径规划,本文改进了蚁群算法的改进启发式信息,引入一种新的路径评价函数,考虑到二维的平滑路径,和更新的有效路径信息素分化。路径规划的仿真结果在三个不同的网格环境中表明,该改进算法具有更好的路径规划,收敛速度更快,更少的,平滑的路径,减少了移动机器人的能量损失,使其安全、迅速移动到目标点。它有效地证明了算法的有效性和适应性在复杂的环境。

微流体技术,集成了基本操作单位如样品制备、反应、分离、检测过程中生物、化学、医学分析成微米尺寸芯片自动完成整个过程的分析(29日,30.]。数字微流控生物芯片(DMFB)以离散microdroplets为单元,实现液滴的各种基本操作或处理,如发电、运输、合并、混合、分离、储存、和检测,通过液滴驱动模式。液滴路径规划是一种先进的合成DMFB的核心步骤。它的目标是计划一群液滴的移动路径和需要滴正确执行生化反应过程的检测和分析。每个液滴被解释为一个点移动机器人在一个离散二维配置空间。在这种假设下,路径规划的水滴变成了多个移动机器人运动规划问题(31日- - - - - -34]。因此,在未来的研究中,我们将进一步尝试使用蚁群算法来解决滴DMFB路径规划和调度的问题。

数据可用性

使用的数据来支持本研究的发现可以从相应的作者。

的利益冲突

作者宣称没有利益冲突有关的出版。

确认

这项工作是支持的安徽大学优秀青年人才支持计划项目(没有。gxyq2019072)大学和安徽省级质量工程项目(没有。2020 jyxm2151)。

引用

1. d·h·张,x m . s . Liu和h .锅,“动态多用途自适应协作蚁群优化机器人路径规划,“IEEE访问,8卷,第129974 - 129958页,2020年。视图:出版商的网站|谷歌学术搜索
2. f·l·李”,一种优化基于进化的人工势场路径规划方法”应用力学和材料卷,380 - 384。384年,第1417 - 1414页,2013年。视图:出版商的网站|谷歌学术搜索
3. e·w·迪杰斯特拉”,注意在连接图,两个问题”Numerische Mathematik,1卷,不。1,第271 - 269页,1959。视图:出版商的网站|谷歌学术搜索
4. 黄c . j .范h·李,和刘x, y . Liu“光滑的基于动态反馈的路径规划方法^∗蚁群算法”,中国农业机械学会的事务,48卷,不。4,34-40,2017页。视图:出版商的网站|谷歌学术搜索
5. l .曰和h·陈,“无人驾驶车辆使用新型蚁群算法路径规划,“EURASIP无线通讯和网络》杂志上,卷2019,不。1、1 - 9,2019页。视图:出版商的网站|谷歌学术搜索
6. c . Lamini s Benhlima, a . Elbekri“基于遗传算法的方法自主移动机器人路径规划,“Procedia计算机科学卷,127年,第189 - 180页,2018年。视图:出版商的网站|谷歌学术搜索
7. y . k .,“使用简化的群优化智能移动机器人路径规划,“Procedia计算机科学卷,120年,第90 - 83页,2017年。视图:出版商的网站|谷歌学术搜索
8. t .锣和m .王”,一种改进的免疫算法求解路径优化问题在深免疫基因网络的学习,“计算机和通讯》杂志上,7卷,不。12日,第174 - 166页,2019年。视图:出版商的网站|谷歌学术搜索
9. 郭j·l . Wang,问:王,j .菅直人“地面机器人路径规划基于模拟退火遗传算法,”《2018年国际会议上Cyber-Enabled分布式计算和知识发现(CyberC)郑州,页417 - 4177年,中国,2018年10月。视图:出版商的网站|谷歌学术搜索
10. j .问:廖”PAGV路径规划研究基于人工免疫蚁群算法,融合”智能和模糊系统杂志》上,35卷,不。16日,1 - 6,2018页。视图:出版商的网站|谷歌学术搜索
11. j·l . Liu姚明,d .他et al .,“全球动态路径规划融合算法结合跳^∗算法和动态窗口的方法,”IEEE访问9卷,第19638 - 19632页,2021年。视图:出版商的网站|谷歌学术搜索
12. 答:女子和s . Varma Nadimpalli“新融合算法提供了一种替代方法的机器人路径规划方法,”国际期刊的信息工程和电子商务,12卷,不。3、1 - 7,2020页。视图:出版商的网站|谷歌学术搜索
13. 诉Maniezzo m .民宿,a . Colorni”由一群蚂蚁系统:优化代理、合作”IEEE系统,人,控制论,B部分(控制论),26卷,不。1,29-41,1996页。视图:出版商的网站|谷歌学术搜索
14. X.-L。曹,z。Wang j·冯·m·查和中州。王,“全球机器人基于改进蚁群算法的路径规划,“计算机工程与科学,42卷,不。3、187 - 193年,2020页。视图:谷歌学术搜索
15. J.-L。巴姨,h。陈,Y.-B。胡,硕士。他,X.-D。梁,d .公园,“蚁群算法基础上负面的反馈及其应用在机器人路径规划,“计算机集成制造系统,25卷,不。7、1 - 9,2019页。视图:谷歌学术搜索
16. j .赵Y.-F。唐,G.-P。江,F.-Y。徐,j .叮”移动机器人路径规划的基础上改进的蚁群算法,”南京邮电大学学报(自然科学版),39卷,不。6,73 - 78年,2019页。视图:谷歌学术搜索
17. 马x h·梅,“移动机器人全局路径规划基于改进蚁群系统算法与潜在领域,“机械工程学报卷,57号1,19-27,2021页。视图:出版商的网站|谷歌学术搜索
18. 田,y, y康,j .夏“多机器人路径规划算法在无线传感器网络中基于跳机制和安全避障的差距,“未来一代计算机系统,卷118,不。6,37-47,2020页。视图:出版商的网站|谷歌学术搜索
19. 郭x m .霁z,赵,d,和w·张,“全局路径规划和多目标路径控制的无人地面车辆基于改进粒子群优化(PSO)算法,”海洋工程文章ID 107693卷,216年,2020年。视图:出版商的网站|谷歌学术搜索
20. 方m z . Wang j . Li, y,”一个multimetric蚁群优化算法在车辆动态路径规划网络,”国际期刊的分布式传感器网络文章ID 271067卷,2015年,10页,2015。视图:出版商的网站|谷歌学术搜索
21. w·高,问:唐,b, y,和j .姚明,”一个增强的移动机器人路径规划,启发式蚁群优化”软计算,24卷,不。2、6139 - 6150年,2020页。视图:出版商的网站|谷歌学术搜索
22. 问:罗,h . Wang y郑,j .他“研究移动机器人的路径规划改进蚁群算法的基础上,“神经计算和应用,32卷,不。6,1555 - 1566年,2020页。视图:出版商的网站|谷歌学术搜索
23. j .宁问:张、张c和b,”一个best-path-updating information-guided蚁群优化算法,”信息科学卷,433 - 434。434年,第162 - 142页,2018年。视图:出版商的网站|谷歌学术搜索
24. t . Stutzle和h . hoo不等式蚂蚁系统和本地搜索货郎担问题,”学报1997年IEEE国际会议97年进化计算(欧洲的)印第安纳波利斯,页309 - 314年,在美国,1997年4月。视图:出版商的网站|谷歌学术搜索
25. l . c . Lu和t . w .曰,“面向ant-team min-max MTSP ACO,”应用软计算卷,76年,第444 - 436页,2018年。视图:谷歌学术搜索
26. m .民宿和l . m . Gambardella蚁群系统:合作学习方法货郎担问题,“IEEE进化计算,1卷,不。1,53 - 66年,1997页。视图:出版商的网站|谷歌学术搜索
27. h . g . z . Tan欢,a·斯洛曼“蚁群系统算法实时移动机器人全局最优路径规划,“《自动化学报》,33卷,不。3、279 - 285年,2007页。视图:出版商的网站|谷歌学术搜索
28. S.-Z。周,Z.-H。詹,Z.-G。陈,美国邝,j .张“多目标蚁群系统算法航空公司机组人员名单问题公平和满意,“IEEE智能交通系统,2020年1 - 15页。视图:出版商的网站|谷歌学术搜索
29. f . Sapuppo奔驰精灵美国总裁f . Schembri l .命运和m . Bucolo“微流控电路和系统,IEEE电路和系统杂志,9卷,不。3,6-19,2009页。视图:出版商的网站|谷歌学术搜索
30. 奔驰精灵美国总裁f . Schembri f . Sapuppo, m . Bucolo非线性动力学实验分类”的微流体泡沫流,”非线性动力学,卷67,不。4、2807 - 2819年,2012页。视图:出版商的网站|谷歌学术搜索
31. k . f . Bohringer”droplet-based微流控系统的建模和控制并行任务,”IEEE计算机辅助设计的集成电路和系统,25卷,不。2、334 - 344年,2006页。视图:出版商的网站|谷歌学术搜索
32. i, p . Dasgupta h . Rahaman, t . Samanta”基于蚁群优化的液滴路由技术在数字微流控生物芯片,”《2011年国际研讨会上电子系统设计高知县,页223 - 229年,印度,2011年12月。视图:出版商的网站|谷歌学术搜索
33. w·郑h . Yu l·冯·傅姜和h,“单液滴联机测试路径优化数字微流控生物芯片基于改进蚁群算法,”《2017年IEEE国际仪器和测量技术会议(I2MTC)意大利的都灵,页1 - 6,,2017年5月。视图:出版商的网站|谷歌学术搜索
34. 穆克吉,即锅,t . Samanta”粒子群优化方法故障定位和去除残留在数字微流控生物芯片,”应用软计算,卷85,不。1,文章ID 105839, 2019。视图:谷歌学术搜索

版权

版权©2021王雯et al。这是一个开放分布式下文章知识共享归属许可,它允许无限制的使用、分配和复制在任何媒介,提供最初的工作是正确引用。