基于BPF的移动机器人避障及路径规划外文翻译资料

 2022-01-23 21:03:54

基于BPF的移动机器人避障及路径规划

摘要

在本文中，使用一种新的路径规划方法计算移动机器人（MR）的静态和动态障碍环境中的最佳路径。所提出的方法称为细菌势场（BPF），确保了可行、最佳和安全的路径。该新颖的提议利用人工势场（APF）方法和细菌进化算法（BEA）来获得增强的灵活路径规划方法，该方法具有使用APF方法的所有优点，大大减少了其缺点。针对经典APF方法，以及伪细菌势场（PBPF）方法和遗传势场（GPF）方法的BPF方法的顺序和并行实现的对比实验，所有这些都基于进化计算，实现了优化APF参数。设计了一个使用MR真实模型的仿真平台来测试路径规划算法。一般而言，已经证明BPF通过减少计算时间来寻找最佳路径至少1.59倍，从而优于APF，GPF和PBPF方法。 这些结果对BPF路径规划方法在动态复杂环境中满足局部和全局可控性的能力产生积极影响，避免与干扰MR导航的对象发生碰撞。

第一章 介绍

移动机器人（MR）的自主导航的问题在于在没有人类操作员的帮助的情况下将其从一个位置带到另一个位置，特别是规划可达到的一组MR配置以完成其任务。为了解决这个问题，有必要采用一种方法，该方法允许引导MR完成一组导航和操作目标，即其任务。一般而言，该方法涉及运动规划，其包括两个不同但互补的任务，路径规划和轨迹规划。第一个是设计一个动态系统，可以将MR从初始位置（状态）驱动到目标位置（目标），而轨迹规划则侧重于以一种尊重MR的机械限制的方式确定如何沿着路径规划算法给出的解决方案移动MR。

在本文中，我们提出了一种称为细菌势场（BPF）的新方法，用于MR中的路径规划。 BPF提案基于利用细菌进化算法（BEA）增强的人工势场（APF）来解决原始APF给出的限制。 目前，这是用于MR的路径规划的BPF算法的第一个实现。

最初的APF方法是一种广泛用于MR自主导航的数学方法，因为它提供了对运动的有效控制；这种方法的一些推导已被用于路径规划。然而，它存在一些限制；这些解决方案被发现受到本地最小值的影响，并且在许多情况下远非最佳解决方案，因为规划只是局部的和反应性的。使用BPF提议的路径规划允许MR以自主形式导航而不会陷入局部最小值，使得BPF提议适合在动态环境中工作，这在实际应用中非常关键。图1总结了BPF相对于原始APF方法以及其具有进化人工势场（EAPF）的方法的显着优势，。

在第2节中，提供了一些关于机器人运动规划的经典的（包括APF），启发式和元启发式的重要方法。在第3节中，强调了这项工作的主要理论贡献，并给出解释了实现该方法的代码。在第4节中，对BPF提案的实验进行了解释，分析和比较两个EAPF的性能，特别是基于遗传算法的遗传势场（GPF）方法和第二个EAPF基于伪细菌遗传算法被称为伪细菌势场（PBPF）的方法。最后，在第5节中，提供了结论和未来的工作。

图1 BPF相对于APF和EAPF的优势

第2章 相关工作

机器人运动规划的起源可以追溯到20世纪60年代中期。它一直由经典方法主导，如路线图，细胞分解，数学规划和APF。 路线图方法的代表性提议是可见性图，它是自由空间中的线的集合，将对象的特征连接到另一个; 几何对象集合的Voronoi图是将空间划分为单元格，每个单元格由更接近一个特定对象的点组成；在Subgoal Network中，保留了从启动配置到可达配置的列表。 Silhouette方法包括生成工作单元的轮廓并通过将这些轮廓曲线相互连接来开发路线图。 细胞分解算法的思想是将C空间分解为一组简单单元，然后计算单元之间的邻接关系。在数学规划方法中，避障的要求由配置参数上的一组不等式表示；我们的想法是最小化某些标量，以找到起始位置和目标位置之间的最佳曲线。Khatib（1986）介绍了APF概念。 最初，这种方法被用于机器人路径规划中的避障，随着时间的推移，它被机器人和机器人组很好地采用，在Barnes，Fields和Valavanis（2009）中提供了一个例子，提出了一种具有潜在场的群体控制，以控制机器人群体形成，避障和群体运动。在APF中，MR被视为在配置空间中表示由U（q）表示的APF影响的粒子的点，其局部变化反映自由空间结构； APF方法背后的想法是在目标点周围建立一个有吸引力的潜在场力，以及在障碍物周围建立一个排斥势场力。 两个潜在的领域（吸引力 排斥性）形成了称为APF的总潜在领域。

在Masehian和Sedighizaddeh（2007年）中，调查了1973年至2007年的1381篇论文，涵盖了机器人运动规划领域的足够深度的文献。 在本文中，提出了一种启发式技术的广泛分类，这有助于其分析和方法的期望。 从广义上讲，给定的分类如下：概率，启发式和元启发式方法。前者是概率路线图，快速探索随机树，水平集和语言几何。 启发式和元启发式方法是神经网络、遗传算法（GA）、模糊逻辑算法、蚁群算法等。所有提到的方法都有各自的优点和缺点; 它们彼此紧密相连，并且在许多应用中，它们中的一些被组合在一起以最有效和高效的方式得到所需的机器人控制器。

在本文中，BPF被提出作为移动机器人路径规划的一种方法，确保机器人导航的可行的，最佳的和安全的路径。BPF提议使用来自APF的数学规划和元启发式的概念来有效地解决机器人路径规划问题，确保可达到的配置集和可控性（如果存在）优于当前的APF方法。APF是一种反应式运动规划方法，在寻找全局最优路径时具有固有的众所周知的困难，因为它无法解决所有局部最小问题；因此，已经开发出克服这些挑战的现代方法。其中之一是APF与进化算法（EA）混合，获得了一种名为进化人工势场的不同潜在场方法，这里APF方法与GAs结合得出 最佳潜在场功能。变分规划方法将潜力用作成本函数，并尝试找到达到目标点的路径，从而最大限度地降低此成本。

此外，Nawa，Hashiyama，Furuhashi和Uchikawa（1997）提出了一种称为伪细菌遗传算法（PBGA）的新型进化算法，该算法成功应用于从一组输入和输出数据中提取规则。该算法引入了称为细菌突变的遗传操作，已证明该系统在系统参数之间的关系较弱的环境中是有用的。这是一种简单的算法，可以在解决方案中快速收敛和改进，而不会对地标检测产生不利影响。此外，Nawa和Furuhashi（1999）提出了用于模糊规则库提取的细菌进化算法（BEA）。 该算法基于PBGA，由一种称为基因转移的新遗传操作支持，该遗传操作建立了来自种群的个体之间的关系; 它还可以用于减少或增加模糊规则库中规则的数量。 PBGA和BEA都是全球搜索方法。与GA相比，BEA的全局最优收敛更快，这很重要，因为省略了组合的计算过程成本。与GA相比，细菌学方法更像是一种自适应方法，而不是优化方法。它旨在改变初始种群，使其适应特定环境，适应性仅基于个体的微小变化，种群中的个体被称为细菌并且对应于原子单位。与遗传模型不同，细菌不能分裂，交叉操作不能再使用了，细菌只能被复制和改变以改善种群。

第3章 BPF路径规划器开发

路径规划在具有障碍物的环境中产生无碰撞路径（可行）并且相对于诸如距离，时间或能量，距离是最常采用的标准并且用于该工作的某些标准进行优化。 为了开发BPF路径规划方法，需要考虑以下几点：

1、路径p是一组数据n MR将起始位置q0连接到最终位置qf。

2、由于具有可达到的配置集和可控性密切相关，前者必须存在以便完成控制MR的控制任务，以满足系统设计者施加的总时间T =的要求。

3、系统的小时间局部（Tst）可控性意味着MR可以在T st =Tp Tj，给定的时间内从P中的任何点，比如qa到qb，其中tp是规划者采取的时间 计算路径，时间tj是轨迹规划器和跟随算法所消耗的时间，这取决于MR架构。

4、对于具有已定义P的在线计划中的静态环境，时间t p为零，因为景观没有变化。 然而，对于具有动态环境的景观，时间t p上升其重要性，因为慢速路径规划算法将不满足局部和全局可控性标准。

BPF提案是一种原始路径规划方法，它使用潜在函数（Khatib，1986）作为寻找最优路径的成本函数；因此，BPF和APF方法具有共同的数学基础; 在这项工作中，他们有以下相似之处：

1、移动机器人q在2-D欧几里得坐标系中

2、移动机器人以半径r，圆心C=（x，y）和方向。因此，系统中MR的位置由q=（c,r,）给出。在APF，r = 0，但在BPF中，r用于表示物理尺寸MR。

3、他们需要一个起始位置q 0，一个目标位置q f和障碍物位置O 1 ,hellip;, O n。

4、他们使用由（1）给出的势函数Utotal(q)，它包括两个项，（2）描述的吸引势函数Uatt(q)，以及（3）中描述的排斥势函数Urep(q)。

（1）

2 （2）

(3)

5、（2）中的ka和（3）中的kr是分别代表函数的吸引力和排斥比例增益的标量变量。

6、在（3）中，q0是势场的影响的极限距离，q是到障碍物的最短距离。

7、MR使用F（q）=Utotal（q）给出的总力来导航。

3.1 BPF算法

BPF提议使用起点，目标和障碍物位置作为特征来获得MR必须达到的一系列目标点，以及受吸引力和排斥力影响的梯度信息，以将一系列目标点变换为路径P，因此提案实现了路径规划生成的任务，具有特定的特性，即如果它存在于动态环境中，它以非常低的计算成本提供最佳或接近最优的可达配置（路径）集。

如图3.1所示算法1中，给出了BPF方法的伪代码; 比例增益通过BEA进行演化，BEA使用算法3中解释的APF方法作为适应度函数。特别是，我们的原型BEA函数由（4）给出，

[var1,hellip;,varn,fitValue]opt=BEA([var1,hellip;,varn],BEAparam,FitFunc,Np) (4)

在函数的右边，[var1，...，varn]是使用特定突变率，感染数量，细菌数量等进行优化的参数，目的是实现优化标准 根据FitFunc给出的适应度函数，最后一个参数N p是要使用的处理器数量。 返回值是优化变量[var1，...，varn]和相应的适应值fitValue。

图3.1 算法1

3.2 细菌进化算法

细菌进化算法（BEA）引入了两种受微生物进化现象启发的操作。细菌突变操作的工作是优化单个细菌的染色体，以及基因转移操作，以提供人群中细菌之间的信息传递（Botzheim＆Koacute;czy，2004）

在最基本的形式中，可以使用（5）所描述的差分方程对BEA进行算法建模以用于计算机模拟

P(t 1)=s(v(P(t)) (5)

其中t表示时间，新的种群P(t 1)是在由随机变异v和选择s操作之后从实际种群P（t）获得的。在这种情况下，考虑到Omega;是Rn的子集称为约束集（可行集），解向量pOmega;称为个体（细菌），由离散单元组成。每个离散单元控制细菌的一个或多个特征；默认情况下，这些单位是二进制位（Mitchel，2001）。群体是随机初始化的NB细菌的集合。BEA使用细菌突变和遗传转移操作从现有的解决方案中生成新的解决方案。

如图3.2所示的算法2本质上是并行的。分而治之的策略可以以多种不同的方式应用；我们使用单一群体主从方法，其中一个主节点执行处理单个群体P（t）的BEA操作，并且P（t）中个体的适合度评估被划分为P i（t）分布在几个子处理器之间的子群体（Cantuacute;-Paz，2001）。 对于输入参数Np为1的特定情况，我们有顺序实现；其他输入参数是：符合细菌的变量数组[var1，...，varn]，BEA参数包含在BEAparam中，其中给出了有关突变率，感染次数，停止条件等的信息， 和适应度函数fitFunc。 该算法将返回一个包含优化变量的数组，以及找到的最佳适应值fitValue。

图3.2 算法2

3.3 APF最适函数

APF方法在机器人的路径规划中具有很大的优势，其中来自用户的基本输入是起始位置，目标位置以及吸引力和排斥潜在收益的值。在这项工作中，如图3.3所示1算法3基于APF方法，并且它被设计用作所提出的BPF方法的适应度函数。经典的APF能够找到可行的路径，并且MR以自主形式达到目标位置;这可以避免设定点之间的障碍。不幸的是，对于经典的APF方法，有必要为方法提供适当的增益值（通常，程序员通过反复试验提供值）；否则，很可能找不到可行的路径;因此找到最佳收益集的重要性。众所周知，路径规划应用中的这样的任务是艰苦的，因为问题导致了一些计算问题，其中一些，目前，它们仍然是开放的问题，因为对于大空间，没有令人信服的解决方案，因为现有的可以持续很长时间使MR可控性不可行。因此，具有可以以高计算速度找到最佳参数的方法（例如BPF）的重要性使得机器人系统在巨大且动态的场景中可控制。

全文共11198字，剩余内容已隐藏，支付完成后下载完整资料

英语原文共 15 页，剩余内容已隐藏，支付完成后下载完整资料

资料编号：[711]

原文和译文剩余内容已隐藏，您需要先支付 30元 才能查看原文和译文全部内容！立即支付

以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。

您可能感兴趣的文章