人工智能高级规划算法

Question

我目前正在从事一个人工智能项目，其中代理需要将箱子从其原始位置推拉到某个目标位置。然后该项目将扩展到包括多个代理，因此我们有一个主管负责创建“高级”目标，而代理负责实际实现。

在实践中，目前，主管应该决定将盒子放在目标位置的顺序。事实上，将一个盒子放在目标位置可能会阻挡通向另一个目标的路径。

我们解决这个问题的第一个方法是尝试考虑“切入位置”。如果某个位置将可步行空间划分为两个子集，则该位置是一个切割位置，其中一个子集有代理，另一个子集有一个或多个目标。例如，考虑以下级别，其中“x”是代理，“A”和“B”是框，“a”和“b”是各自的目标位置:

+++++++++++++++++++++++++++++++++++++++++
x                        a             b+
+++++   +++++++++++++++++++++++++++++++++
    +AB +
    +++++ 

在这种情况下，目标“a”的位置是一个切割位置，因为如果一个盒子放在那里，那么智能体将无法到达目标“b”。

您能否建议一种快速算法来计算切割位置，并且可能会返回每个切割位置阻挡的目标数量？

Answer 1

您所说的网格词的切割位置在一般图形中称为切割顶点 或接合点。来自 Wikipedia :

Specifically, a cut vertex is any vertex whose removal increases the number of connected components.

在同一篇文章的更下方:

The classic sequential algorithm for computing biconnected components in a connected undirected graph due to John Hopcroft and Robert Tarjan (1973) [1] runs in linear time, and is based on depth-first search. This algorithm is also outlined as Problem 22-2 of Introduction to Algorithms (both 2nd and 3rd editions).

确定了双连通分量后，确定关节点应该很容易:包含在多个双连通分量中的所有节点都是关节点。