从系列:自主导航
布莱恩•道格拉斯
这个视频探索了一些方法,我们可以使用像二元占用网格的地图来进行运动和路径规划。我们简要介绍了什么是运动规划,以及我们如何使用图来解决这个规划问题。然后我们将介绍创建该图的两种流行方法:基于搜索的算法(如A*)和基于抽样的算法(如RRT和RRT*)。
在上个视频中,我们讲了同步定位和映射。正如它的名字所暗示的,我们最终得到了一幅以二元占据网格形式呈现的环境地图。在这个视频中,我们将探索一些使用这样的地图来进行运动规划的方法,也就是在这个环境中找到一条将机器人的起始状态和目标状态连接起来的轨迹。我们将简要介绍什么是运动规划,以及我们如何使用一个图来解决这个规划问题,然后我们将介绍创建这个图的两种流行方法——基于搜索的算法,如a *和基于采样的算法,如RRT和RRT*。我想这段视频会很好地让我们对如何用图形来规划已知环境中的轨迹有一个基本的理解。当你走出去学习这些规划方法的时候你可以以此为基础。所以,我希望你能留下来。我是Brian,欢迎来到MATLAB技术讲座。
我们想找到一条从开始姿势到目标姿势的路径。如果我们讨论的是一个沿着地面移动的机器人,可能有三种状态组成它的姿态,x和y位置和它的方向。
路径是一系列的姿态状态,平滑地连接起点和目标。确定这个顺序称为路径规划。现在,路径规划只是更大的运动规划问题的一个子集。在运动规划中,我们不仅要考虑姿态的序列,还要考虑它们的导数,比如速度、加速度、旋转速率等等。因此,通过运动规划,我们试图精确地指示机器人如何在环境中移动。对于路径规划,我们只关心它所经过的路径,而不是它加速或通过它的速度。
当然,姿势向量的大小取决于系统和环境的具体情况。如果机器人是全方位的,方向不重要,那么它可能只有两个状态,即x和y,而不是3个状态。或者,对于具有多个执行器的机械臂,姿势可能由几十种状态组成。
在这个视频中,我将使用的例子集中在路径规划和一个全向机器人,所以只有两个姿势状态。这将简化解释,希望你们能够看到这些技术可以外推到高维系统中。
好了,让我们从一个简单的地图开始它和我们在上个视频中生成的很相似。它只是一个矩形。
假设,起始姿势在这里,目标姿势在这里。最小距离解可以直接用一条直线把起点和目标连接起来,在没有障碍的情况下求解。如果机器人沿着这条路径移动,它将在尽可能短的距离内到达目标。
现在,解析解出这样的最短路径对于我们这个简单的环境来说是很简单的。这种类型的解决方案甚至可以适用于有一些障碍和限制的环境。
但对于许多问题,系统的障碍和动力学过于复杂,无法解析地生成最优解。所以,我们通过数值求解来解决这个问题。正如我在本视频开头所说的,我们将重点讨论基于图形的方法,以数值方式找到最短长度的路径。
在我们讨论任何特定的算法之前,让我向你展示一下这个简单地图的基于图的解决方案背后的总体思想。金宝搏官方网站基于图的算法的工作原理是将环境离散化——将其分解成离散的点或节点——然后只考虑这些节点就找到到目标的最短距离。
让我们以随机的方式来处理这个问题。起始位置是图中的第一个节点,它的成本为0,因为我们已经在那里了。所以我会在节点内部加一个零。然后我们可以在一个随机的方向上移动,并将一个节点放置在图中的新位置。节点之间的边是我们移动的距离,到达该节点的成本是该边的长度。现在我们在一个随机方向上再做一步,放置另一条边,这个节点的成本总共是3个单位。我们可以继续这样做,以一种随机的方式,直到我们达到目标。这种特殊随机路径的成本是10个单位。我们找到了一条可行的路径,尽管它肯定不是最短的路径。
所以,我们可以重新开始,采取一个新的随机步骤,添加一个节点,将它与一条边连接,并记录它的代价。如果我们碰巧到达了我们之前访问过的一个节点,我们可以比较到达那个节点的两条不同路径的代价,并保留最小的路径。基本上,修改了我们对到达那个节点需要多少单位的估计。
我们现在有了这个节点的图表,或者地图上的位置,以及到达每个节点的花费。我们应该认识到我们实际上不需要构建一个完全连通的图,只需要一个树,它是一个图的子集。图中可以有任意连接的节点,但在树中每个节点只有一个父节点。如果你可以用两种不同的方式到达一个节点,如果你在寻找最短路径,那么保持较长的路径是没有意义的。因此,您可以删除较长的路径的边,保持树形结构。
通过这种方式,一棵树将从机器人的位置开始,分支将冒险到其他状态,但永远不会重新组合。
现在,为了找到距离目标较短的距离,我们可以继续在环境中随机漫游,更新树,直到找到一个成本足够低的分支到达目标。这并不能保证一条最优路径,但随着节点数量的增加,它将继续接近最优路径。
当然,通过随机漫游构建树并不是最好的解决方案。这就是路径规划算法的作用所在,它们提供了更有效的方法来构建这棵树。
我想从所谓的基于搜索的方法开始,这种方法通过在有序的模式中添加节点来构建树。在实践中,实现这一点的一种方法是从一个基于网格的地图开始,就像我们拥有的占据网格,一个单元一个单元地移动,并确定成本,或者机器人为了到达那个单元所必须走的距离。这里,我说相邻移动是10,对角移动是14。这类似于我们刚才做的随机方法,除了我们有条不紊地通过每个单元,计算到达它的代价,如果是到那个节点的最短路径更新代价和树。一旦我们覆盖了网格中的每个单元,最优路径就是产生最小目标成本的单元序列。
这将产生一个最优的解决方案,至少在网格的分辨率上是最优的,但您可以看到,这将是一种计算成本很高的方法,因为它是一种检查每个可能节点的蛮力方法。为了改善这一点,研究人员在1968年提出了A*算法,使机器人Shakey能够自行决定要去哪里——这在通用移动机器人中尚属首次。这种基于搜索的方法仍然以有序的方式添加节点,但它是通过对更可能产生最优路径的节点进行优先排序,并首先在那里搜索。它通过跟踪其他启发式方法来实现,比如节点到目标的直线距离,以及节点的成本。这两个数的和就是路径的绝对最小代价。如果有一条直线射向目标,那么你可以想象,这个节点的总路径长度是48。我们已经走了10个,还剩下至少38个。因此,应该对另一个节点进行优先排序,即使它的当前代价是14,因为有可能只有28个节点可以访问总共42个节点,所以继续尝试这条路径更有意义。
通过这种方法,A*可以让我们搜索所有节点而不用把所有节点都加到树中。事实上,一旦我们到达目标我们就知道我们走的是最优路径因为其他路径的花费加距离都大于我们找到的路径。
这是对a *的快速介绍,我将制作一个动画来展示如何在障碍存在的情况下仍然有效,但坦白地说,我无法做得比Sebastian Lague (Leg-you)在他的YouTube频道上所做的更好。他在A*上的视频和动画非常棒,如果你想知道更多关于这个方法的信息,我建议你去看看。
好的,基于搜索的算法为我们提供了一种通过以某种有序模式添加节点来构建树的方法。但这类算法的一个问题是,即使是像A*这样的高效算法,随着状态空间的大小和维数的增加,它们的计算成本也会变得非常高。您可以想象网格点的数量是如何随着维度数量的增加而呈指数增长的。这会让一切变慢。因此,它们往往不用于高维状态空间,比如确定多关节机器人操纵器的路径,或者用于真正大的低维状态空间,一个可能有数百万或更多网格单元的状态空间。这就是所谓的基于采样的算法有用的地方。
为了理解基于采样的算法是如何工作的,我认为首先应该认识到,在我们的地图中,可能在大多数地图中,在需要转弯之前,路径可以沿着单一方向继续一段距离。对于A*,我们必须计算这两个点之间的每个网格单元——树中的多个节点。但是,如果我们只检查远处的节点,并且在路上没有任何障碍,那么我们就可以计算这一个节点的直线代价。这减少了节点的数量,从而减少了总计算的数量。
所以问题就变成了,我们如何选择这些稀疏节点的位置,以使我们仍然达到目标?一种方法是随机选择它们,或对它们取样,因此得名。我知道我说过随机选择节点不是构建树的最佳方法,但我们将随机选择一个节点位置,有点不同。而不是扩展路径通过某种随机游走,这可能允许的路径圆回来,需要很长时间去探索的方向目标,我们要懂得随机化,关注迅速探索随机树(RRT)和一个版本,可以达到一个名为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一样,最初的路径有点曲折。但随着我们继续添加更多节点,现有的路径将重新连接,你可以看到它们是如何随着时间的推移而变得更加精炼,变得更短更直。只要我们对结果满意,就可以停止添加节点。我们不仅有一个接近最优的路径到目标,而且我们的树生成了接近最优的路径到环境中的任何地方。至少,只要环境没有改变。这就是RRT*的力量。
再一次,这是对基于采样算法的快速介绍,在这个视频的描述中我留下了更好的信息来源。这就是我现在要做的,最简短的介绍。这里的想法,不是告诉你所有你需要知道的关于路径规划就有数十个不同的种类的RRT孤独,但是希望你有一个的树可以帮助我们通过环境规划一条路径,和一些搜索和sampling-based方法我们可以建造那棵树。
在这个视频中,我们讨论了在静态环境中规划路径。然而,通常其他物体和障碍也在环境中移动,规划算法需要对这些变化做出反应。解决这一问题的部分方法是跟踪扩展对象——这些对象足够大,传感器可以返回对其的多次检测。这就是我们下个视频要讲的内容。
如果你不想错过这个或任何其他未来科技演讲视频,不要忘记订阅这个频道。如果你想看看我的频道,控制系统讲座,我也会讲更多控制理论的话题。感谢收看,我们下次节目再见。
你也可以从以下列表中选择一个网站:
选择中国网站(中文或英文)以获得最佳网站性能。其他MathWorks国家站点没有针对您所在位置的访问进行优化。