仅具有部分图知识的寻路算法
我需要编写一种算法来导航机器人穿过“迷宫”（带有起点、目标、空白空间和不可跨越的空间或“墙壁”的矩形网格）。它可以沿任何基本方向（N、NW、W、SW、S、SE、E、NE）移动，每次移动的成本恒定。
问题是机器人不“知道”地图的布局。它只能查看其周围的 8 个空间并存储它们（它会记住它访问的每个空间的周围瓷砖）。唯一的其他输入是每一步目标的基本方向。
有没有我可以实现的研究算法来解决这个问题？像 Dijkstra 或 A* 这样的典型节点并不能很好地适应该任务，因为我无法在没有成本的情况下返回重新访问图中的先前节点（回溯机器人的步骤以走上更好的路径会花费移动时间）再次），并且无法想出一种方法来为 A* 制定合理的启发式。
我可能可以想出一些合理的东西，但我只是想知道这是否是一个已经解决的问题，我不需要重新发明轮子：P
感谢您的任何提示！
I need to program an algorithm to navigate a robot through a "maze" (a rectangular grid with a starting point, a goal, empty spaces and uncrossable spaces or "walls"). It can move in any cardinal direction (N, NW, W, SW, S, SE, E, NE) with constant cost per move.
The problem is that the robot doesn't "know" the layout of the map. It can only view it's 8 surrounding spaces and store them (it memorizes the surrounding tiles of every space it visits). The only other input is the cardinal direction in which the goal is on every move.
Is there any researched algorithm that I could implement to solve this problem? The typical ones like Dijkstra's or A* aren't trivialy adapted to the task, as I can't go back to revisit previous nodes in the graph without cost (retracing the steps of the robot to go to a better path would cost the moves again), and can't think of a way to make a reasonable heuristic for A*.
I probably could come up with something reasonable, but I just wanted to know if this was an already solved problem, and I need not reinvent the wheel :P
Thanks for any tips!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
这个问题还没有得到解决，但就像许多规划问题一样，已经有大量的研究可供使用。
该领域的大部分工作都是基于RE Korf在论文“Real-time heuristic search”中的原创工作。那篇论文似乎是付费的，但初步结果论文以及对实时 A* 算法的讨论仍然可用。
关于具有隐藏状态的离散规划（使用图形的部分知识进行路径查找）的最新最佳出版物由 Sven Koenig 撰写。这包括学习实时 A* 算法的重要工作。
Koenig 的工作还包括一系列理论实验算法的演示，这些算法比模拟中可能发生的任何事情都更具挑战性。特别请参阅 Koenig 的 “实时搜索算法的简单和困难测试平台”和西蒙斯。
The problem isn't solved, but like with many planning problems, there is a large amount of research already available.
Most of the work in this area is based on the original work of R. E. Korf in the paper "Real-time heuristic search". That paper seems to be paywalled, but the preliminary results from the paper, along with a discussion of the Real-Time A* algorithm are still available.
The best recent publications on discrete planning with hidden state (path-finding with partial knowledge of the graph) are by Sven Koenig. This includes the significant work on the Learning Real-Time A* algorithm.
Koenig's work also includes some demonstrations of a range of algorithms on theoretical experiments that are far more challenging that anything that would be likely to occur in a simulation. See in particular "Easy and Hard Testbeds for Real-Time Search Algorithms" by Koenig and Simmons.