基于遗传算法的机器人路径规划融合连续贝塞尔曲线的优化

文摘

在这项研究中,提出了一种平滑的路径规划的新方法应用于基于贝塞尔曲线和冗余节点的解决问题和峰值拐点在路径规划过程中传统的算法。首先,遗传操作是用来获得贝塞尔曲线的控制点。第二,选择较短路径的优化准则,贝塞尔曲线的长度是由控制点。最后,一个安全的距离和自适应惩罚因子引入适应度函数以确保机器人的行走过程的安全。许多实验中实现两个不同的环境,与现有的方法相比。证明了该方法是更有效的生成一个短,平滑,与传统方法相比更安全的道路。

1。介绍

路径规划是移动机器人领域的一个重要研究方向,是研究的一个主要困难等机器人(1]。路径规划问题的目标是找到最安全、最短路径自主没有碰撞从起始点到目标点在给定环境下与障碍(2,3]。路径规划在物流配送等领域得到了广泛的应用,智能交通,和武器导航4- - - - - -6]。因此,如何找到一种快速、有效的路径与高已成为一个研究问题的理论意义和实用价值。

近年来,遗传算法(GA)已广泛应用于移动机器人路径规划问题,因为其伟大的全局优化能力和隐式并行计算特点(7,8]。遗传算法搜索最优解的模拟自然进化基于基因遗传和变异的理论模型在达尔文的生物进化9,10]。最近,一些有意义的结果为GA已报告。例如,一个广义交叉算子分割中引入了遗传算法来提高算法的局部优化能力和执行效率(11]。Albayrak和Allahverdi贪婪搜索算法引入遗传算法的变异操作和设计一个新的贪婪日光浴变异算子来解决旅行商问题(TSP) [12,13]。此外,提出了一种改进的交叉算子(14),可避免过早收敛在静态环境中获得最优路径。机器人路径规划方法,提出了基于改进的遗传算法(15),移动机器人路径规划算法的适应性提高通过引入可变长度染色体。并行遗传算法提出了精英保持种群多样性,避免过早收敛,并保持与传统遗传算法并行性(16]。然而,值得注意的是,在规划过程中仍然存在许多问题。例如,峰值和拐点在获得路径将使机器人无法沿着路径移动的过程中,计划或将之间频繁切换不同的模式,如停止旋转,并重启,导致过度的时间和能量的损失,等等。6,17]。

最近,贝塞尔曲线应用于光滑的路径规划(见[6,18- - - - - -27])。举个例子,提出了一种遗传算法找到分段贝塞尔曲线的控制点,从而解决移动机器人路径规划的问题(16]。路径规划方法,提出了基于贝塞尔曲线来解决机器人足球的旅行路径(21]。提出了一种无碰撞曲率有界的平滑路径规划技术将分段线性路径中的节点分为控制点(22]。此外,Bezier-curve-based(公司)的改进遗传算法和动态领域的用于路径规划23]。一种新的混沌粒子群优化算法(复)提出了优化贝塞尔曲线的控制点,在起点和终点之间的总距离被使用选定的控制点(最小化24]。此外,Bezier-curve-based提出了路径规划和应用在自动车辆25]。此外,协作multi-incomplete机器人的避碰方法,提出了基于Bernstein-Bezier曲线(26]。最后,一个有效的和分析连续曲率路径平滑算法(27),它被发现适合路径点的序列生成的避障路径规划。

尽管如此,仍有许多困难在规划平稳安全的路径移动机器人用上面提到的方法。因此,本文旨在提出一种新的平滑路径规划方法处理冗余节点和拐点在路径规划过程中达到顶峰。首先,遗传算子用于获得贝塞尔曲线的控制点,确保顺利连续性的路径。第二,贝塞尔曲线的长度选择的优化准则,以确保计划的最短长度路径。第三,通过增加安全距离和适应度函数的自适应惩罚因子,机器人行走过程的安全保证。最后,实验结果说明该方法可以产生更短,更流畅,更安全有效的路径比现有的方法(例如,28- - - - - -31日])。总之,本文的贡献如下:(1)与方法介绍(29日,30.],我们的遗传操作是用来获取控制点的贝塞尔曲线,它可以保证路径曲率的连续性;(2)选择较短的平滑路径通过使用一个优化准则,可确保生成的路径最优无需进一步平滑;和(3)的方法进行对比(6,22),机器人的行走安全进步是进一步提高通过引入适应度函数的自适应调整。

本文的其余部分组织如下。介绍了贝塞尔曲线部分2。部分3介绍了关键点的基于贝塞尔曲线的平滑的路径规划方法。实验结果,讨论了该方法的可行性和有效性4。最后,得出结论并提出了未来工作的方向5。

2。贝塞尔曲线

贝塞尔曲线是连续光滑的曲线是由几个功能点,控制一个起点和一个终点。贝塞尔曲线的高阶导数连续性保证曲线的平滑变化从起点到终点(17,32- - - - - -34]。因此,当使用贝塞尔曲线获得机器人的路径旅行,计划中的路径是连续和光滑。

给定一个曲线米控制点, ,相应的贝塞尔曲线确定的(35]: 在哪里t是位置参数(例如,什么时候 , 四分之一的路径点吗P₀来 ), 代表贝塞尔曲线的控制点,是伯恩斯坦多项式,它的基本功能是贝塞尔曲线表达式。

根据方程(1)和(2),贝塞尔曲线的衍生品也可以由控制点。贝塞尔曲线的一阶导数表示如下: 和贝塞尔曲线的高阶导数曲线可以通过方程计算(3)。贝塞尔曲线的二阶导数可以表示为(35]:

因此,在二维平面上,贝塞尔曲线的曲率对t可以表示成 在哪里代表和曲率半径 , , ,和第一和第二的组件是贝塞尔曲线的衍生品吗为和坐标。

一般来说,传统的路径规划算法会产生很多尖锐拐点和冗余节点,如图1(一),在那里年代是起点,T是终点,是路径拐点。假设控制点,可以获得相应的贝塞尔曲线方程(1)和(2)(见图1 (b))。从图1 (c)可以看出,通过贝塞尔曲线是平滑的路径和短。

3所示。基于贝塞尔曲线的平滑路径规划

在这项研究中,遗传算子和贝塞尔曲线相结合找到一个平稳和安全的移动机器人的路径。首先,遗传算子应用于寻找贝塞尔曲线的控制点;然后,安全距离和自适应调整因素被添加到适应度函数来评估计划的贝塞尔曲线路径的安全。最后,确定最短路径根据所有计划的贝塞尔曲线路径的长度。提议的方法的要点如下所述。

3.1。问题描述

路径规划问题通常被称为寻找从起始点到目标点的无碰撞路径按照一定的评价指标。具体地说,整个计划路径从起点到终点必须最短的和无碰撞。这个问题在数学上可以定义如下: 在哪里t是位置参数,代表贝塞尔曲线路径的长度,代表的路径从开始点年代到终点 ,和是没有冲突的道路。

方程(1)和(2)表明,贝塞尔曲线是由控制点。因此,这个问题等于找到贝塞尔曲线的控制点约束(9)。

在这里,是障碍,代表了贝塞尔曲线的控制点。它必须持有控制点不能在障碍寻找贝塞尔曲线的控制点。

3.2。染色体编码

染色体遗传操作(即前需要编码。,the chromosome is the control point sequence of the Bezier curve). Common encoding methods include binary encoding and decimal encoding. Binary coding uses strings of 0 or 1 to form a chromosome, which has the advantages of simple operation and easy decoding. Therefore, the chromosome of this paper is encoded in binary.

所有控制点都定义在工作区中网格的中心。从网格数字坐标转换值表示为 num表明网格数量,米表示地图的大小,国防部代表其余的操作,代表的是四舍五入了,和是X和Y坐标网格的中心组成部分,分别。

3.3。适应度函数的自适应调整

虽然可以保证当路径长度最短路径被认为是主要的标准,可能会存在一些问题造成的碰撞小机器人和障碍物之间的距离。因此,本章提出了一种safety-assurance-based适应度函数增加安全距离通过引入一种自适应惩罚因子,这是表示如下: 在哪里贝塞尔曲线路径的长度是通过控制点顺序约束(下6)- (9)。安全距离是障碍。当最小距离之间的路径和障碍小于安全距离,将处罚。方程(14)表明,惩罚的强度有关 。路径和障碍之间的距离越近,惩罚强度越高。这使得动态调整的适应度函数来提高质量的规划路径。根据方程(12),我们就可以观察到较短的规划路径和路径的健身价值越高,路径将被选中的概率越大。

3.4。遗传操作

在这项研究中,引入遗传操作贝塞尔曲线找到控制点。有三个遗传算子:选择算子、交叉算子和变异算子。

选择算子实现路径的选择运用不同的选择策略根据健身价值。选择方法是轮盘赌法、锦标赛法等。本文采用轮盘赌选择路径的方法。假设的路径长度th贝塞尔曲线 ,贝塞尔曲线的健身价值(见方程(12))。所选路径的概率 在哪里n贝塞尔曲线的数量。

交叉操作的特点,结合两个父染色体产生两个后代。根据交叉概率,两条染色体的基因交换随机生成的交叉点。本文采用单点交叉,如图2。

介绍了变异算子增加解的多样性。它改变了基因变异的任何扣除的一部分开始点和结束点的染色体,它避免了造成的过早收敛算法陷入局部最优解的过程。在这篇文章中,变异算子的概率设置为0.1,可以保证算法的稳定性的解决方案的过程。

4所示。实验和分析

在本节中,以验证该算法的可行性和有效性,验证了移动机器人的路径规划在两个不同的网格环境中,如图3。在环境1中,机器人的起始坐标是(0,0),终点坐标是(20、20)障碍覆盖率是15.00%,和参数设置如下:人口规模作为 ,最大的代被认为是 ,交叉概率为 ,和变异概率是作为 , , ,和 。在环境2中,机器人的起始坐标是(0,0),终点坐标是(20、20)障碍覆盖率是20.75%,和参数设置如下:人口规模作为 ,最大的代被认为是 ,交叉概率为 ,和变异概率是作为 , , ,和 。

4.1。贝塞尔曲线平滑算法的可行性实验

在实验中,传统的蚁群优化(ACO),传统的遗传算法(GA),蚁群优化与遗传算法相结合(ACO-GA),人工鱼群算法(ASFA-GA),贝塞尔曲线平滑算法(BCA)和贝塞尔曲线平滑算法增加了安全距离(BCA-Q)采用环境1中进行实验。图4显示了路径规划的结果用不同的算法。为了消除随机和其他应急因素对算法的影响,上述算法执行独立的30倍,并给出统计结果表1,“-”意味着不能获得统计结果。

结合图4和表1可以找到,下面的路径长度。(1)算法、GA和ASFA-GA可以计划一个无碰撞路径(如图4(一),4 (b),4 (d))与路径长度为34.6248,32.8663,和31.2144,分别。与BCA(29.9416)相比,配电网的规划路径,GA,和ASFA-GA更长,这是感染造成的大量冗余节点和冗余点的路径。(2)遗传算法引入算法,即。,为ACO-GA,the path length is 31.7964; this is an improved performance compared with just ACO and just the GA. However, there are still peak inflection points (e.g., Figure4 (c))。(3)从数据可以看出4 (e)和4 (f)路径的质量获得由BCA BCA-Q已经显著提高;在这里,蓝色的圆圈的控制点是贝塞尔曲线,红线是最优平滑路径。路径的长度分别是29.9416和31.1843。结合表1,计划路径长度的最小值和平均值获得通过使用BCA和BCA-Q比其他方法。这样做的原因是,改进算法减少了冗余的拐点和冗余节点路径规划;因此,道路顺畅,短。(4)尽管路径长度计划图4 (f)长于如图4 (e)机器人的移动安全保证,和路径规划性能优于其他算法。

运行时间而言,表1表明ASFA-GA是最好的模拟算法所需的时间。此外,ACO-GA增加了仿真时间由于遗传算法的引入。这是由于遗传算法引入了交叉和变异操作过程中路径规划。最后,表1表明,尽管BCA的仿真时间和BCA-Q时间比其他算法,最小路径长度较短。因此,与传统的算法相比,该算法有更好的性能在路径长度和平滑度较低的环境中的实时要求。

4.2。贝塞尔曲线平滑算法的有效性实验

为了验证该算法的性能,一个复杂的网格环境本文建立了。所示的算法部分4.1应用于环境2。图5显示了路径规划的结果用不同的算法。为了消除随机和其他应急因素对算法的影响,上述算法独立30倍,执行和统计结果记录在表2,“-”意味着不能获得统计结果。

基于图的分析5和表2,它可以观察到障碍的报道环境2是与环境1相比增加了5.75%。然而,增加覆盖范围使它更难搜索全局最优的解决方案。相比之下,表1路径规划的仿真时间和距离表2是增加了。ASFA-GA的路径长度是32.3821。虽然不是最长的路径的算法,有明显的拐点(见图5 (d))。(2)从数据5(一个)- - - - - -5 (d)和表2,你会发现算法和ACO-GA也可以找到一条无碰撞路径在复杂的环境中,但是他们的平均路径长度长的ASFA-GA相比,33.6631。从图我们也可以观察到5 (e)通过BCA的路径平滑和短而获得的其他算法。避免冗余节点,路径长度是30.3458。从表2,我们可以看到,BCA略有不足与其他算法相比,仿真时间消费。然而,它仍然是在复杂的环境中有效的路径长度和平滑度。此外,尽管在路径拐点消失计划由BCA,路径是非常接近的障碍。适应度函数,通过增加安全距离BCA-Q提高移动机器人的安全,可以验证图5 (f)。然而,这种优势是通过牺牲路径长度。BCA-Q的计划路径长度为31.8503,大于BCA的4.96%。值得注意的是BCA-Q还是短的路径长度比算法和遗传算法。此外,它的平滑度和路径安全性大大提高。

5。结论

在本文中,一种新的平滑路径规划方法相结合提出了遗传算子和贝塞尔曲线为移动机器人。首先,贝塞尔曲线的控制点是由遗传操作,和贝塞尔曲线的平滑特性被用来使规划路径平滑和更一致,减少了能量损失在机器人运动。第二,安全距离是添加到适应度函数和可以动态调整路径和障碍之间的距离,确保安全、高效的机器人。最后,仿真结果表明,该算法是有效的在寻找一个最优路径;这个最优路径短,流畅,比传统算法获得的安全。然而,仿真时间增加。这是因为改进算法更加关注质量的解决方案的过程中路径规划。仍然存在各种各样的有意义的课题需要解决,例如如何选择最合适的数量的连续贝塞尔曲线的控制点,如何将该算法应用到更复杂的实际环境(如房间或其他特殊环境),以及如何提高计算效率和更多的控制点。

数据可用性

使用的数据来支持本研究的结果包括在本文中。本文列出了所有必需的模型和参数。

的利益冲突

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

确认

这部分工作是支持中国国家重点研发项目授予2016年yfe0104600和河南省的科技项目拨款172102410071下的中国。

引用

1. m·a·p·加西亚,o .打算o·卡斯蒂略,r·赛普维达和p ?梅林”的自主移动机器人导航路径规划蚁群优化和模糊成本函数评价,“应用软计算,9卷,不。3、1102 - 1110年,2009页。视图:出版商的网站|谷歌学术搜索
2. g·李和w·周”,为移动机器人路径规划使用自适应学习粒子群优化,“中国科学信息科学,卷61,不。5、文章ID 052204, 2018。视图:出版商的网站|谷歌学术搜索
3. r·k·Mandava s Bondada, p . r . Vundavilli”移动机器人的路径规划优化利用势场方法和PSO算法,”先进的智能系统和计算,8卷,不。7,139 - 150年,2019页。视图:出版商的网站|谷歌学术搜索
4. r·李•吴(george w . bush)和h·乔,”机器人从功能的合规机制。”装配自动化,35卷,不。3、281 - 286年,2015页。视图:出版商的网站|谷歌学术搜索
5. d . c .罗宾逊、d·a·桑德斯和e . Mazharsolook”环境智能优化制造业和能源效率。”装配自动化,35卷,不。3、234 - 248年,2015页。视图:出版商的网站|谷歌学术搜索
6. 王歌,z l .盛,“一个新的遗传算法平滑的移动机器人路径规划方法,”装配自动化,36卷,不。2、138 - 145年,2016页。视图:出版商的网站|谷歌学术搜索
7. a . Bakdi a . Hentout h . Boutami a . Maoudj o . Hachour和b . Bouzouia”最佳的移动机器人路径规划和执行使用遗传算法和自适应模糊逻辑控制,”机器人和自治系统卷,89年,第109 - 95页,2017年。视图:出版商的网站|谷歌学术搜索
8. 刘邓y, y, d .周”的一种改进遗传算法初始种群策略对于对称TSP,”数学问题在工程212794卷,2015篇文章ID, 6页,2015。视图:出版商的网站|谷歌学术搜索
9. b . k . Patle d·r·k·Parhi a . Jagadeesh这位和s·k·卡什亚普,“Matrix-binary代码基于遗传算法的移动机器人路径规划,“计算机与电气工程卷,67年,第728 - 708页,2018年。视图:出版商的网站|谷歌学术搜索
10. m·a·Contreras-Cruz诉Ayala-Ramirez,美国h . Hernandez-Belmonte”移动机器人路径规划采用人工蜜蜂殖民地和进化编程,”应用软计算,30卷,第328 - 319页,2015年。视图:出版商的网站|谷歌学术搜索
11. A·d·惠特利·海恩,豪,“货郎担问题的混合遗传算法使用广义分区交叉,”程序并行解决问题国际会议的性质施普林格,页566 - 575年,克拉科夫,波兰,2010年9月。视图:谷歌学术搜索
12. m . Albayrak和n . Allahverdi“发展一个新的变异算子遗传算法解决旅行商问题的援助,”专家系统与应用程序,38卷,不。3、1313 - 1320年,2011页。视图:出版商的网站|谷歌学术搜索
13. g . Dantzig r . Fulkerson,美国约翰逊,“大规模旅行商问题的解决方案,”美国运筹学学会杂志》上,卷2,不。4、393 - 410年,1954页。视图:出版商的网站|谷歌学术搜索
14. m . Nazarahari大肠Khanmirza, s . Doostie“多目标多机器人路径规划使用改进的遗传算法,在连续环境”专家系统与应用程序卷,115年,第120 - 106页,2019年。视图:出版商的网站|谷歌学术搜索
15. h . j .倪k . Wang黄et al .,”机器人路径规划基于一种改进遗传算法与可变长度染色体”学报2016年12日国际会议对自然计算,模糊系统和知识发现(ICNC-FSKD)长沙,页145 - 149年,中国,2016年8月。视图:出版商的网站|谷歌学术搜索
16. c c。蔡,H.-C。黄,C.-K。Chan“平行精英遗传算法及其应用为自治机器人全局路径规划导航”IEEE工业电子产品,卷。58岁的没有。10日,4813 - 4821年,2011页。视图:出版商的网站|谷歌学术搜索
17. m . m . Malakiyeh s Shojaee, s . Hamzehei Javaran,“洞察一个隐式时间积分法伯恩斯坦基于贝塞尔曲线和三阶基函数对结构动力学,”亚洲土木工程杂志》上,19卷,不。1、1 - 11,2018页。视图:出版商的网站|谷歌学术搜索
18. n . Arana-Daniel a·a·盖乐葛斯c Lopez-Franco et al .,“光滑的全球和本地移动机器人路径规划使用粒子群优化径向基函数,样条函数和贝塞尔曲线”学报2014年IEEE国会进化计算(CEC),第182 - 175页,北京,中国,2014年7月。视图:出版商的网站|谷歌学术搜索
19. 答:a .否决权,d . g . Macharet和m·f·m·坎波斯”可行RRT-based使用第七阶贝塞尔曲线路径规划,”《IEEE国际会议上智能机器人和系统,页1445 - 1450,台北,台湾,2010年10月。视图:出版商的网站|谷歌学术搜索
20. 歌,g .田,f .周”比较研究激光机器人导航路径平滑算法的移动机器人路径规划在智能空间中,“信息与计算科学杂志》上,7卷,不。1,第2950 - 2943页,2010。视图:谷歌学术搜索
21. k . g .快活,r . Sreerama Kumar和r . Vijayakumar”基于贝塞尔曲线的多智能体机器人足球系统中路径规划在不违反加速度限制,”机器人和自治系统卷,57号1,23-33,2009页。视图:出版商的网站|谷歌学术搜索
22. y . j . Ho和j·s·刘,”无碰撞curvature-bounded平滑路径规划使用复合基于泰森多边形法图,贝塞尔曲线”学报2009年IEEE机器人与自动化国际研讨会上计算智能- - - - - - (CIRA)大田,页463 - 468年,韩国,2009年12月。视图:出版商的网站|谷歌学术搜索
23. m . Elhoseny a Tharwat, a . e . Hassanien”基于贝塞尔曲线的路径规划在一个动态的领域,使用改进后的遗传算法,”计算机科学期刊25卷,第350 - 339页,2018年。视图:出版商的网站|谷歌学术搜索
24. a . Tharwat m . Elhoseny a . e . Hassanien et al .,“聪明的贝塞尔曲线使用混沌粒子群优化算法,路径规划模型”集群计算,22卷,不。S2, 4745 - 4766年,2019页。视图:出版商的网站|谷歌学术搜索
25. ,h·l·汉h .八城政基et al ., t·n·内贾德“基于贝塞尔曲线的路径规划自主车辆在城市环境中,”学报2010年IEEE智能车辆研讨会圣地亚哥,页1036 - 1042,美国2010年6月。视图:出版商的网站|谷歌学术搜索
26. 即Škrjanc和g . Klančar多个机器人之间的最优合作防撞Bernstein-Bezier曲线的基础上,“机器人和自治系统,卷。58岁的没有。1、1 - 9,2010页。视图:出版商的网站|谷歌学术搜索
27. 杨k和s Sukkarieh”分析continuous-curvature path-smoothing算法,”IEEE机器人,26卷,不。3、561 - 568年,2010页。视图:出版商的网站|谷歌学术搜索
28. k·l·苏,s·h·贾j . h .郭et al .,“基于蚁群系统的移动机器人路径规划,”学报》2010年第四次国际会议上遗传和进化计算,页210 - 213,深圳,中国,2010年12月。视图:出版商的网站|谷歌学术搜索
29. A·t·伊斯梅尔、A . Sheta和m . Al-Weshah”使用遗传算法的移动机器人路径规划在静态环境下,“计算机科学期刊,4卷,不。4、341 - 344年,2008页。视图:出版商的网站|谷歌学术搜索
30. Chaari, a . Koubaa h . Bennaceur et al .,“SmartPATH:混合ACO-GA机器人路径规划的算法,”《2012年IEEE国会在进化计算,页1 - 8,布里斯班昆士兰,澳大利亚,2012年6月。视图:出版商的网站|谷歌学术搜索
31. k .梁、陈z . j .和x严,“移动机器人路径规划仿真研究”现代电子技术第41卷。。17日,第172 - 167页,2018年。视图:谷歌学术搜索
32. m . m . Malakiyeh s Shojaee, s . h . Javaran”发展的直接基于贝塞尔曲线的时间集成方法和5阶伯恩斯坦基函数,“计算机与结构卷。194年,15-31,2018页。视图:出版商的网站|谷歌学术搜索
33. 郭h . n . Wang, b . Chen等人“扶轮介电弹性体驱动器的设计使用拓扑优化方法对曲线的基础上,“智能材料和结构,27卷,不。5、文章ID 055011, 2018。视图:出版商的网站|谷歌学术搜索
34. 歌,z . Wang l .邹l .徐和f·e·Alsaadi”一种新的平滑的全局路径规划方法的移动机器人运动学约束,“国际期刊的机器学习和控制论,10卷,不。1,第119 - 107页,2019。视图:出版商的网站|谷歌学术搜索
35. l . b .歌曲,z Wang邹et al .,“全球平滑的移动机器人路径规划使用一种新颖的多通道延迟PSO算法,”认知计算,9卷,不。1,5 - 17页,2017。视图:出版商的网站|谷歌学术搜索

版权

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