改进遗传算法的移动机器人动态路径规划.docx

发布时间：2022-06-19 发布人：admin 分类：说明书资料大小：0.53M 资料格式：docx 举报版权申诉

f08f5515-6833-4fe9-bda5-a1e184f8ebd1.docx.pdf-第1页.png

第1页 / 共10页

f08f5515-6833-4fe9-bda5-a1e184f8ebd1.docx.pdf-第2页.png

第2页 / 共10页

f08f5515-6833-4fe9-bda5-a1e184f8ebd1.docx.pdf-第3页.png

第3页 / 共10页

f08f5515-6833-4fe9-bda5-a1e184f8ebd1.docx.pdf-第4页.png

第4页 / 共10页

f08f5515-6833-4fe9-bda5-a1e184f8ebd1.docx.pdf-第5页.png

第5页 / 共10页

f08f5515-6833-4fe9-bda5-a1e184f8ebd1.docx.pdf-第6页.png

第6页 / 共10页

f08f5515-6833-4fe9-bda5-a1e184f8ebd1.docx.pdf-第7页.png

第7页 / 共10页

f08f5515-6833-4fe9-bda5-a1e184f8ebd1.docx.pdf-第8页.png

第8页 / 共10页

文本预览

改进遗传算法的移动机器人动态路径规划摘要：本研究针对遗传算法（GA）提出了一种新的变异算子，并将其应用于动态环境下移动机器人的路径规划问题。移动机器人的路径规划在障碍物环境中发现从起始节点到目标节点的可行路径。通过利用其强大的优化能力，遗传算法已被广泛用于生成最优路径。虽然简单遗传算法或其他改进的变异算子中的常规随机变异算子会导致不可行路径，但所提出的变异算子不会并且避免早熟收敛。为了证明所提出的方法的成功，它被应用于两种不同的动态环境，并且与之前在文献中改进的 GA 研究进行了比较。与所提出的变异算子相比，遗传算法寻找最优路径的次数要多得多，并且比其他方法收敛得更快。 1.介绍最近，研究人员对自动驾驶汽车的兴趣随着技术发展而增加。关于自动驾驶汽车的文献中有许多研究。自主车辆研究的主要课题之一是路径规划。路径规划试图为移动机器人在有障碍物的环境中从起始节点移动到目标节点寻找一条可行路径[1]。路径规划环境可以是静态的也可以是动态的。在静态环境中，在开始执行之前必须找到整个解决方案。但是，对于动态或部分可观察的环境，需要经常重新计划，需要更多计划更新时间。一般来说，移动机器人路径规划的主要问题是计算复杂性，局部最优性和适应性的存在。研究人员一直在寻找替代和更有效的方法来解决这些问题[2]。有许多关于使用各种方法的机器人路径规划的研究，例如基于网格的算法，道路图（Voronoi 图和可见性图），细胞分解和人工势场。以前的一些方法使用全局方法来搜索工作空间中的可能路径，通常只处理静态环境，并且在环境复杂的情况下计算量很大[3]。每种方法的有效性取决于应用环境的类型，每种方法都有自己的优缺点。例如，即使在静态环境中，人工势场法也只能给出一条可能不是最短路径的解决方案路线。Ajmal Deen Ali 等人[4]研究了遗传算法（GAs）对研究机械手的无碰撞路径规划以减少搜索时间和提高解决方案质量的有效性。发现这种方法的结果比传统的 Asearch 更好，无论是在旅行距离上还是在计算时间上。 Chen 和 Zalzala [5]将 GA 与改进的 Amethod 在移动机器人路径规划中进行了比较。据观察，尽管修改的 A 方法可以比 GA 更快地获得解，但修改的

Amethod 可以很容易地陷入局部最小值，而 GA 总能达到全局最优或接近全局最优。与传统的搜索和优化方法（如基于微积分和枚举的策略）相比，进化算法是健壮的，全局的，并且通常更直接地应用于对需要解决的问题很少或没有先验知识的情况[6]。一种在路径规划方面优于其他方法的技术是 GA 方法，因为它能够探索解空间，同时保留已经找到的最佳解决方案[7]。在过去的十年中，GAs 被广泛用于利用其强大的优化能力来产生最优路径[8]。遗传算法已被认为是复杂和不良行为目标函数的最稳健搜索技术之一。遗传算法在开发接近最优解的过程中具有吸引力的基本特征是它们本质上是并行搜索技术[9]。他们可以以平行的方式同时搜索所有工作环境，因此他们可以更快地达到更好的解决方案。近年来，许多基于遗传算法的路径规划已经通过定制遗传算子的方式得以实现，其中大部分都是改进的方法。他们成功地获得了更好的解决方案。虽然简单遗传算法中的常规随机变异算子会导致不可行路径，但本研究中提出的变异算子会增加种群的多样性并避免早熟收敛。本文组织如下：在第 2 节中，我们解释了如何将 GAs 应用于移动机器人的路径规划问题; 第 3 节分析了以前报道和本文提出的变异算子; 第 4 部分评估实验研究和结果; 在第 5 节中我们总结了这篇文章的主要发现。 2.遗传算法的路径规划遗传算法是一种模拟自然遗传算子的并行和全局搜索技术。因为它同时评估参数空间中的许多点，所以它更可能收敛到全局最优。搜索空间不必是可区分的或连续的[10-12]。 2.1 环境表示许多路径规划方法使用基于网格的模型来表示环境空间，如图 1 所示。已经确定用基于网格的表示法计算障碍物的距离和表示更容易。基于网格的环境空间通过有序编号的网格[1,13-15]或通过（x，y）坐标平面[9,16,17]的方式以两种方式表示。已经发现在文献中有序编号的网格表示被广泛使用，因此这种表示方法被用于本研究中。图 1.基于网格的环境表示。

2.2 染色体的编码染色体代表路径规划问题的候选解决方案。染色体或路径由起始节点，目标节点和移动机器人越过它们的节点组成。这些节点或路径中的步骤被称为染色体的基因。不同的编码方法被用来创建染色体。一般使用二进制编码的字符串方法[9,18,19]，但是也使用十进制编码的字符串方法[1,13,14]，它被认为更灵活。十进制编码需要更少的内存和更少的优化空间。如图 2 所示，一个有效的路径由一系列网格标签组成，这些网格标签从起始节点开始到结束于目标节点。 2.3 人口初始化最初的人口一般是随机产生的。一些生成的染色体可能包括与障碍相交的不可行路径。即使最初的种群包含不可行的路径，遗传算子也可以找到最优或接近最优的解。但是，此过程会降低算法的搜索能力，并增加寻找最佳解决方案的时间。此外，两个不可行染色体的交叉可能会产生新的不可行路径。为了解决这个问题，每个染色体在产生初始种群时都必须检查它是否与障碍物相交。如果

是这样，染色体上的相交基因会随机变化，并且是可行的。在这项研究中，遗传算法与随机生成和可行的初始种群一起运行。对于相同的环境和 10 次运行，每种方法的平均适应值，生成次数和求解时间在表 1 中给出。确定以可行的初始种群开始 GA 是相当有益的，也如[13，14]。 2.4 健身功能路径规划问题的目的是在起始节点和目标节点之间找到最佳路径。最佳路径可能是最短的，最短的时间和能量需求路径。通常，在路径规划问题中，目标函数被认为是最短路径。在这项研究中，用于遗传算法的染色体的目标函数值在以下等式中给出：这里; f 是适应函数，pi 是染色体的第 i 个基因，n 是染色体的长度，d 是两个节点之间的距离，xi 和 yi 是机器人当前的水平和垂直位置，x（i+1）和 y i + 1）是机器人的下一个水平和垂直位置。机器人的方向由以下公式确定：目标函数值定义为路径中每个节点之间的距离之和。如果在机器人方向上存在障碍物，则将惩罚添加到目标函数值。惩罚值应该大于环境的最大路径长度。为了寻找最佳路径，该算法搜索消除了惩罚的染色体。图 2.染色体的十进制编码基因

2.5 选择方法图 3.单点交叉遗传算法的主要原理是，染色体上最好的基因应该存活并转移到新一代。在这个阶段，需要进行选择程序来确定最佳染色体。选择过程由三个步骤组成。第一步，找到所有染色体的目标函数值。在第二步中，根据其目标函数值将适应度值分配给染色体。在这项研究中，使用基于等级的适应性分配而不是比例分配方法。这可以防止一些更好的染色体在人群中占优势。在最后一步中，根据适应值选择染色体，然后将其置于交配池中以产生新的染色体。 2.6 交叉操作符通常，交叉结合两条亲本染色体的特征以形成两条子代。如图 3 所示，本研究中使用单点交叉算子。交叉点后的两条染色体的基因被交换。 2.7 突变算子在交叉操作之后，群体中的所有候选染色体都经历随机突变。这是一个随机的逐位二进制补码操作或基因中的随机小变化，取决于染色体的编码，以突变率的概率统一应用于群体中所有个体的所有基因。变异操作将搜索空间扩大到可能不接近当前总体的区域，从而确保全局搜索[14]。变异操作增加了种群的多样性并避免了过早收敛。 3.一种新的路径规划变异算子在传统的遗传算法中，随机变异是最常用的算子。然而，随机突变可能导致不可行路径的产生。即使在变异操作之前染色体是可行的，由变异改变的新

节点可能具有障碍，因此它构成如图 4a 所示的不可行路径。这使得优化变得更慢并且增加了世代的数量。为了克服这个问题，一些关于突变操作改进的研究已经在文献中完成。其中之一，最常见的是检查新的突变染色体的可行性。如果不可行，则在染色体上应用新的突变，直到产生可行的突变。 Changan 等[20]使用改进的遗传算法，这种爬山方法在当前最好的个体周围寻找更好的个体，而突变个体被更好的个体取代。 Li 等人提出了另一种更有效的突变改进方法。[14]专门用于解决移动机器人的路径规划问题。该方法从紧邻突变基因的所有空闲节点集合中随机选择一个节点，然后根据前向方向接受该节点，这可以通过比较起始节点和目标节点的坐标来确定（参见图 4b）。如果变异操作之后的新路径不可行或不合需要，则重复随机节点选择直到该组的搜索过程结束。图 4.各种变异算子的比较表 2 提出的变异算子的程序在这项研究中，提出了一种新的变异算子方法，如表 2 所示。虽然它看起来像[14]中提到的方法，但所提出的方法在两种方式上不同于该方法。首先，提出的突变方法同时检查整个自由节点靠近突变节点，而不是随机选择一个节点。这

意味着所提出的方法可以保证找到最好的节点，然而在找到最好的节点之前，逐个随机选择可能会接受更好的节点。第二，所提出的方法根据总路径的适应度值来接受节点，而不是通过变异节点的移动方向（见图 4c）。即使突变节点的方向与从开始到目标节点的方向相反，最佳路径也可以由适应值确定。作为一个例子，由染色体（0,31,62,65,99）表示的路径取自图 1 所示的环境。随机选择的节点 65 被视为突变基因。突变节点的邻居组由节点 {54,55,56,64,66,74,75,76}组成，然而节点 54,55 和 56 是障碍网格。除了节点 54,55,56 之外，找到所有邻居的适合度值。根据适应度值，将包括节点 65 的路径确定为具有最小距离的适合度路径。因此，在突变之后节点 65 将被节点 66 替代，并且新染色体将是（0,31,62,66,99）。 4.动态环境的实验和性能评估为了证明所提出的方法的成功，它被应用于两种不同的动态环境，并且与之前在文献中改进的 GA 研究进行了比较。首先，处理[14]中使用的环境。图 5a 显示了初始环境，即机器人开始移动之前的环境，由 16 * 16 个网格组成，并具有六个障碍区域（阴影区域）。图 5b 示出了原始环境的修改版本，其是在机器人开始移动之后改变的环境，具有七个障碍区域。 GA 的参数如下。人口规模为 60，交叉概率为 1，变异概率为 0.3。对于环境＃1，GA 利用随机突变的方法逐一运行，Ref。 [14]，参考文献中的突变。 [20]和本研究中提出的突变。对每种方法 GA 进行 100 次。表 3 和 4 分别给出了初始和修改环境的实验结果。表格包含了 100 次试验中最佳解决方案的数量，近乎最优解决方案的数量和不可行解决方案的数量。表格还包含 100 次试验中最佳加近似最优解的平均适应值，平均世代数和平均解。在表 3 和表 4 中清楚地看到，提出的变异算子的遗传算法分别找到最优路径 54 和 44 次，而其他方法仅找到几次。所提出的方法在 2 或 0 次试验中分别找不到可行的路径，而其他方法在 5 至 29 次试验中不成功。该方法的平均适应度值和平均代数均优于其他方法的值。然而，即使所有这些都不到一秒钟，所提出的方法的平均解决时间比其他方法的解决方案时间更差。图 6 显示了所有方法的收敛性。具有所提出的方法的 GA 比其他方法收敛得更快。因此，这使得该方法在动态环境中有利。

为了进行额外的比较，我们产生了一个比前一个更加复杂的新的动态环境，如图 7 所示。图 7a 示出了初始环境，其是机器人开始移动之前的环境，由 16 * 16 个网格组成并且具有九个障碍区域（阴影区域）。图 7b 示出了原始环境的修改版本，其是在机器人开始移动之后改变的环境，具有十个障碍区域。GA 的参数如下。人口规模为 80，交叉概率为 1，变异概率为 0.2。对于环境＃2，GA 采用与环境＃1 中相同的方法逐一运行。每种方法对遗传算法执行 100 次。表 5 和 6 分别给出了初始和修改环境的实验结果。表格包含了 100 次试验中最佳解决方案的数量，近乎最优解决方案的数量和不可行解决方案的数量。表格还包含 100 次试验中最佳加近似最优解的平均适应值，平均世代数和平均解。从表 5 和表 6 中可以清楚地看到，GA 与所提出的变异算子分别找到最优路径 9 和 32 次，而其他方法分别仅找到最大 2 次和 15 次。所提出的方法在 13 次或 0 次试验中分别找不到可行路径，而其他方法在 31-59 次和 0-8 次试验中不成功。该方法的平均适应值和平均生成数均优于其他方法。然而，即使所提出的方法的平均求解时间并不比其他方法的求解时间好，但所有方法都是彼此接近的。图 6.示例＃1 的变异算子的收敛性比较。

分享到：

赞收藏

资料库

改进遗传算法的移动机器人动态路径规划.docx

相关推荐

人工智能

热门标签

最新资料