了解 A* 搜索

Question

我在理解如何将 A* 搜索应用于实时穿越迷宫的机器人时遇到了一些困难。我了解 A* 的工作原理，但仅在 "pre-computed" 意义上（即，如果您在尝试穿越迷宫之前要计算出整条路径）。

您将如何使用它在迷宫的每一步给出 "where to next" 的答案？或者我错过了什么？非常感谢！

Answer 1

一般来说，机器人会尽可能地绘制出迷宫，然后 运行 寻路算法并遵循最终的最佳路径。如果稍后检测到迷宫的变化，机器人将从当前位置重新运行 A*。

A* 有一个更改，称为 D*-lite，当对迷宫进行小的更改时，它能够重用过去的搜索来加速未来的搜索。这是火星探测器使用的算法。