PPT讲稿RobotPathPlanningus1

《PPT讲稿RobotPathPlanningus1》由会员分享，可在线阅读，更多相关《PPT讲稿RobotPathPlanningus1（24页珍藏版）》请在装配图网上搜索。

1、1Robot Path Planning using Particle Swarm Optimization of Ferguson Splines采用采用Ferguson样条粒子群优化的机器人路径规划样条粒子群优化的机器人路径规划算法算法2摘要摘要 机器人路径规划问题是移动机器人最重要的任务之一。机器人路径规划问题是移动机器人最重要的任务之一。本文提出了一种新方法，采用三次样条方法来描述路径。这样本文提出了一种新方法，采用三次样条方法来描述路径。这样描述的路径执行起来容易。而且，在重要的样条交接处，这种描述的路径执行起来容易。而且，在重要的样条交接处，这种描述方法也有利于实现平滑微分。描述方

2、法也有利于实现平滑微分。这样，路径规划问题就等同于最优化样条参数的问题。这样，路径规划问题就等同于最优化样条参数的问题。基于其快速的收敛性和全局搜索特性，本文采用一种叫粒子基于其快速的收敛性和全局搜索特性，本文采用一种叫粒子群优化的进化算法群优化的进化算法(Particle Swarm Optimization,PSO)。本文采用各种不同的本文采用各种不同的PSO参数进行测试。并与两种经典的参数进行测试。并与两种经典的机器人路径规划算法进行比较测试，证明了本文算法的有效性。机器人路径规划算法进行比较测试，证明了本文算法的有效性。31.Introduction 移动机器人障碍物规避算法，就是在约

3、束条件下，比如已知移动机器人障碍物规避算法，就是在约束条件下，比如已知障碍物障碍物O的位置和形状的情况下，找到一条从起点的位置和形状的情况下，找到一条从起点S到目标终点到目标终点G的路径。所用的参数都作为算法的输入，输出或者是一条从的路径。所用的参数都作为算法的输入，输出或者是一条从S到到C最佳的轨迹，或者是与局部最优轨迹相关的方向。通过路最佳的轨迹，或者是与局部最优轨迹相关的方向。通过路径算法进行补偿函数的最优化可以分两步进行。第一步计算径算法进行补偿函数的最优化可以分两步进行。第一步计算出轨迹的长度出轨迹的长度(或者是需要计算出轨迹的时间或者是需要计算出轨迹的时间)。第二步保证路。第二步保

4、证路径的安全性径的安全性(例如：与障碍物的距离例如：与障碍物的距离).因此，如何在满足这些要、因此，如何在满足这些要、求的前提下找到可接受的折衷方案，就是障碍物规避算法的核求的前提下找到可接受的折衷方案，就是障碍物规避算法的核心问题。心问题。4在当前的机器人文献中，提到了许多障碍物规避算法。不幸的在当前的机器人文献中，提到了许多障碍物规避算法。不幸的是，算法中的大部分只是将一些点作为输出，这样造成机器是，算法中的大部分只是将一些点作为输出，这样造成机器人执行困难。机器人能够沿着点与点之间的线段移动，但是人执行困难。机器人能够沿着点与点之间的线段移动，但是这种移动是不连续的。机器人必须在线段的终

5、点停止，调整这种移动是不连续的。机器人必须在线段的终点停止，调整其方向后再继续。可以采用相关函数计算插补点，以有利于其方向后再继续。可以采用相关函数计算插补点，以有利于机器人的运动。这种方法能够实现快速到达终点的目的，但机器人的运动。这种方法能够实现快速到达终点的目的，但是在障碍物的约束下，这些轨迹往往不是最优轨迹，而且会是在障碍物的约束下，这些轨迹往往不是最优轨迹，而且会产生碰撞的可能性。产生碰撞的可能性。我们采用直接对期望路径的描述函数进行最优化的方法。函数我们采用直接对期望路径的描述函数进行最优化的方法。函数的参数可以作为控制模块的输入，而且不再需要进行后处理。的参数可以作为控制模块的输

6、入，而且不再需要进行后处理。Ferguson三次样条被选作描述轨迹的函数，因为其具有简单三次样条被选作描述轨迹的函数，因为其具有简单的几何意义。的几何意义。PSO算法作为最优化方法使用，在具有局部最算法作为最优化方法使用，在具有局部最小化的情况下该算法具有良好的结果。这种算法非常新，也小化的情况下该算法具有良好的结果。这种算法非常新，也从来没有用于解决相似度问题。另外，因为搜索空间的多维从来没有用于解决相似度问题。另外，因为搜索空间的多维性，传统的迭代方法不能够在实时情况下应用。性，传统的迭代方法不能够在实时情况下应用。5文章的组织结构如下：在文章的第二部分，我们介绍了碰撞规文章的组织结构如下

7、：在文章的第二部分，我们介绍了碰撞规避算法：包括避算法：包括Ferguson splines(Ferguson样条样条)、particles coding（粒子编码）、适应度函数以及（粒子编码）、适应度函数以及PSO算法。在第三部算法。在第三部分，我们介绍了实验的结果，介绍了影响算法的部分因素，分，我们介绍了实验的结果，介绍了影响算法的部分因素，并且与在机器人足球运用中标准的算法做比较。并且与在机器人足球运用中标准的算法做比较。62.Method7891011123.Result 本文在两个实验中测试提出的路径规划算法。第一个实验研本文在两个实验中测试提出的路径规划算法。第一个实验研究不同的究

8、不同的PSO算法参数设置的影响，另一个实验我们将算法与机算法参数设置的影响，另一个实验我们将算法与机器人足球其他算法比较器人足球其他算法比较(Potential Eield和和Visibility Graph).最后最后一部分描述进化过程如何解决局部最优值得问题。一部分描述进化过程如何解决局部最优值得问题。A PSO parameter tuning PSO参数调整参数调整 本节列出了等式本节列出了等式(20)中不同的常量设置对算法的影响。如图中不同的常量设置对算法的影响。如图2所示，可以观察出几个显著的特点。所示，可以观察出几个显著的特点。1314151617C.Comparison在本节中

9、，我们将说明我们的算法与其在本节中，我们将说明我们的算法与其他两种算法他两种算法-Potential Field和和Visibility Graph算法比较的结果。算法比较的结果。图图5所示为在标准的机器人足球环境下所示为在标准的机器人足球环境下的的3种算法的结果。采用样条的方法在种算法的结果。采用样条的方法在30次次PSO迭代时候就找到了短和平滑的迭代时候就找到了短和平滑的轨迹。其中，每个种群包含轨迹。其中，每个种群包含15个粒子。个粒子。采用采用VG算法的机器人，也能够找到最短算法的机器人，也能够找到最短路径，但是机器人必须在急转弯的时候路径，但是机器人必须在急转弯的时候减慢速度，否则容易

10、撞到障碍物上。采减慢速度，否则容易撞到障碍物上。采用用Potential field方法找到的路径在方法找到的路径在三种算法中是最长的，并且在接近函数三种算法中是最长的，并且在接近函数Z的局部极值处具有一些小幅度的振荡的局部极值处具有一些小幅度的振荡(图图中用中用LE标记标记)。18图图6所示为三种路径规划算法所示为三种路径规划算法的共同测试的共同测试(在具有长墙障在具有长墙障碍物的情况下碍物的情况下)。在这个过。在这个过程中，程中，Potential Field方法没有找到合适的轨迹，方法没有找到合适的轨迹，因为其最优化过程陷入局因为其最优化过程陷入局部最优。部最优。PSO算法成功避算法成功

11、避开障碍物，即使在初始粒开障碍物，即使在初始粒子群中也没有发生碰撞。子群中也没有发生碰撞。算法需要算法需要50个粒子群，每个粒子群，每个粒子群包含个粒子群包含15个粒子。个粒子。19C Evolutional process study 进化过程研究进化过程研究 在本节中我们将介绍在本节中我们将介绍PSO算法克服陷入局部最优的能力。在机算法克服陷入局部最优的能力。在机器人工作空间采用长障碍物，在这种环境下的适应度函数具器人工作空间采用长障碍物，在这种环境下的适应度函数具有局部极小解。具有这种适应度值的粒子，其轨迹往往是连有局部极小解。具有这种适应度值的粒子，其轨迹往往是连接起点和终点的线段，所

12、以容易造成与障碍物的碰撞。局部接起点和终点的线段，所以容易造成与障碍物的碰撞。局部极小值对进化过程影响很大，因为随机生成的种群中大部分极小值对进化过程影响很大，因为随机生成的种群中大部分粒子都处于这样的环境之中。而且初始种群常常比包含总极粒子都处于这样的环境之中。而且初始种群常常比包含总极值的粒子。值的粒子。查找移动机器人最优轨迹的进化算法中查找移动机器人最优轨迹的进化算法中131516,常常在这个常常在这个情况下失败。图情况下失败。图7说明了为什么说明了为什么PSO算法能够成功。算法在这算法能够成功。算法在这种情况下，比图种情况下，比图6所描述的需要更多的种群。因为为了更加透所描述的需要更多

13、的种群。因为为了更加透明，采用了小的种群明，采用了小的种群(仅仅仅仅10个微粒个微粒)。20图图7(a)所示为在工作空间内随机生成的初始种群。最小适应度函数值的所示为在工作空间内随机生成的初始种群。最小适应度函数值的种群具有最短的轨迹。种群具有最短的轨迹。图图7(b)所示为在探索模式下所示为在探索模式下(exploratory mode)的种群的种群(高值高值)。粒子遍布。粒子遍布整个工作区域，所以能够克服局部极值。整个工作区域，所以能够克服局部极值。21由于采用小的种群，在第由于采用小的种群，在第39th种群中找到最优解种群中找到最优解（图（图7(c)所示）。这条轨所示）。这条轨迹已经是在障

14、碍物的附近，迹已经是在障碍物的附近，造成适应值下降非常大造成适应值下降非常大(图图8示示)。2223在最优化过程的下一步，粒子在最优化过程的下一步，粒子将被新的最佳位置吸引，将被新的最佳位置吸引，因此适应度函数值将在两因此适应度函数值将在两次迭代过程中就急剧减少次迭代过程中就急剧减少(如图如图7(d)所示所示)。244.结论结论 本文提出一种新的碰撞规避算法。算法采用本文提出一种新的碰撞规避算法。算法采用PSO来最优来最优化化Ferguson样条。在与其他最优化方法比较中，样条。在与其他最优化方法比较中，PSO算法算法能够克服局部最优。算法在机器人足球的应用环境中得到验能够克服局部最优。算法在机器人足球的应用环境中得到验证，比与证，比与Visibility Graph和和Potential Field算法的比算法的比较中证明了其有效性。较中证明了其有效性。