人工智能中的高层规划算法

Question

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

在实践中，就目前而言，主管应该决定将盒子放在目标位置的顺序。事实上，将一个盒子放在它的目标位置可能会阻碍通往另一个目标的道路。

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

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

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

你能建议一种快速算法来计算切球位置，并且可能返回每个切球位置阻塞的目标数量吗？

Answer 1

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

具体地说，剪切顶点是其移除会增加连接组件数量的任何顶点。

在同一篇文章中还有更深一层的内容：

由于John Hopcroft和Robert Tarjan (1973) 1的缘故，计算连通无向图中的双连通分量的经典顺序算法在线性时间内运行，并且基于深度优先搜索。该算法也被概述为算法导论(第二版和第三版)的问题22-2。

在确定了双连接组件之后，应该很容易确定连接点:包含在多个双连接组件中的所有节点都是连接点。

Answer 2

您可以将该区域放入一个无向图中，其中每个节点都是地图的一个位置，如果位置彼此相邻，则两个节点是相连的。然后，您可以在图形上标记这些“切割位置”，并查看切割位置上的方框所阻挡的所有路径。