用于人工智能中高级计划的算法

Question

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

实际上，目前，主管应该决定箱子放置在目标位置的顺序。事实上，将箱子放入其目标位置可能会阻碍另一个目标的实现。

我们解决这个问题的第一种方法是试图考虑“裁员”。如果将可行走空间分为两个子集，其中一个是我们的代理人，另一个是我们的一个或多个目标，那么某个职位就是一个裁员职位。例如，考虑下面的水平，其中“x”是代理，“A”和“B”是框和“a”和“b”是各自的目标的位置：

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

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

你能否提出一个快速算法来计算切割位置，这可能会返回每个切割位置阻挡的目标数量？

Answer 1

你所谓的切割位置为网格词叫割点或一般图关节点。来自Wikipedia：

具体地说，切割顶点是其去除增加了连接成分数量的任何顶点。

而同样制品中的位进一步向下：

用于计算在连接的无向图由于约翰·霍普克洛夫特和罗伯特·塔扬（1973）双连通部件经典顺序算法[1]在运行线性时间，并基于深度优先搜索。该算法也概述为算法简介（第2版和第3版）的问题22-2。

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

Answer 2

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