字段中机器人的搜索技术

Question

我的字段由开放网格空间和填充网格空间组成。我的机器人只能在空地上移动。它只能检测其8个相邻网格中是否存在填充的网格空间(即上、下、左、右和诊断空间)。也就是说，它不能超越8个相邻的空间。在这样的网格中，什么是最好的搜索技术？让我们说，我的目标是在网格中找到对象的no (对象是一组连通的填充空间)。

我试过以下几种方法，它们都很糟糕：

1. 保存已访问的空间列表(将初始位置取为0,0并存储所访问的空间的相对位置)。也就是说，我最好去那些没有去过的地方。
2. 首先转到最底部和最左边的点，然后开始彻底地搜索5个底部行，然后是下5个底部行，依此类推。

Answer 1

我不能完全理解你的目标，但是最常见的(非优化的)算法是A* (发音为"A - Star")。它最广泛的应用是基于网格的路径查找，包括“打开”和“关闭”节点；就像“打开”和“填充”网格空间一样。

查看http://en.wikipedia.org/wiki/A*_search_algorithm

希望这能帮上忙！

Answer 2

您没有描述为什么您认为您的解决方案“相当糟糕”，但我假设您观察到了低效的搜索行为。您可能想尝试的一种尝试是将每个空间标记为“信息的值”，也就是说，当您访问该空间时，您将发现有多少以前未被发现的相邻空间。这是你的“奖赏”。你的“成本”是你去那个特定空间的距离。然后，你将不得不找到一个最大限度的搜索策略(奖励成本)。

Answer 3

听起来像是一个部分可以观察到的马尔可夫决策过程。也许可以看看强化学习。这是萨顿和巴托的一本书的free在线版本。

我认为这个问题对于强化学习来说太难了，取得了很好的效果，而且对于经典的方法(使用逻辑)来说也太不确定了。