在A*算法中加权启发式函数

Question

三个人工智能初学者问题：

1. 为什么A*算法中的启发式函数必须是可接受的才能找到最优路径？
2. 如果有障碍物，那么打结技术有什么用呢？
3. 什么算法适用于在带有障碍物的网格上找到路径？（如吃豆人）

对于第一个问题，以曼哈顿距离启发式函数为基础，称之为h(x)。现在为什么A*要使用一个新的启发式函数（如8*h(x)+5）来找到非最优路径呢？就我所知，在A*算法中，决策将根据函数f(x)=g(x)+h(x)进行，因此如果我放大h，为什么最大/最小值会改变呢？

我已经阅读了这篇文章，他们谈到了通过乘以小因子来进行打结技巧，这在我的理论中也是如此，但他们坚持认为因子应该很小。所以我不知道该怎么想。

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

对于第三个问题没有什么可补充的了。如上所述-我找不到比曼哈顿距离更好的方法。

- Ramzi Khahil

---

我有一个作业任务是为吃豆人制作人工智能，但是我必须在几个小时内提交它，我不确定我是否能够及时得到答案...所以我确实很感兴趣，但我只会根据答案进行快速测试并离开。 - Ramzi Khahil

A是两个重叠启发式的算法。Djikstra更喜欢靠近起点的节点，而最佳优先搜索则更喜欢靠近目标的节点。A像Djikstra一样（向所有方向扩展），直到遇到障碍，然后开始沿着直线向目标扩展。如果将距离目标的成本乘以，A就会开始专注于快速解决方案。在2秒钟内，我的A遍历了2500个节点，通过加权以支持目标（1.1倍），它遍历了1750000个节点。速度提高了约700倍（代价是准确性）。 - Aarowaim

Answer 1

1) 简短的回答是，如果你的启发式不可接受，你可能会得到一个非最优结果。我想你已经知道了这一点。对于直觉，回想一下可接受启发式的定义：它是一种从不比现实更悲观的启发式。（我们通常说，“它总是乐观的”，因为如果你有一种既不乐观也不悲观的启发式，你基本上已经得到了答案。）如果你的启发式在某些地方过于悲观，那么它最终会避免最佳选择。

至于根据你的问题扩大和缩小启发式，记住，你只是扩大公式中的启发式部分，而不是公式中的沉没成本部分。如果你能够完全相同地扩大它们，你就看不出区别了，但你并不总是能做到这一点。即使在你的例子中，你添加的附加位也破坏了它。

2-3) 我不清楚你所说的“解决”吃豆人的意思。如果它比在空网格中找到吃掉所有点的最短路径更复杂，我认为你已经远远超出了A*的范围。即使是这样，A*也不会是我的首选工具。

- Novak

Answer 2

1. 如果启发式函数不是可接受的，则启发式函数有时会高估到达目标的成本，使得最终路径可能是非最优的，因为它可能没有探索那些由于“坏”启发式函数而显得过于昂贵的路径。在您的情况下，使用 8*h(x) + 5 可以单调地增加所有估计成本，因此虽然所有估计路径的成本都将更高，但它们仍将以相同的方式排序（例如，路径 A 的长度曾经是 5，路径 B 的长度曾经是 3，使用您的启发式函数 B（成本为 29）仍将被估计为比 A（成本为 45）更短）。
2. 如 文章 所示，曼哈顿距离加上第一个提到的打破平局的方法对于障碍物很有效。您是否将预估的最大路径长度保留在 1000，或者应该将此值提高以适用于您的 Pac-Man 实现？

- Sicco

---

我已经计算出了 p，其中1是一步的代价，(height*width - width/3*(height-1)) 是预期的最大路径。实际上最大路径比这个少，但我认为这已经足够好了。有什么问题吗？ - Ramzi Khahil

你只试过这个 p 吗？否则我建议多尝试一下，可以按照你描述的计算方法，再尝试更小的值（例如将其乘以0.1、0.01、0.001等）。 - Sicco

此外，如果我们特别谈论吃豆人游戏，那么整个地形都充满了障碍物，没有任何“开放区域”可供使用。因此，吃豆人的迷宫实际上使这些启发式算法变得毫无价值 - 因为它们适用于一些“重”的和一些“轻”的单元格的开放地形，而不是绕过障碍物。 - Ramzi Khahil

我刚试了一下这个代码： problem.goal = foodNode ; w = problem.walls.width ; h = problem.walls.height ; p.append( min( min(w-foodNode [0], foodNode [0])/w, min(h-foodNode [1], foodNode [1])/h) ) ; p.append( 1/(hw - w/3(h-1)) * 0.001 ) ; distance = manhattanHeuristic(position, problem) * (1+ max(p)) ; 结果和只使用 manhattanHeuristic 得到的结果相同 - 我在每行之间加了 ;，希望这样有些意义 - 这是 Python 代码。 - Ramzi Khahil

Answer 3

问题3：

如果您真的在制作吃豆人游戏，在其中必须找到每个"幽灵"的路径，您还可以使用迪杰斯特拉算法，以Pac Man的位置为目标，并一次性计算每个幽灵的最佳路径。由于每个“边缘”的成本（从一个单元到下一个单元）始终相同，因此您也可以使用简单的广度优先搜索。最后，您还可以查看协同扩散，以便为每个幽灵发送不同的路线。

- tobias_k

Answer 4

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

现在回答Pac-Man AI的问题。原始的Pac-Man AI中没有A*，没有复杂的路径规划，也没有网格空间导航。在Artificial Intelligence for Games by Iann Millington一书中有一个非常简单但非常有效的Pac-Man AI算法。

1.鬼魂沿直线移动，直到到达交叉口。 2.在交叉口，它们会随机选择下一个移动方向。

就是这样。

对于“半随机”，我指的是有两种情况：

1. 它会随机选择方向 x/10 次。
2. 它会在剩下的 (10-x)/x 次中选择朝向玩家的路线（通过计算玩家和幽灵位置之间的简单偏移量来确定）。

您可以为每个幽灵选择不同的 x，以实现它们各自不同的“个性”。

如果您仍然想使用 A* 算法来实现 Pac-Man AI，我的建议是仅表示交叉口（一个图形，其中每个节点都是交叉口），而不是整个方格网格世界。走廊中的方格基本上是无用的。 ;)

- Davide Aversa

---

这不是Pac-Man中幽灵使用的算法。每个幽灵都有不同的算法。Pac-Man档案详细介绍了幽灵如何在迷宫中导航：http://home.comcast.net/~jpittman2/pacman/pacmandossier.html - Matt Greer

哦。我参考了Iann Millington的《游戏人工智能》一书，认为它是指原始算法。然而... :) 谢谢你提供的信息。我会修正我的回答。 :) - Davide Aversa