artificial-intelligence - 适合爬山的启发式机制

Question

以下问题是我从人工智能类(class)中找到的考试练习题。

“建议使用爬山算法解决此问题的启发式机制。(S=起点，F=终点/目标)。不允许对角线移动。”

由于很明显曼哈顿距离或欧几里得距离会将机器人发送到 (3,4) 并且不允许回溯，那么这个问题的可能解决方案(启发式机制)是什么？

编辑:为了使问题更清楚，我在黑板上标记了一些曼哈顿距离:

很明显，使用曼哈顿距离，机器人的下一步行动将在 (3,4) 处，因为它的启发式值为 2 - HC 将选择它并永远卡住。目标是通过找到合适的启发式算法，尝试永远不要走那条路。

Answer 1

我认为障碍物很热，而且热量会上升。我将一个单元格的净成本设为到 F 的曼哈顿度量距离加上热惩罚的总和。因此，存在将机器人拉向 F 的吸引力以及迫使其远离障碍物的排斥力。

有两种热罚:

1) 碰到障碍物是很不好的。查看给定单元格正下方的行中相邻单元格的 2 或 3 个单元格。为给定单元正下方的每个障碍单元添加 15，为正下方的每个对角线邻居添加 10

2) 对于未直接接触说明书的电池——热量更加分散。我将其计算为单元格下方及其相邻列中障碍物 block 平均数量的 6 倍。

下面显示了所有这些组合的结果，以及从 S 到 F 的路径:

一个关键点是，当机器人撞到第一行时，求平均值会导致机器人向左转而不是向右转。向左的未加热柱使该方向更冷。值得注意的是，所有单元格(右上角的两个单元格可能除外)是如何通过这种启发式方法被吸引到 F 的。