自主导航,第4部分:使用A*和RRT进行路径规划
从系列:自主导航
布莱恩•道格拉斯
本视频探讨了一些方法,我们可以使用地图,如二元占用网格的运动和路径规划。我们将简要介绍运动规划的含义以及如何使用图表来解决这个规划问题。然后我们介绍了创建该图的两种流行方法:基于搜索的算法(如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*,我们必须计算这两点之间的每一个网格单元也就是树中的多个节点。但是,如果我们只检查遥远的节点,并且途中没有任何障碍,那么我们就可以计算这一个节点的直线代价。这减少了节点的数量,从而减少了总计算的数量。
那么问题就变成了,我们如何选择这些稀疏节点的位置以达到目标?其中一个答案是随机选择他们,或对他们进行抽样,因此得名。我知道我说过随机选择节点不是构建树的最好方法,但是我们要选择一个随机节点的位置有点不同。比起通过某种随机游走来扩展路径,这可能会让路径绕回自己,并花很长时间去探索目标的方向,我们将更明智地使用随机化并专注于快速探索随机树(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.
我们可以继续这个过程,直到路径到达目标的某个阈值。在这一点上,我们有了一个可行的路径,尽管可能不是一个最优的路径,因为这个方法在它的方式趋向于z字形。但我们确实找到了一个解决方案,而且重要的是,这个方案使用的节点可能比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就有许多变体,但希望你能够理解树是如何帮助我们在环境中规划路径的,以及我们可以通过基于搜索和基于抽样的方法来构建这棵树。
在这个视频中,我们讨论了如何规划通过静态环境的路径。然而,通常其他物体和障碍也在环境中移动,规划算法需要对这些变化做出反应。解决这个问题的部分方法是跟踪扩展对象——这些对象足够大,以至于传感器返回多次探测到它。这就是我们下个视频要讲的内容。
如果你不想错过这个视频或其他未来的科技谈话视频,不要忘记订阅这个频道。你们可以看看我的频道,控制系统讲座,我也会在那里介绍更多的控制理论主题。感谢收看,我们下期见。
相关产品2022世界杯八强谁会赢?
了解更多
您也可以从以下列表中选择网站:
如何获得最佳的网站性能
选择中国网站(中文或英文)以获得最佳的网站表现。其他MathWorks国家网站没有针对从您的位置访问进行优化。