algorithm - 最佳 A* 启发式 : multiple targets and agents

Question

我有一个问题，由一个有墙、目标和代理的方形迷宫组成。代理只能水平/垂直移动。在每一步，每个智能体从 1 个方格移动。

我必须实现 A* 算法来解决问题，但我很难找到一个很好的启发式算法来解决它。

每次我阅读有关最佳启发式方法的文档时，它总是涉及一个只有一个代理和多个目标的迷宫，但与多个代理无关。

我尝试试验的启发式方法如下:

对于每个目标，我采用距代理最近的 Manathan 距离并对结果求和。

在这种情况下，如果还剩下两个目标和三个智能体，则只求和两个智能体，不考虑最远的智能体，总和将小于三个智能体和三个目标的情况。

根据可接受启发式的定义，我怀疑我的启发式是否可接受。

我觉得这是合理的，因为它考虑了每一种食物，而不仅仅是一种，但我认为我遗漏了一个重要的观点。

有人可以考虑一些技巧或有趣的方法吗？

Answer 1

A* 仅适用于一个代理。您需要为每个代理运行一个单独的搜索实例。

如果有很多代理而只有几个目标，并且你的图是无向的，你可以从目标搜索到代理而不是(假设你只需要最近的代理)然后反向结果。

如果您需要对很多很多 代理进行路径查找，您应该使用不同的算法。有很多选择；此处要查找的关键字是“群体寻路”、“人群流动”和“群体”。通常，您将为整个 map 创建一个矢量场，并将其与某种回避算法相结合。