运动规划与RRT算法,第1部分:运动规划算法介绍
从系列中:运动规划实践使用RRT算法
运动规划让机器人或车辆规划从起点到目标状态的无障碍路径。学习一些流行的运动规划算法,它们是如何工作的,以及它们在不同场景中的适用性。
了解以下算法如何参考自动驾驶汽车和仓库机器人等合适的应用程序进行全局和局部路径规划-混合A*,概率路线图(PRM),快速探索随机树(RRT), RRT*和轨迹最优Frenet。
用MATLAB学习各种函数®和导航工具箱™来定制机器人的状态空间,并根据应用程序实现不同的运动模型。
大家好。欢迎来到MATLAB运动规划实践课程。我是Mihir Acharya,网络自主导航的产品经理。和我一起的是YJ Lim, MathWorks机器人和自主系统的产品经理。对于任何类型的自主机器人,运动规划都是经济中必不可少的一部分。它有助于找到将机器人从源位置移动到目标位置的有效配置序列。在本节课中,我们将学习路径和运动规划算法,以及如何使用MATLAB和导航工具箱快速实现这些算法,并为您的机器人找到最短的无障碍路径。
我们将看到两个应用示例,其中我将介绍移动机器人的路径规划示例,VJ将介绍如何对机器人机械手进行同样的操作。在典型的自主机器人工作流程中,感知模块提供关于机器人周围环境的信息。这包括机器人应该避免撞到的障碍物。我们从定位算法中得到机器人在每个运动或状态下的位置。当机器人需要从初始位置自主导航到目标位置时,就需要进行运动规划。
运动规划算法,帮助规划到目标的最短无障碍路径。使用MATLAB和Simulink,您可以使用RRT或混合A*等算法进行全局路径规划。如果路上有未知障碍,你可以使用轨迹生成进行局部重新规划。
此外,我们可以将运动规划分为三类,包括先前称为行为规划的高级决策。然而,我们也可以将运动规划算法的类型分为基于搜索的和基于采样的。在本节课中,我们将简要介绍这些算法,以及如何使用MATLAB和导航工具箱中的规划基础设施实现RRT算法。但我们先来看看MATLAB中可用的一些规划算法。
一旦我们得到了环境的地图,就有两种方法来解决路径规划问题。一种方法是将地图划分为网格单元。另一种方法是在图中随机抽样图节点。有几种基于网格的算法,如A*是最受欢迎的算法之一。我想每个运动规划爱好者都对A*算法有所了解。在MATLAB中有一个传统的a *实现,具有可定制的代价和启发式。
A*只适用于驱动或完整机器人。但如果我们想要像汽车一样的运动呢?我们有一个a的变体,它允许我们这样做,它是杂化a。混合A*算法与传统的A*算法在搜索空间是xy的区分方面是相似的。但与传统的A*不同,混合A*将车辆的连续3D状态或我们所说的运动原语与每个网格单元相关联。这些运动原语使用状态验证器检查地图中的碰撞,并生成平滑的无障碍路径。
与传统的A*不同,混合动力A*适用于具有非完整约束的车辆和类车机器人,例如自动驾驶汽车。它还保证了运动学的可行性,并考虑了微分约束。这意味着你可以考虑飞行器的方向和速度。你可以把车辆的方向和这个图表一起作为输入。我们可以看到如何根据不同的目标方向得到不同的可驱动部件。用MATLAB和Simulink就可以了
实现混合A*与多个参数来调整,如运动原语的长度,最小转弯半径,向前向后运动等。
基于网格的算法不适用于各种自由度较高或地图尺寸非常大的应用。存储大型地图的网格信息在计算上非常昂贵。这就是基于抽样的规划算法很有用的地方。一种常用的基于抽样的算法是PRM或概率路线图,它是地图中不同可能部分的网络图。在MATLAB的实现中,我们首先导入使用slam创建的二进制占用映射。然后我们可以根据机器人的大小来扩大地图,以避免与墙壁相撞。然后我们在自由空间中随机采样节点,MATLAB中的PRM影响计划对象将它们连接起来以创建路线图。
一旦构建了路线图,我们就可以在地图上从给定的起始位置到给定的目标位置查询零件。我们可以在同一路线图中多次查询不同的起始和目标位置。您可以自定义节点数量和连接距离,以适应地图的复杂性。MATLAB中的PRM实现适用于各种类型的完整移动机器人应用程序,在这些应用程序中,您希望更改开始和前进的位置,而不需要再次学习整个地图。例如,没有未知障碍的静态仓库环境就是一个很好的例子。
但在其他很多情况下,机器人是不完整的。也就是说,它具有微分约束,也可能涉及具有未知障碍的高维状态空间。这就引出了RRT或快速探索随机树算法。RRT在阶段空间中使用随机采样的状态或节点创建树。RRT算法是为高效搜索非凸高维空间而设计的。RRT是以一种快速缩短树中随机选择节点的期望距离的方式增量构造的。
让我们简单地看看基于抽样的算法是如何工作的。我们首先定义状态空间。初始树T的起始点是其中一个节点。为了以规划算法或规划程序能够理解的方式表示映射,我们以状态空间的形式表示它。机器人的状态是它的位置和方向。状态空间是许多可能的机器人状态的集合。状态空间表示的一个例子是SE2状态空间,其中机器人可以在二维地图中移动,每个状态包含三个变量xy和theta。
现在我们在状态空间X中随机抽取一个状态X,然后找到一个离X最近的节点,这个节点已经存在于树中。这个随机X可以在状态空间的任何地方。所以我们需要另一个节点X new在X random和X附近来展开树。重复这个过程,直到达到目标X。每次我们采样一个新的模式节点,比如X new,我们也会检查节点X random和节点X new之间的碰撞。使用MATLAB,您可以使用运动原语或运动模型,如引脚芯片或杜宾疤痕来生成从一个节点到另一个节点的局部运动。
RRTs特别适用于涉及障碍和微分约束的路径规划问题。也适用于高自由度的机器人比如机器人操作手但它们同样适用于移动机器人的路径规划。RRT算法给出了一个有效路径,但不一定是最短路径,这就把我们带到了RRT*。RRT*是RRT的一个变体,或者我可以说它是RRT的优化版本。RRT*在展开树的方式上与RRT相似。但它以一种方式重新连接树,在给定的半径下,总是试图找到从随机采样的节点回到树的起点的更短的路径。这使得RRT*给出了一个最优解,并使它对于高维问题更加可行。
虽然RRT*找到节点数量较少的最短路径,但与RRT相反,它不适用于非完整车辆。RRT能够处理差分约束。因此,这取决于你的应用程序,找出哪种算法更适合。在进一步的会议中,VJ还将涵盖双向RRT,并解释如何为机器人机械手工作。现在让我们看看MATLAB和导航工具箱中可用的规划基础设施,用于基于抽样的算法(如RRT)。我们首先加载环境的占用地图,机器人可以在其中检查碰撞。
占用地图指定了地图中每个单元被障碍物占用或单元有空闲空间的概率。然后,我们使用建筑物状态空间表示形式之一(如SE2、SE3)或Dubin车辆的状态空间表示状态空间。杜宾状态空间是支持杜宾运动模型的一种SE2形式的状态空间。这种状态空间允许机器人在杜宾的汽车中移动,这使得它适合使用阿克曼转向的汽车运动。运动模型可作为部分段,如杜宾的连接。在我们完成了状态空间中的状态随机采样之后,下一步是规划器需要一个状态验证器。
为了理解一个状态的有效性或两个状态之间的移动,规划器需要一个状态验证器。例如,如果机器人在给定状态和运动过程中没有与任何障碍物碰撞,则机器人状态被认为是有效的。任何障碍物与机器人状态的碰撞都将使其成为无效状态。规划者将避免在零件中添加这样的状态。导航工具箱为2-D和3-D占用地图以及成本地图提供了内置的状态验证器。
最后我们定义规划器,它找到路径。所有内置的状态空间都可以根据您的应用程序进行定制。我们将在示例中看到如何定制它们。但是您也可以使用MATLAB和导航工具箱构建自己的自定义路径规划接口。使用这个规划基础设施,只需几行代码就可以在MATLAB中实现RRT算法。这里我们看到规划器RRT的语法,它将状态空间SE2或任何其他状态空间和占用映射的状态验证器作为输入。然后它返回路径状态和解信息作为输出。现在我将切换到MATLAB,我们将看看如何使用RRT算法为移动机器人规划路径的运输示例。
您也可以从以下列表中选择一个网站:
如何获得最佳的网站性能
选择中国站点(中文或英文)以获得最佳站点性能。其他MathWorks国家站点没有针对您所在位置的访问进行优化。