知识有限且无距离启发式的路径查找

Question

我有困难在一个简单的精英风格的游戏，我正在编写的人工智能的寻路程序。

这个游戏中的世界是由“虫洞”连接的几个“系统”，一艘船可以从它所在的系统跳到它每轮连接一次的任何系统。AI仅限于知道它应该知道的事情；它不知道哪些链接来自它从未去过的系统(尽管它可以从它所看到的系统中找到它，因为链接是双向的)。AI的其他部分根据其库存中的货物以及它所通过的系统的价值来决定船舶需要进入哪个系统。

问题是，我不知道如何处理找到目标系统路径的问题。我不能使用A*；没有办法确定与另一个系统的“距离”，而不对它进行修改。我也需要这个算法是有效的，因为它将需要运行约100次，每次球员轮流。

有人知道合适的算法吗？

Answer 1

最后，我实现了一个双向的、贪婪的广度优先搜索版本，非常适合这个目的。简单地说，我只是让程序查看每个节点的起始节点，然后是连接到的每个节点，然后是连接到的每个节点。直到找到目标节点为止。

通常，一个人会构建一个合适的路径列表并选择最短的路径，但是我尝试了一种不同的方法；我让程序并行运行两个搜索，一个从起点，一个从终点。当“从”搜索找到“to”搜索的最后一个节点时，路径被认为是找到的。

然后，它通过检查路径上的每个节点是否连接到路径中更高的节点，并删除它们之间的每个节点来优化路径。

这个古怪的算法是否真的比直接的BFS更好，还有待观察。

Answer 2

当它到达未知环境时，我通常使用一种进化算法。它并不能保证你能在很短的时间内找到最好的解决方案，但这是解决这个问题的一种方法。

Answer 3

看看部分可观测马尔可夫决策问题 (POMDP)。你应该能够用这个模型来表达你的问题。

然后，您可以使用解决这些问题的算法试图找到一个好的解决方案。请注意，求解POMDP通常非常昂贵，您可能不得不求助于近似方法。