运动规划之搜索算法：前端规划、后端轨迹生成到状态求解( 二 ) _算法

文章插图
在配置空间中规划¹²³

机器人在C-space中被表示为一个点，例如，位置（在R3中的一个点），姿态（在 (3)中的一个点），等等???
障碍物需要在配置空间中表示（在运动规划之前的一次性工作），称为配置空间障碍物，或C-障碍???
C-space = (C-障碍) ∪ (C-自由)???
路径规划是在C-自由中找到从起点qstart到目标点qgoal的路径?[10]¹?

文章插图
在工作空间中

机器人有形状和大?。??，难以进行运动规划）
在配置空间：C-space中
机器人是一个点（即，易于进行运动规划）?
在进行运动规划之前，障碍物在C-space中表示?[10]
在C-space中表示障碍物可能非常复杂。因此，在实践中使用近似（但更保守）的表示。

如果我们保守地将机器人建模为半径为 _ 的球，那么可以通过在所有方向上膨胀障碍物 _ 来构造C-space1 。这是一种常见的机器人碰撞检测方法，通过确保球体中心在膨胀地图的自由空间中来实现碰撞评估1 。然而，这种保守的方法并未考虑到机器人的形状和大小。
构建地图：在路径规划中，构建搜索地图是一个关键步骤。这通常涉及到将实际环境抽象为一个图（Graph），其中节点（Nodes）代表可能的位置，边（Edges）代表从一个位置到另一个位置的移动。以下是一个详细的例子：
假设我们有一个机器人需要在一个室内环境中导航。这个环境可以是一个房间，有一些障碍物，比如桌子和椅子。

定义节点（Nodes）：首先，我们需要确定节点的位置。在这个例子中，我们可以将房间的每一个可达的位置定义为一个节点。例如，我们可以创建一个网格（Grid），每一个网格单元都是一个节点。
定义边（Edges）：然后，我们需要确定边。如果机器人可以直接从一个节点移动到另一个节点，那么这两个节点之间就有一条边。在我们的例子中，如果两个网格单元相邻，并且没有障碍物阻挡，那么这两个网格单元（即节点）之间就有一条边。
定义权重（Weights）：最后，我们需要为每一条边定义一个权重。权重可以根据实际的移动成本来确定。例如，如果从一个节点到另一个节点的距离更远，或者路径上有斜坡，那么这条边的权重就应该更大。

地图种类：栅格地图（Grid Map）则是把环境划分成一系列栅格，在数学视角下是由边联结起来的结点的集合，一个基于图块拼接的地图可以看成是一个栅格图，每个图块(tile)是一个结点，图块之间的连接关系如短线。
概率图（Cost Map）如果在栅格图的基础上，每一栅格给定一个可能值，表示该栅格被占据的概率，则该图为概率图。
特征地图（Feature Map）特征地图用有关的几何特征（如点、直线、面）表示环境。常见于vSLAM（视觉SLAM）技术中。它一般通过如GPS、UWB以及摄像头配合稀疏方式的vSLAM算法产生，优点是相对数据存储量和运算量比较小，多见于最早的SLAM算法中。
拓扑地图（Topological Map）是指地图学中一种统计地图, 一种保持点与线相对位置关系正确而不一定保持图形形状与面积、距离、方向正确的抽象地图。包括有有向图和无向图（字面意思）。