来自系列:自主导航
布莱恩•道格拉斯
此视频探讨了我们可以使用像二进制占用网格的地图以用于运动和路径规划的一些方法。我们简要介绍了哪些运动计划手段以及我们如何使用图表来解决这个规划问题。然后,我们通过两个流行的方法来创建该图:基于搜索的算法,如*和基于采样的算法,如RRT和RRT *。
在上个视频中,我们讨论了同步定位和映射。正如它的名字所暗示的那样,我们最终以二元网格的形式绘制出了一幅环境地图。在这个视频中,我们将探索一些可以使用这样的地图来进行运动规划的方法,也就是在这个环境中找到一个轨迹将机器人的起始状态和某个目标状态连接起来。我们将简要介绍什么是运动规划,以及我们如何使用图形来解决这个规划问题,然后我们将介绍两种流行的创建图形的方法-基于搜索的算法,如a *和基于采样的算法,如RRT和RRT*。我认为这个视频将很好地为我们建立一个基础的理解如何使用图形来规划通过已知环境的轨迹。当你走出去学习更多关于这些规划方法的知识时,你可以以此为基础。所以,我希望你能坚持下去。我是Brian,欢迎来到MATLAB技术讲座。
我们想从一个起始姿势找到一个路径到目标姿势。如果我们谈论沿着地面移动的机器人,可能有三个态度构成其姿势,x和y位置及其方向。
路径是一系列平稳连接起点和目标的姿态状态。确定这个序列称为路径规划。现在,路径规划只是更大的运动规划问题的一个子集。在运动规划中,我们不仅关注姿态的序列,还关注它们的导数,比如速度,加速度,旋转速率等等。所以,通过运动规划,我们试图精确地指示机器人如何在环境中移动。在规划路径时,我们只关心它所走的路径,而不是它加速或移动得有多快。
当然,姿势矢量的大小取决于系统和环境的细节。如果机器人是全点和方向无关紧要,它可能只有两个,x和y可能只是两个,x和y。或者,在具有多个执行器的机器人手臂的情况下,姿势可能由数十种状态组成。
对于此视频,我将使用专注于路径规划的示例,并为全方位的机器人使用,所以只有两个姿势状态。这将简化解释,希望您能够看到这些技术可以推断为更高的维度系统。
好了,让我们从一个简单的地图开始它和上个视频中生成的类似。它只是一个矩形。
假设,起始姿势在这里,目标姿势在这里。一个最小距离的解决方案可以直接通过一条直线连接出发和目标,只要没有障碍在路上。如果机器人沿着这条路径移动,它将在尽可能短的距离内到达目标。
现在,像这样解析求解最短路径对于我们这个简单的环境来说是很简单的。这种解决方案甚至也适用于有一些障碍和限制的环境。
但对于许多问题来说,系统的障碍和动态太复杂,无法在分析上产生最佳解决方案。因此,我们通过数字地解决问题来解决它。正如我在这个视频开始时所说,我们将专注于基于图形的方法,以便在数字上找到具有最短长度的路径。
在我们进入任何特定的算法之前,请让我向您展示基于图形的解决方案背后的一般想法,使用这一简单的地图。万博 尤文图斯基于图形的算法通过离散环境 - 将其分解为离散点或节点 - 然后在考虑这些节点的考虑到目标的最短距离。
让我们以随机的方式接近这个问题。起始位置是我们图中的第一个节点,并且由于我们已经存在,它的成本为0。所以我将在节点内部放置零点。然后我们可以随机移动,并在新位置处的图表中放置一个节点。节点之间的边缘是我们旅行的距离,到达此节点的成本是该边缘的长度。现在我们在随机方向上拍摄另一台步骤,放置另一台边缘,这个节点的成本总共3个单位。在我们进入目标之前,我们可以继续这样做。这个特定随机路径的成本是10个单位。我们发现一条有效的道路,即使它绝对不是最短的路径。
因此,我们可以重新开始,采用新的随机步骤,添加节点并用边缘连接并记录其成本。如果我们碰巧到达我们之前访问过的节点,我们可以比较我们采取的两个不同路径之间的成本,以便到达该节点并保持最小的路径。基本上,修改我们对该节点所需的单位的估计。
我们现在有了这个节点图,或者地图上的位置,以及到达每个节点需要多少成本。我们应该意识到,我们实际上不需要建立一个完全连通的图,只需要一个树,它是一个图的子集。一个图可以以您想要的方式连接节点,但在树中每个节点只有一个父节点。如果你可以通过两种不同的方式到达一个节点,那么如果你在寻找最短的路径,那么保持更长的路径是没有意义的。所以,对于较长的路径,你可以去掉这条边,保持树状结构。
通过这种方式,一棵树将从机器人的位置开始,分支会冒出其他州,但从不重组。
现在,要找到较短的目标距离,我们可以继续随机徘徊环境,更新树,直到我们找到一个分支,以获得足够低的成本。这不会保证最佳路径,但随着节点的数量进入无限远,它将继续接近最佳。
当然,通过随机漫步构建一棵树并不是最好的解决方案。这就是路径规划算法的作用,它们提供了更有效的方法来构建这棵树。
我想从所谓的基于搜索的方法开始,这些方法以有序的模式添加节点来构建树。在实践中实现这一点的一种方法是从一个基于网格的地图开始,就像我们拥有的占用网格,然后一个单元一个单元地去确定成本,或者机器人为了到达那个单元必须走的距离。这里,邻步是10对角线是14。这类似于我们刚才做的随机方法,除了我们有条不紊地遍历每个单元格,计算到达它的代价,如果这是到那个节点的最短路径就更新代价和树。一旦我们覆盖了网格中的每一个单元格,最优路径就是在目标下产生最小成本的单元格序列。
这将产生最佳解决方案,至少在网格分辨率上最佳,但您可以看到这将是计算方式,因为它是检查每个可能节点的蛮力方法。为了改善这一点,研究提出了1968年的A *算法,使机器人能够确定其在其自己的位置的能力 - 首先用于通用移动机器人。这种基于搜索的方法仍然以有序方式添加节点,但它通过优先考虑更有可能产生最佳路径的节点,并首先搜索。除了节点的成本之外,它还通过跟踪从节点到目标的直线距离等一些其他启发式轨道来实现这一点。这两个数字的总和是路径的绝对最低成本。如果有一条直线射击目标,那么你可以想象总路径的长度如何表示,这个节点将是48.我们已经走了10次,我们至少有38个左转去。因此,即使其当前成本为14,也应该优先考虑该另一个节点,因为只有28个才能获得28个,总共有42次,因此继续尝试这条路径更有意义。
因此,通过这种方式,A *允许我们以一种方式通过节点搜索,这将使我们成为目标而不必将每个节点添加到我们的树中。事实上,一旦我们实现了目标,我们知道我们拍摄了最佳路径,因为每隔一个路径都有一个成本加上我们找到的路径的成本加距离。
现在,这是一个关于a *的快速介绍,我将制作一个动画来展示这在存在障碍时是如何有效运行的,但老实说,我无法做得比Sebastian lagage (Leg-you)在他的YouTube频道上已经拥有的更好。他关于A*的视频和动画是惊人的,如果你想知道更多关于这个方法,我建议你去看看。
好的,所以基于搜索的算法给我们通过在某种有序模式中添加节点来构建一棵树。但是这些类型的算法的一个问题,即使是高效的算法,也是它们变得非常昂贵,因为状态空间的尺寸和尺寸增加。您可以想象网格点的数量如何以尺寸增加呈指数级增长。这可以减慢一切。因此,它们倾向于不用于高尺寸状态空间,例如确定多关节机器人操纵器的路径,或者对于真正大的低维状态空间,其可能具有数百万或更多的网格单元。这是所谓的基于样品的算法是有用的。
为了理解基于采样的算法是如何工作的,我认为首先要意识到在我们的地图中(可能是大多数地图),在需要转弯之前,一条路径在某些区域中可以沿着单一方向持续一段距离。对于A*,我们必须计算这两个点之间的每个网格单元格,也就是树中的多个节点。但是,如果我们只检查遥远的节点,没有任何障碍,那么我们就可以计算这一个节点的直线代价。这减少了节点的数量,从而减少了总计算数。
所以问题就变成了,我们如何选择这些稀疏节点的位置才能达到目标?一个答案是随机选择它们,或抽样,因此得名。我知道我说过,随机选择节点并不是构建树的最佳方法,但我们将随机选择节点位置,稍有不同。而不是扩展路径通过某种随机游走,这可能允许的路径圆回来,需要很长时间去探索的方向目标,我们要懂得随机化,关注迅速探索随机树(RRT)和一个版本,可以达到一个名为RRT *的最优解。
让我们进入基本RRT算法的工作原理。从起始节点中,我们需要在树中放置一个新节点。通过随机选择状态空间中的任何位置来完成此操作。一旦我们有这个随机节点,我们希望将其连接到最近的节点到它的树中。其中,由于我们刚刚开始是第一个节点。但我们不想将其放置得太远,因为越过障碍物或者在错误方向上的障碍物的障碍物的可能性更大,并且具有更长的边缘。因此,我们指定了新节点可以远离最近节点的最大距离。
现在,快速放在一边。如果随机节点比最大距离更近,那么我们将在那里放置新节点。此外,如果最近的节点与我们想要放置新节点之间的障碍,那么完全忽略该树的障碍物,树上没有添加到树中,我们继续前进。这使树上试图穿过任何墙壁或其他障碍物。
好的,让我们继续前进。我们随机选择一个新节点并找到最接近的节点。同样,这恰好是起始节点。所以我们树上已经有两条路径,两者都冒了进入国家空间的不同部分。一个新的随机节点,我们再次将其连接到最近的,它正在将一条路径延长到开放空间中。这就是为什么这种算法称为快速探索随机树的原因。当有大型未开发的地区时,就像我们一样,在该区域中选择随机节点有很大的机会。这具有添加新节点在导致路径快速进入未开发的区域的地方,从而快速探索。并且在与目标相反的方向上的随机节点不会影响到目标的路径,因为不同的节点最接近。通过这种方式,一条路径总是迅速实现目标,其他路径迅速进入状态空间的其他开放区域。 And then later on, as the unexplored area starts to fill up, the random node selection tends to just fill the tree out with more branches.
我们可以继续这个过程,直到路径到达目标的某个阈值。在这一点上,我们有一个可行的路径,尽管可能不是最优路径,因为这个方法往往是曲折的。但我们确实找到了一个解决方案,而且更重要的是,这个方案使用的节点比a *所需的节点要少得多,因为节点之间的间距可以更大。同样,我们将其设置为最大连接距离。
RRT可以在您只是寻找有效路径的情况下工作,而不是必然是最短的距离。只要启动和目标节点即可,就可以保证该方法查找路径,随着样本的数量接近无穷大 - 在大多数情况下,在大多数情况下都有更小的有限数量的样本。
现在,如果我们想要一个更接近最优的解,我们必须在RRT算法中添加一些额外的步骤,我们得到RRT*。对于RRT*,节点选择过程完全相同。我们选择一个随机节点,找到最近的邻居,如果没有障碍,我们将一个新节点放置在随机节点或最大连接距离-哪个较小。区别在于我们将该节点连接到现有树的位置。我们不需要把它和最近的节点连接起来。相反,我们检查某些指定搜索半径内的其他节点,并确定是否可以重新连接这些本地节点,以保持树结构的同时最小化总路径长度。这里,我把它连接到另一个节点因为这样会产生一条更短的路径回到起始点。
让我们看RRT *与稍微复杂的环境一起工作。在这里,我正在使用MATLAB从导航工具框中执行此可视化和RRT *功能。一开始,您可以看到它正在迅速探索环境。只有几十个节点这样做。到目前为止,它与RRT不同,但让我暂停它。此下一个节点将显示在此处。如果这是RRT,它将将该节点连接到这一点,因为它是最近的。但观看会发生什么。将出现该节点,它在这里一直连接,因为这是一个较短的路径返回开始。它重新连接了搜索半径内的一些其他节点。 So RRT* is always trying to shorten the paths. Let’s continue.
在这里,它达到了目标,就像RRT一样,一开始就是一个曲折的Zaggy。但随着我们继续添加更多节点,并且重新连接现有路径,您可以看到它们如何随着时间的推移而改进,越来越短。每当我们满意的结果时,我们都可以停止添加节点。我们不仅具有目标的近乎最佳路径,而且我们的树已经在环境中任何地方的最佳路径中产生了附近。至少,只要环境没有改变。这是RRT *的力量。
现在,这是对基于采样的算法的超级快速介绍,并且我在该视频的描述中留下了更好的信息来源。这就是我现在要留下它的地方,只需最简短的介绍。这里的想法是不是告诉你关于路径规划所需的一切,因为只有RRT的数十个变化只是rrt,但希望你有一种树木如何帮助我们通过环境计划一条路径,有些基于搜索和基于抽样的方式,我们可以接近构建该树。
在这个视频中,我们讨论了在静态环境中规划路径。然而,通常其他物体和障碍也会在环境中移动,规划算法需要对这些变化做出反应。解决这个问题的方法之一是跟踪扩展对象——这些对象足够大,传感器可以多次探测到它。这就是我们下个视频要讲的。
如果你不想错过这个视频或者其他未来的科技谈话视频,不要忘记订阅这个频道。你们可以去看看我的频道,控制系统讲座,我也讲了更多的控制理论主题。感谢收看,我们下期再见。
您还可以从以下列表中选择一个网站:
请选择表现最佳的中国网站(中文或英文)。MathWorks的其他国家网站并没有针对您所在位置的访问进行优化。