从系列:自主导航
布莱恩•道格拉斯
这个视频探索了一些方法,我们可以使用像二元占用网格的地图来进行运动和路径规划。我们简要介绍了什么是运动规划,以及我们如何使用图来解决这个规划问题。然后我们将介绍创建该图的两种流行方法:基于搜索的算法(如A*)和基于抽样的算法(如RRT和RRT*)。
在上个视频中,我们讲了同步定位和映射。正如它的名字所暗示的,我们最终得到了一幅以二元占据网格形式呈现的环境地图。在这个视频中,我们将探索一些使用这样的地图来进行运动规划的方法,也就是在这个环境中找到一条将机器人的起始状态和目标状态连接起来的轨迹。我们将简要介绍什么是运动规划,以及我们如何使用一个图来解决这个规划问题,然后我们将介绍创建这个图的两种流行方法——基于搜索的算法,如a *和基于采样的算法,如RRT和RRT*。我想这段视频会很好地让我们对如何用图形来规划已知环境中的轨迹有一个基本的理解。当你走出去学习这些规划方法的时候你可以以此为基础。所以,我希望你能留下来。我是Brian,欢迎来到MATLAB技术讲座。
我们想找到一条从开始姿势到目标姿势的路径。如果我们讨论的是一个沿着地面移动的机器人,可能有三种状态组成它的姿态,x和y位置和它的方向。
路径是姿势指出平滑连接的起点和目标的序列。确定这个序列称为路径规划。现在,路径规划仅仅是个较大的运动规划问题的一个子集。随着运动的规划,我们不只是关心姿态的顺序,而且它们的衍生物,如速度,加速度,转速等。所以,用运动规划,我们正试图决定如何准确通过环境的机器人移动。随着路径规划,我们只是关心的路径,它需要,而不是它通过它加速或移动的速度有多快。
当然,姿势向量的大小取决于系统和环境的具体情况。不是三个状态,它可以是两个,x和y如果机器人是全向的,方向无关紧要。或者,在一个有多个驱动器的机械手臂的情况下,这个姿势可能包含几十种状态。
对于此视频,我将使用专注于路径规划的示例,并为全方位的机器人使用,所以只有两个姿势状态。这将简化解释,希望您能够看到这些技术可以推断为更高的维度系统。
好了,让我们从一个简单的地图开始它和我们在上个视频中生成的很相似。它只是一个矩形。
假设,起始姿势在这里,目标姿势在这里。最小距离解可以直接用一条直线把起点和目标连接起来,在没有障碍的情况下求解。如果机器人沿着这条路径移动,它将在尽可能短的距离内到达目标。
现在,解析求解最短路径这样是平凡的我们简单的环境。而这种类型的解决方案甚至可以与一些障碍和制约因素以及环境中工作。
但对于许多问题,系统的障碍和动力学过于复杂,无法通过解析得到最优解。所以,我们通过数值解法来解决这个问题。正如我在本视频开始时所说的,我们将关注基于图的方法来数值计算出最短长度的路径。
在我们进入任何特定的算法之前,请让我向您展示基于图形的解决方案背后的一般想法,使用这一简单的地图。万博 尤文图斯基于图形的算法通过离散环境 - 将其分解为离散点或节点 - 然后在考虑这些节点的考虑到目标的最短距离。
让我们用随机的方法来处理这个问题。起始位置是图中的第一个节点它的代价是0因为我们已经在那里了。所以我在结点里面写一个0。然后我们可以向随机方向移动,并在图中新位置放置一个节点。节点之间的边就是我们走了多远到达这个节点的代价就是这条边的长度。现在我们往随机方向再走一步,放置另一条边,这个节点的成本总共是3单位。我们可以继续这样做,以一种随机漫步的方式,直到我们到达目标。这条随机路径的成本是10单位。我们找到了一条可行的路径,尽管它肯定不是最短路径。
因此,我们可以重新开始,采用新的随机步骤,添加节点并用边缘连接并记录其成本。如果我们碰巧到达我们之前访问过的节点,我们可以比较我们采取的两个不同路径之间的成本,以便到达该节点并保持最小的路径。基本上,修改我们对该节点所需的单位的估计。
我们现在有了这个节点的图表,或者地图上的位置,以及到达每个节点的花费。我们应该认识到我们实际上不需要构建一个完全连通的图,只需要一个树,它是一个图的子集。图中可以有任意连接的节点,但在树中每个节点只有一个父节点。如果你可以用两种不同的方式到达一个节点,如果你在寻找最短路径,那么保持较长的路径是没有意义的。因此,您可以删除较长的路径的边,保持树形结构。
通过这种方式,树将从机器人所在的位置开始,树枝将冒险到其他状态,但永远不会重新组合。
现在,为了找到离目标更近的距离,我们可以继续在环境中随机游荡,更新树,直到我们找到一个成本足够低的到达目标的分支。这并不能保证路径是最优的,但当节点数趋于无穷时,路径将继续趋近最优。
当然,通过随机漫游构建树并不是最好的解决方案。这就是路径规划算法的作用所在,它们提供了更有效的方法来构建这棵树。
我想从所谓的基于搜索的方法开始,这种方法通过在有序的模式中添加节点来构建树。在实践中,实现这一点的一种方法是从一个基于网格的地图开始,就像我们拥有的占据网格,一个单元一个单元地移动,并确定成本,或者机器人为了到达那个单元所必须走的距离。这里,我说相邻移动是10,对角移动是14。这类似于我们刚才做的随机方法,除了我们有条不紊地通过每个单元,计算到达它的代价,如果是到那个节点的最短路径更新代价和树。一旦我们覆盖了网格中的每个单元,最优路径就是产生最小目标成本的单元序列。
这将产生一个最优的解决方案,至少在网格的分辨率上是最优的,但您可以看到,这将是一种计算成本很高的方法,因为它是一种检查每个可能节点的蛮力方法。为了改善这一点,研究人员在1968年提出了A*算法,使机器人Shakey能够自行决定要去哪里——这在通用移动机器人中尚属首次。这种基于搜索的方法仍然以有序的方式添加节点,但它是通过对更可能产生最优路径的节点进行优先排序,并首先在那里搜索。它通过跟踪其他启发式方法来实现,比如节点到目标的直线距离,以及节点的成本。这两个数的和就是路径的绝对最小代价。如果有一条直线射向目标,那么你可以想象,这个节点的总路径长度是48。我们已经走了10个,还剩下至少38个。因此,应该对另一个节点进行优先排序,即使它的当前代价是14,因为有可能只有28个节点可以访问总共42个节点,所以继续尝试这条路径更有意义。
因此,通过这种方式,A *允许我们以一种方式通过节点搜索,这将使我们成为目标而不必将每个节点添加到我们的树中。事实上,一旦我们实现了目标,我们知道我们拍摄了最佳路径,因为每隔一个路径都有一个成本加上我们找到的路径的成本加距离。
这是对a *的快速介绍,我将制作一个动画来展示如何在障碍存在的情况下仍然有效,但坦白地说,我无法做得比Sebastian Lague (Leg-you)在他的YouTube频道上所做的更好。他在A*上的视频和动画非常棒,如果你想知道更多关于这个方法的信息,我建议你去看看。
基于搜索的算法为我们提供了一种建立树的方法通过在某种有序的模式中添加节点。但这类算法的一个问题是,即使是像A*这样高效的算法,随着状态空间的大小和维度的增加,它们的计算成本会变得非常昂贵。您可以想象网格点的数量是如何随着维数的增加而呈指数增长的。这会让一切慢下来。因此,它们往往不用于高维状态空间,比如为多关节机器人操作器确定路径,或用于非常大的低维状态空间,一个可能有数百万或更多网格单元的空间。这就是所谓的基于抽样的算法的用处所在。
要了解基于采样的算法是如何工作的,我觉得首先它有助于认识到,在我们的地图,甚至可能是大多数的地图,也有部分地方的路径可以继续在一个方向一段距离之前,它需要转弯。随着A *我们要计算这两个点之间的每一个网格单元 - 如此多节点树。然而,如果我们只检查了遥远的节点,有没有在途中的任何障碍,那么我们就可以计算仅这一个节点的直线成本。这减少了节点的数量,并且因此总的计算的数量。
于是问题就来了,我们该如何选择这些稀疏节点的位置,使我们仍达到目标?而一个答案是随机选择它们,或品尝它们,因此得名。现在,我知道我说的是随机选择的节点不是打造出来的树,最好的办法,但我们要选择一个随机的节点位置略有不同。Rather than extending the path through some kind of random walk, which could allow the path to circle back on itself and take a long time to explore in the direction of the goal, we’re going to be smarter about randomization and focus on rapidly exploring random trees (RRT) and a version of it that can approach an optimal solution called 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.
我们可以继续做这个过程,直到路径的目标一定阈值内到达。在这一点上,我们有一个可行的道路,尽管可能不会,因为这种方法中最佳的一种趋于曲折,因为它使得它的方式。但是,我们没有找到一个解决方案,更重要的一个解决方案,可能的用途远远更少的节点从1995年起的节点也有必要对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国家站点没有针对您所在位置的访问进行优化。