人工智能高级规划的算法

Question

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

在实践中，目前监督者应该决定将箱子放在目标位置的顺序。实际上，可能会发生将一个箱子放在其目标位置会阻碍另一个目标的路径的情况。

我们解决这个问题的第一个方法是尝试考虑“切削位置”。如果某个位置将可走空间分成两个子集，在其中一个子集中我们有代理，而在另一个子集中我们有一个或多个目标，则该位置就是一个切割位置。例如，考虑以下关卡，“x”是代理，“A”和“B”是箱子，“a”和“b”是各自的目标位置:

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

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

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

- papafe

Answer 1

你所谓的网格单词的切割位置在一般图中被称为割点或关节点。根据维基百科：（Cut vertex），具体来说，割点是任何一个其移除会增加连接组件数量的顶点。接着在同一篇文章中有这样的描述：经典的连通无向图双连通分量计算的顺序算法由约翰·霍普克罗夫特和罗伯特·塔杨（1973）[1]开发，运行时间为线性，并且基于深度优先搜索。这个算法也被概述为《算法导论》（第2版和第3版）的问题22-2。确定了双连通分量后，很容易确定关节点：所有包含在多个双连通分量中的节点都是关节点。

- blubb

Answer 2

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

- masotann