机器人探索算法

我正在尝试为机器人设计一种算法，试图找到位于未知位置的旗帜，该旗帜位于一个包含障碍物的世界中。机器人的任务是夺取旗帜并将其带到他的基地（代表他的起始位置）。机器人在每一步只能看到有限的邻域（他事先不知道世界是什么样子），但他有无限的内存来存储已经访问过的单元格。

我正在寻找有关如何有效地做到这一点的任何建议。尤其是第一部分；即到达旗帜。

简单的广度优先搜索/深度优先搜索就可以工作，尽管速度很慢。请务必防止机器人多次检查具有相同平方的路径，因为这将导致这些算法在标准情况下运行更长时间，并且在无法到达标志的情况下无限期地运行。

A* 是更优雅的方法，特别是如果您知道旗帜相对于您自己的位置。维基百科 http://en.wikipedia.org/wiki/A%2a_search_algorithm和往常一样，解释得很好。使用的经典启发式是到目的地的配员距离（假设没有障碍物的移动次数）。

这些算法对于回程很有用 - 而不是“找到标志”部分。

Edit:这些方法涉及创建代表地图上方块的对象，以及创建要击中的“路径”或一系列方块（或要采取的步骤）。一旦你建立了一个代表你的正方形的框架，使用哪种搜索的问题就变得不再那么艰巨了。

这个类需要能够获取相邻方块的列表并知道它是否可遍历。

考虑到您没有所有信息，请尝试将未探索的图块视为可遍历的，如果发现它们不可遍历，则重新计算。

Edit:至于在未知区域寻找未知物体……

你可以使用类似的东西质押的算法 http://en.wikipedia.org/wiki/Maze_solving_algorithm#Pledge_algorithm直到您找到空间的边界，并记录您所走的所有信息。然后使用您最喜欢的漂移/寻路算法查看所有看不见的方块。如果在途中的任何一点，您看到旗帜，请停止您正在做的事情并使用您最喜欢的寻路算法回家。