partial - 只有部分图知识的寻路算法

Question

我需要编写一个算法来引导机器人穿过“迷宫”(一个有起点、目标、空白区域和不可穿越的空间或“墙壁”的矩形网格)。它可以在任何基本方向(N、NW、W、SW、S、SE、E、NE)上移动，每次移动的成本不变。

问题是机器人不“知道” map 的布局。它只能查看它周围的 8 个空间并存储它们(它会记住它访问的每个空间的周围瓷砖)。唯一的其他输入是目标在每一步中的主要方向。

有没有我可以实现的研究算法来解决这个问题？像 Dijkstra 或 A* 这样的典型算法并不能简单地适应任务，因为我无法返回以无成本地重新访问图中的先前节点(回溯机器人的步骤以转到更好的路径将花费移动再次)，并且想不出一种方法来对 A* 进行合理的启发。

我可能可以想出一些合理的办法，但我只是想知道这是否是一个已经解决的问题，我不需要重新发明轮子:P

感谢任何提示!

Answer 1

问题尚未解决，但与许多规划问题一样，已有大量研究可用。

该领域的大部分工作都是基于 R. E. Korf 在论文“Real-time heuristic search”中的原创工作。那篇论文似乎是收费的，但是preliminary results论文中的内容以及对实时 A* 算法的讨论仍然可用。

关于带隐藏状态的离散规划(利用图的部分知识进行寻路)的近期最佳出版物来自 Sven Koenig .这包括学习实时 A* 算法的重要工作。

Koenig 的工作还包括在理论实验上对一系列算法的一些演示，这些算法比模拟中可能发生的任何事情都更具挑战性。具体见"Easy and Hard Testbeds for Real-Time Search Algorithms"由 Koenig 和 Simmons 撰写。