类车移动机器人路径规划中如何引入最小掉头次数和强制交叉约束？

Question

我在开发类CAR移动机器人的路径规划问题时，遇到了以下问题：

1. 要求机器人必须经过设定的路径点，例如必须经过50个点。
2. 规划的路径要求掉头次数最少。

初步设计采用A*或PRM算法。

如何将上述两个约束引入到算法中？这样的设计可行吗？

Answer 1

您的答案取决于您如何定义掉头。如果您将其定义为连续 2 个“左”或“右”转弯，那么是的，您可以相当容易地解决这个问题。取出你的节点，并形成一个有向图 G0。暂时保留边缘 - 我们稍后会添加它们，现在我们只需要顶点本身。现在，让我们重复复制此图，为我们关心的每个可能的“状态”创建每个顶点的实例。为了检测掉头，我们需要三条状态信息：

• 我们之前转向哪个方向（左/右/直）
• 我们朝该方向连续转了多少圈（0/1/2）
• 我们现在面向什么方向（北/南/东/西）

这可以归结为每个顶点的

3*3*4

=

36

状态，但是我们实际上可以做得更好。我们永远不会在该方向上连续转

0

来左转或右转，而且我们实际上并不关心我们直行了多长时间，因此我们可以将其修复为

0

。所以现在我们有

(2 + 2 + 1) * 4

=

20

状态。

仍然不理想，但我们可以做进一步的简化。同样，这取决于您对 U 形转弯的定义，但如果我们将闭合 1x1 循环视为单个 U 形转弯（或者，如果禁止重新访问节点），我们可以将 2-左和 2-右状态视为等效的“U 形转弯”状态，无论方向如何，在退出该顶点时都会重置转弯计数。这导致需要考虑

(1 + 1 + 1 + 1) * 4

=

16

状态。

现在，正如我提到的，我们将为每个顶点可能处于的每种可能状态创建一个实例，并且出于组织目的，我们将这些顶点集中到子图中，其中每个子图包含相同状态的顶点。用符号表示，我们可以说子图 G1LN 包含刚刚向左转一次并且现在在其当前节点上“面向”北的节点。

现在我们需要在每个子图内的这些顶点之间以及子图之间添加有向边。请注意，唯一在其自身顶点之间具有边的子图应该是 G0SN/G0SS/G0SE/G0SW 图。所有边的权重应如下：

G2L* 或 G2R* 中顶点的传入边的权重为 1

• 所有其他边的权重均为 0
我们快完成了。我们的图表现在完全编码了当前 U 形转弯状态，并且我们路径的权重等于我们进行的 U 形转弯数量。我们只需要插入一个虚拟源和汇节点，并将它们连接到我们的图表即可开始。对于源，将向外的边连接到 G0S* 子图中的每个顶点。对于接收器，连接每个子图中每个顶点的传入边。

现在，只需开始从源到汇的搜索，最小化路径权重，但仍然需要每个路径点至少访问一个顶点。第一条路径将是掉头最少的路径。

旁白：这可以用多重图来表示，每个节点包含多个边，只要您在搜索中显式存储方向/转弯状态即可。为了便于理解，我在这里以简化的形式呈现。

如果您对 U 形转弯有不同的定义，那么您需要以不同的方式编码您的状态，但结果可能会相似 - 您为每个顶点创建多个“变体”来表示此状态，然后添加非- 完成掉头的边缘重量为零。