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

Question

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

1. 要求机器人必须通过设定的路径点，例如必须通过50个点。
2. 计划的路径要求 U 形转弯次数最少。

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

在此处输入图像描述

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

标签： algorithmmobilepathrobotplanning

Answer 1

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

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

这归结为每个顶点的3*3*4=36状态，但是我们实际上可以做得更好。我们永远不会0在该方向连续转弯时左转或右转，而且我们实际上并不关心我们一直直行多长时间，因此我们可以将其修复为0. 所以现在我们有(2 + 2 + 1) * 4=20状态。

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

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

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

• G2L* 或 G2R* 中顶点的传入边权重为 1
• 所有其他边的权重为 0

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

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

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

如果你对 U 形转弯有不同的定义，那么你需要对你的状态进行不同的编码，但结果可能是相似的——你为每个顶点创建多个“变体”来表示这个状态，然后添加非完成 U 形转弯的边缘的权重为零。