4

三个AI新手问题：

  1. 为什么 A* 应该采用启发式算法来找到最佳路径？
  2. 如果障碍物挡在路上，平局制动技术有什么好处？
  3. 什么算法适合在有障碍物的网格上寻找路径？（像吃豆人）

对于第一个问题，让我们以Manhattan distance启发式为基础，调用是 h(x)。现在，为什么 A* 应该找到一条具有 8*h(x) + 5 的新启发式的非最优路径？（随机数）。据我在 A* 算法中的理解，将根据函数做出决定，f(x) = g(x) + h(x)所以如果我按比例放大 h，为什么最大值 \ 最小值会改变？

我读过这篇文章，他们在那里谈到了乘以一个小的系数来进行平拉制动，这在某种程度上符合我的理论，但他们坚持认为这个系数应该很小。所以我不知道该怎么想。

对于第二个问题，我尝试了解决吃豆人游戏的链接中的技术。曼哈顿距离启发式的任何变化都会导致更多节点扩展。我什至“发明”了一个新的加权方案，我更喜欢外壳上的路径——同样的事情。后来我试图取所有函数中的最大值（这也应该是可以接受的），但仍然表现不佳。我错过了什么？

第三个问题没什么可补充的。如前所述 - 我找不到比曼哈顿距离更好的东西了。

4

4 回答 4

1

1) The terse answer is, if your heuristic is not admissible, you will (possibly) get a non-optimal result. I think you knew this. For the intuition, recall the definition of an admissible heuristic: It is a heuristic which is never more pessimistic than reality. (We usually say, "it is always optimistic," since if you had a heuristic that was neither optimistic nor pessimistic, you'd basically have your answer already.) If your heuristic is pessimistic in some places, then it ends up avoiding the best choices.

As for scaling up and scaling down the heuristics as per your question, remember, you are only scaling up the heuristic part of your formula, not the sunk cost part of the formula. If you could scale them up exactly the same, you couldn't see the difference, but you can't always do that. Even in your example, the additive bit you tacked on spoils it.

2-3) It's not clear to me what you mean by "solving" pacman. If it's anything more complex than finding a shortest path to eat all the dots in an empty grid, you're getting well beyond the scope of A*, I think. Even then, A* would not be my tool of choice.

于 2012-09-03T19:36:12.233 回答
0
  1. 如果启发式不可接受，那么您的启发式将（有时）估计达到目标的成本高于可能的最低成本。因此，最终路径可能不是最优的，因为它可能没有探索由于“坏”听力而显得过于昂贵的路径。在您的情况下，使用8*h(x) + 5单调增加所有估计成本，因此虽然所有估计路径的成本都会更大，但它们仍将以相同的方式排序（例如，使用您的启发式，路径长度A为 5，路径长度为 3 BB（成本 29）仍然估计比 A（成本 45）短。
  2. 如文章所示，曼哈顿距离+第一个提到的决胜局对障碍物效果很好。您是否将估计的最大路径长度保留为 1000，或者对于您的 Pac-Man 实施，该值是否应该更高？
于 2012-09-03T10:27:56.897 回答
0

问题 3：

如果您实际上是在制作 Pac Man 游戏，您必须在其中找到每个“幽灵”的路径，您还可以使用Dijkstra 算法，以 Pac Man 的位置为目标，一次性计算出每个幽灵的最佳路径. 而且由于每个“边”（从一个单元格到下一个单元格）的成本始终相同，因此您也可以使用简单的广度优先搜索。最后，您还可以看看Collaborative Diffusion以不同的方式发送每个幽灵。

于 2012-09-03T11:56:16.780 回答
0

通常，如果您的启发式函数不可接受，您可以在更短的时间内找到“非最佳”解决方案（是一种“问题缓解”）。如果您对解决方案“最优性”没有严格限制，则可以使用不允许的启发式函数。（例如，在游戏 AI 中，您需要快速解决方案而不是最佳解决方案）。

现在是吃豆人 AI 的答案。在最初的吃豆人 AI 中，没有 A*，没有复杂的路径规划，没有网格空间导航。Iann Millington 的《人工智能游戏》一书中有一个简单的吃豆人 AI 算法，非常简单但非常有效。

  1. 一个幽灵直线移动，直到它到达一个路口。
  2. 在一个路口，他们半随机地选择了下一个方向。

停止。就这样。

对于半随机，我的意思是有两种情况：

  1. x/10次它选择一个随机方向。
  2. (10-x)/x它选择玩家方向的路线的次数（由玩家和幽灵位置之间的简单偏移量计算）。

您可以为每个幽灵选择不同的 x，从而为每个幽灵实现不同的“个性”。

如果你仍然想在吃豆人 AI 中使用 A*，我的建议是只表示连接点（每个节点都是一个连接点的图形），而不是所有的方格世界。走廊里的广场基本上是没用的。;)

于 2012-09-03T15:48:00.717 回答