英语原文共 8 页，剩余内容已隐藏，支付完成后下载完整资料
在不确定环境下基于粒子群优化算法的机器人路径规划
摘要：本文提出了一种在不确定环境下基于粒子群优化算法的机器人路径规划方法。本文认为机器人对其环境的认知是不完整的，即，环境中这些障碍的信息是不确定的。首先基于这些障碍物的不确定性信息构建了一个全局环境模型，然后使用粒子群算法给出了全局最优路径。最后，提出了一种局部最优策略来实时处理机器人检测到的不确定信息。本文初步仿真结果表明，该方法是可行和有效的。
1.引言
移动机器人已广泛用于许多领域，例如在敌对环境中进行太空探索和营救。 在与移动机器人相关的许多技术中，路径规划是成功导航的关键问题，其目标是在满足某些最佳标准的同时在环境中生成无碰撞的路径。一个好的机器人路径规划策略可以保证机器人安全有效地完成所需的任务。因此，近年来对机器人路径规划的问题进行了广泛的研究。
一般来说，机器人路径规划的方法分为两类，即全局路径规划和局部路径规划。全局路径规划是基于事先获得的环境信息，在没有已知障碍物碰撞的情况下生成最佳路径。但是很难获得精确的先验环境信息。鉴于全局路径规划是基于机器人传感器实时获取的环境信息，因此可以避免碰撞这些传感器检测到的环境中的障碍。
然而，现有的路径规划方法通常假设精确地知道环境，即，在某位置是否存在障碍物、障碍物的形状和大小。不幸的是，由于机器人传感器的精度有限，这种假设并不总是成立的，例如本文可以确定障碍物以某种概率位于给定的位置。在这种情况下，本文必须考虑在不确定环境下的路径规划方法。
最近，部分可观察到的马尔可夫决策过程（POMDP）被广泛用于不确定环境中的机器人路径规划，其中机器人的状态和环境中障碍物的信息只能部分观察到。但是，基于模型的方法需要精确的机器人状态和环境中障碍物的模型。一些基于经验的方法不是假设已知模型，而是从经验中学习模型，但是这些方法需要大量的学习数据。
本文提出了一种在不确定环境下机器人路径规划的新框架。本文认为机器人对其环境的认知是不完整的，即信息这些障碍在环境中是不确定的。本文首先基于这些障碍物的不确定信息构建了一个全局环境模型，然后利用一种有效的启发式优化方法——粒子群优化算法给出了一个全局最优路径。最后本文提出了一种局部最优策略来实时处理机器人检测到的不确定信息，以便碰撞自由检测到的障碍物。
本文的其余部分安排如下。在第二节中回顾了有关机器人路径规划的一些相关研究。第三节详细介绍了本文提出的在不确定环境中的路径规划方法。第四部分演示了一些初步的仿真结果。最后，得出一些结论并在第五节中指出研究主题。
2.相关研究
迄今为止，已经应用了各种方法来执行机器人路径规划任务，其中许多常规方法（例如，路线图，Voronoi图等）可以获得全局最优路径。但是由于缺乏适应性和鲁棒性，尤其是动态环境，它们在复杂环境中解决路径规划问题有困难。
众所周知，路径规划的问题是NP难题，还有一些启发式优化算法，例如遗传算法，群智能方法已被广泛采用。
PSO是Kennedy等人提出的基于人口的启发式优化技术，它模仿了在太空中飞翔的鸟群的社会行为。 由于PSO具有易于植入和简单的参数设置等优良性能，因此基于PSO的机器人路径规划研究近年来引起了许多学者的兴趣。
Chen等人将随机PSO应用于移动机器人的平滑路径规划。Wang等人采用有效的编码方案将PSO应用于足球机器人的路径规划。赫里福德基于PSO的结构特征将PSO应用于机器人搜索，其中PSO被视为粒子，并且这些机器人的交互方式与粒子相同。
但是，上述方法很少考虑环境不确定的情况，这在实际应用中非常普遍。因此，上述方法仅具有有限的应用。本文针对不确定环境下的机器人路径规划问题。
3.在不确定环境下使用粒子群优化算法的机器人路径规划
本文考虑移动机器人路径规划的以下问题：在二维环境中寻找机器人从起始位置到目标位置的最短路径。另外，机器人在沿路径移动时应避免与环境中的障碍物碰撞。由于先前的知识有限，因此在机器人移动之前不能完全确定环境中的障碍物信息，即环境是不确定的。
- 对不确定性的说明
本文考虑的不确定性可以描述如下。由于先前的知识有限，本文所知道的不是障碍物的确切信息，而是障碍物的概率。因此，可能会发生两种情况。一个是在环境中的某个位置确实存在障碍物，但是在对环境建模时认为障碍物不存在，这可能导致机器人与该障碍物碰撞。另一个是没有障碍物位于环境中的某个位置，而是在对环境建模时被视为存在障碍物，这可能会导致路径最短。
幸运的是，借助其传感器，机器人可以在其实时移动期间检测是否存在障碍物（如果存在），如果存在，则该障碍物与机器人有多远。基于该信息，在全局最优路径的基础上实时进行局部路径规划。
本文现在考虑所提出的解决障碍的方法的结果。假设在环境中某个位置存在障碍物的概率为p，并且如果在建模时认为不存在成本，则将成本表示为Cn；如果认为存在，则将成本表示为Ce，然后，Cn和Ce描述如下：
（1）
（2）
其中和是与优化相关的权重任务。
不难理解，如果Cnle;Ce，则在建模时考虑存在的障碍是合理的。否则，可以认为它是不存在的。是否存在障碍会影响决策变量应具有的约束。如果环境中的某个位置存在障碍物，则该位置不应与最佳路径交叉，并且机器人的可行空间等于原始空间减去该障碍物所占据的空间。
- 环境建模
为了方便说明，本文考虑如图1所示的机器人环境，其中S分别表示开始位置，T表示目标位置。为了不失一般性，通过将S作为原点，将S与T之间的线作为X轴（其垂直线作为Y轴及其方向）来建立笛卡尔坐标，如图1所示。因此， 开始位置和目标位置分别是S（0，0）和T（，0）。根据先验知识和成本知识，本文假设环境中存在一些矩形障碍，即，，...，，并且的面积由（，），（，），（，），（，），i = 1，2，...，。
现在，本文考虑路径的表达。 为了不失一般性，本文假设通过依次连接条线生成一条路径，并且个转折点，，...，，的坐标分别为（，），j = 1，2，...，。因此，路径由这些个转折点确定。如果本文分别将S和T表示为，，然后通过连接，，...，生成路径。
图1 环境模型
现在，建立路径规划的数学模型。令所有转弯点（，），j = 1，2，...，的坐标为决策变量，则整个路径的长度为
由于路径不能与任何障碍相交，因此约束可以表示为：
本文的目标是寻找不与任何障碍相交的最短路径。因此，路径规划问题转化为以下具有约束的优化问题：
其中表示机器人移动的环境。
C. PSO简介
PSO是Kennedy等人提出的启发式优化技术，其中每个粒子代表优化问题的解决方案。在PSO中，粒子在学习自身经验的同时会与其他粒子通信。在搜索空间中生成一个初始粒子群，其粒子通过速度和位置进行初始化。每个粒子以一定速度随机飞过搜索空间，并相对于两个最佳位置更新自身目标，即本身找到的最佳位置称为个体最优，而其邻域找到的最佳位置称为全局最优，直到找到最佳解。
更新粒子速度和位置的方法如下：
其中和分别是第t代中第i个粒子的速度和位置，i = 1、2，...，，是群大小。是速度的权重。是此粒子实现的最佳位置，而是该群实现的全局最佳位置。和是认知和社会参数，控制着和的影响程度。Rand( )是[0，1]中的随机数，使速度更加多样化。
D. 基于PSO的全局路径规划
现在本文考虑使用PSO优化方程式（4）的方法。有个转折点，每个转折点都是二维的，因此粒子的尺寸为2，因此可以表示为和解码后相应的转折点。
为了更新的个体最优值和全局最优值，需要计算其适应度，表示为。首先对进行解码以获得形成路径的相应转折点，然后根据等式（3）的路径计算出其长度，表示为，因此的适合度可表示为：
（7）
现在，本文考虑障碍物对粒子适应度的影响。 如果不在障碍物(k = 0，...，)所占据的区域内，则由转弯点和形成的路径段不与障碍物(k = 0，...，)相交，然后根据公式（7）计算的适应度；否则，根据公式（5）和（6）生成另一个粒子，直到路径不与任何障碍物相交。
使用PSO进行全局路径规划的步骤如下。
步骤1：初始化群，然后判断所形成的路径段是否与任何障碍物相交，如果是，则将其重新初始化。
步骤2：根据公式（7）计算粒子的适应度，更新其个体最优值和全局最优值。
步骤3：根据公式（5）和（6）更新每个粒子，直到路径不与任何障碍相交。
步骤4：判断是否满足终止条件，如果是，则停止算法；否则执行步骤2。
- 基于PSO的全局路径规划
上述策略产生的全局最优路径是基于不确定信息，可能会导致两种故障。 如上一节所述，一个是在全局优化过程中某些现有障碍不存在，这可能导致与这些障碍发生冲突。另一个是在某些位置没有障碍物，但认为存在障碍物，这可能会导致路径变差。
幸运的是，随着机器人靠近这些障碍物，机器人对环境的认识越来越清晰，这使机器人可以更准确地了解这些障碍物。根据实时获取的信息，机器人可以在必要时执行在线局部最优策略。例如，当机器人确保未建模的障碍物与全局路径的某些部分相交时，它需要执行局部策略以避免与该障碍物碰撞。另一种情况是机器人确保不存在建模障碍物，从而导致最佳路径的最优性降低，然后还执行局部策略以获得最佳路径。
当某些现有障碍不存在时的局部路径规划：为了方便起见，本文假定是现有障碍，但在全局路径规划中不考虑。 路径段与相交，使该路径段不可行，如图2所示。在这种情况下，应执行全局策略。然后应解决以下问题：（1）重新规划时间；（2）选择子起始位置和子目标位置；（3）局部路径规划模型；（4）解决局部路径规划的方法。
图2 路径段与未建模的障碍物相交
本文的目标是在不与障碍物相交的情况下找到从到的局部最优路径。 进行在线局部路径规划的时间应该是机器人已检测到障碍物，并在到达之前完成了局部路径规划。 接着本文选择作为子起始位置，选择作为子目标位置。表示，并链接路径段，，...，形成子路径，然后可以将局部路径规划问题转化为具有约束的优化问题：
其中（，）和（，）分别是和的坐标，以及（，），（，），...，（，）是拐点，，...，的坐标。
本文还采用PSO解决了上述优化问题。类似于公式（7），具有2维的粒子的适合度表示为：
（9）
在此在线全局路径规划过程中，机器人需要一些时间来处理来自传感器的信息并优化路径。本文应该保证机器人在到达子起点之前已经完成了全局路径规划。在这里，本文将机器人的当前位置表示为，如图2所示，其在移动过程中的速度表示为V，将机器人进行全局规划的响应时间表示为Tp，然后应保持以下约束：
（10）
现在本文考虑一个更一般的情况，不是一个路径段而是几个路径段，，...，与障碍物相交，如图3所示。然后本文选择将和分别作为子起始位置和子目标位置，并设置，。其余部分与上一小节中描述的相同。
当某个位置没有障碍物但被认为存在时的局部路径规划：为方便起见，本文假设障碍物确实不存在，但在全局路径规划中被认为是存在的，如图4所示。因此，有必要执行局部路径规划以使路径更优化，该路径应该在机器人检测到障碍物之后执行，并且在机器人到达最接近的转折点之前完成。重新计划时间与上述情况相同。
记下和是最接近的左拐点和右拐点，它们的坐标分别是（，）和（，），本文可以通过以下方程得到和：
分别选择作为子起始位置，选择作为子目标位置。不难理解，连接和的线段是局部最优路径。
图3 路径截面，，...，与未建模的障碍物相交
图4 在全局路径规划期间对不存在的障碍进行建模
3.仿真
在本节中，本文将进行一些仿真，以验证上一节中提出的方法的可行性。这些仿真是在奔腾4 PC上的Visual C 6.0中实现的。实验中PSO的参数设置如下：c1 = c2 = 2；= 1；群大小是20。
在优化过程中，本文将路径分为几个路径段。机器人通过一系列子目标来达到目标。然而，机器人存在次级目标难题，这意味着机器人要精确地到达每个次级目标要花费太多的时间和精力，因为机器人很难精确地定位其位置。更少的细分将减轻机器人的负担，但可能降低最佳效果。这两个因素之间应该有一个很好的权衡。在本文的仿真中，路径由5个路径段组成。然后有4个转折点和8个决策变量。 因此，在优化过程中，每个粒子的尺寸为8。
- 存在一个现有障碍物而没有建模的情况
第一次仿真的目的是演示机器人路径规划过程，其中现有障碍被判断为不存在。 图5表示原始环境。图6表示基于不确定信息的环境模型，其中在基于PSO的全局路径规划中对障碍物，进行了建模。 图7显示了在线局部路径规划，其中虚线表示在线生成的路径段。起始位置和目标位置分别为S（20,200）和T（320,200）。
图5 第一种情况的原始环境 图6 全局路径规划
机器人预先获得的这些障碍物的现有概率分别为 = 0.92， = 0.78，= 0.52。权重的值分别为 = 1，=
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[236124]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
