探索算法

Question

我已经大幅度编辑了这个问题，使它更容易理解。

在一个任意维度和任意位置的障碍物中，我有一个代理探索这个环境，但视野范围有限（障碍物不会阻挡视线）。它可以朝着东南西北四个方向移动，每次移动一格，图是无权重的（每一步的代价为1）。下面链接的地图表示代理人（黄色小伙子）在规划瞬间对环境的当前信念。当代理正在规划时，仿真中时间不会流逝。

http://imagizer.imageshack.us/a/img913/9274/qRsazT.jpg

我应该使用哪种探索算法来最大化效用的成本效率，考虑到允许重新访问单元格？每个单元格都具有效用值。理想情况下，我会寻求最大化所有已看到（而非访问过）单元格的效用之和与路径长度的比值，尽管如果任何适当的算法过于复杂，则已看到的单元格数就足够了。路径长度有一个最大值，但通常在数百或更高。 （我的代理使用的实际测试环境至少4倍以上，尽管从理论上讲，可以设置无限制的维度，并相应地增加最大路径长度）

我认为BFS和DFS是棘手的，给定缺乏合适启发式的A*不是最优的，Dijkstra不适合生成单个不间断的路径。你能想到任何算法吗？此外，我需要帮助循环检测，因为允许重新访问是我第一次这样做。

我考虑的一种方法是将地图缩小为跨度树，除了将其定义为连接所有单元格的树之外，它被定义为可以看到所有单元格的树。我的方法将导致以下结果：

http://imagizer.imageshack.us/a/img910/3050/HGu40d.jpg

在生成的树中，代理可以从一个节点移动到任何相邻的节点，这些节点在交叉口处距离为0-1圈。这是我目前的思考范围。使用此树生成的解决方案可能不是最优的，但它至少应该是近似最优的，并且算法处理的单元格要少得多，因此如果这会使算法更容易处理，那么我认为这是一个可以接受的折衷方案。然而，我仍然困惑于如何生成路径。

- thegreatjedi

---

为什么不使用基于已查看单元格数量的启发式A*算法？ - nkcode

@nkcode 我认为使用已看到的单元格数量作为A*算法的启发式效用/成本度量是不好的，可能无法得到最优解。 - thegreatjedi

环境似乎是有限的；这是真的吗？效用值是否非负？如果是这样，仅优化效用似乎没有意义，而是优化效用与移动的比率；这是一个合适的方法吗？ - Codor

如果我正确理解问题，任务是“看到”整个世界，在每个单元格中您都可以看到世界的一部分。您希望选择最少的单元格来尽可能多地覆盖世界。那么这是最大覆盖问题的一个版本，它是NP完全问题。但是有一些近似算法可以解决它。http://zh.wikipedia.org/wiki/最大覆盖问题 - Krycke

@amit视力> 0，实际上有什么区别吗？ - thegreatjedi

Answer 1

您的问题与标准的强化学习(Grid World)问题非常相似，我会将其形式化为标准的马尔可夫决策过程(Markov Decision Process, MDP)并使用任何强化学习算法来解决它。

形式化如下：

状态s：您的NxM个离散网格。

行动a：UP、DOWN、LEFT、RIGHT。

奖励r：代理人可以从目标单元格s'中看到的单元格的价值之和。即，r(s,a,s') = sum(value(seen(s'))。

转移函数：如果s'没有超出边界或是黑色单元格，则P(s'|s,a)=1，否则为0。

由于您对平均奖励感兴趣，折扣因子为1，并且您需要通过步数来归一化累积奖励。您也提到每一步的成本为1，因此您可以在每个时间步骤时从即时奖励r中减去1，但这不会增加任何东西，因为您已经按步数取平均了。

由于问题是离散的，策略可以是简单的softmax（或Gibbs）分布。

作为解决算法，您可以使用Q学习，它保证在提供足够数量的样本时提供最优解。但是，如果您的网格太大（而且您说没有限制），我建议使用策略搜索算法，如策略梯度或相对熵（尽管它们仅保证收敛到局部最优解）。您可以在互联网上基本上找到有关Q学习的所有信息。关于策略搜索的最近调查，请参见this。

这些方法的酷之处在于，它们将探索编码到策略中（例如，softmax策略中的温度，高斯分布中的方差），并尝试最大化由MDP描述的累积长期奖励。因此，通常您会使用高探索性（例如，完全随机策略）初始化策略，并通过试错使算法变得确定性并收敛到最优策略（但有时随机策略也是最优的）。 所有RL算法之间的主要区别在于它们如何在每次迭代中执行策略更新以及如何管理探索-开发权衡（我应该探索多少VS我应该利用我已经拥有的信息）。

根据Demplo的建议，您也可以使用遗传算法（GA），但它们通常速度较慢，需要更多的调整（精英主义、交叉、突变等）。

我还尝试了一些策略搜索算法来解决您的问题，它们似乎效果不错，尽管我随机初始化了网格，并不知道确切的最优解。如果您提供一些额外的细节（测试网格、最大步数以及初始位置是固定还是随机的），我可以更精确地测试它们。

- Simon