探索算法

Question

大量编辑这个问题，使其更容易理解。

给定一个具有任意尺寸和任意数量障碍物的任意定位的环境，我有一个代理人以有限范围的视线探测环境（障碍物不会阻挡视线）。它可以在NSEW的四个基本方向上移动，一次一个单元格，并且图形未加权（每个步骤的成本为1）。下面链接的是一张地图，表示代理人（黄家伙）在计划时刻对环境的当前信念。在代理计划时，时间不会通过模拟。

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

我可以使用哪些探索算法最大限度地考虑到重新审视细胞被允许公用事业的成本效益，？每个单元格都有一个实用值。理想情况下，我会试图最大化SEEN（未访问）的所有单元的效用总和除以路径长度，但如果对于任何合适的算法来说这太复杂，那么所看到的单元数就足够了。有一个最大路径长度，但它通常在数百或更高。 （我的代理上使用的实际测试环境至少大4倍，尽管理论上可以设置的尺寸没有上限，并且最大路径长度因此会相应增加）

我认为BFS和DFS为难以处理，由于缺乏合适的启发式算法，A *是非最优的，而迪杰斯特拉不适合产生一条不间断的路径。有什么算法可以想到吗？此外，我需要帮助进行循环检测，因为我之前从未这样做过，因为允许重访是我第一次。

我考虑过的一种方法是将映射减少为生成树，但不是将其定义为连接所有单元的树，而是将其定义为可以查看所有单元的树。我的做法会导致如下：

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

在结果树，代理可以从一个节点到是0-1转走在十字路口的任何相邻节点。就我现在的想法而言，这就是我的想法。使用这棵树生成的解决方案可能不是最优的，但它应该至少接近最优，而算法处理的细胞要少得多，所以如果这会使算法更容易处理，那么我认为这是可接受的交易。然而，我仍然想着如何为此产生一条路径。

Answer 1

您的问题与标准的强化学习（RL）问题非常相似，即网格世界。我将它定义为一个标准的马尔可夫决策过程（MDP）并使用任何RL算法来解决它。

的形式化是：

• 国s：你NxM离散网格。
• 操作a：UP, DOWN, LEFT, RIGHT。
• 奖励r：代理可以从目的地小区s'看到的小区的值，即r(s,a,s') = sum(value(seen(s'))。
• 转换函数：P(s' | s, a) = 1如果s'不是超出边界或黑色单元，0否则。

既然您对平均回报感兴趣，折扣系数为1，您必须将累计回报按步数归一化。你还说每一步都花费了一个，所以你可以在每个时间步骤减去1到立即奖励r，但这不会增加任何东西，因为你已经平均的步数。

由于问题是离散的策略可以是一个简单的SOFTMAX（或吉布斯）分布。

作为解决算法可以使用Q学习，保证了解决方案的最优化提供足够数量的样本。然而，如果你的网格太大（并且你说没有限制），我会建议策略搜索算法，比如策略梯度或相对熵（尽管它们只保证局部最优化）。你可以在互联网上的任何地方找到关于Q-learning的东西。对于最近的政策搜索调查，我建议this。

这些方法很酷的一点是，它们将策略中的探索（例如softmax策略中的温度，高斯分布中的变化）编码并尝试最大化累积长期奖励MDP。因此，通常你通过高度探索来初始化你的策略（例如，一个完整的随机策略），并且通过反复试验，算法将使其确定并收敛到最优策略（然而，有时候随机策略是最优的）。 所有RL算法之间的主要区别在于，他们如何在每次迭代中执行策略更新，并管理权衡探索和利用（我应该多少探索VS我应该利用已有信息多少）。

正如Demplo建议，你也可以使用遗传算法（GA），但它们通常比较慢，需要更多的调整（精英，交叉，变异......）。

我自己也尝试在你的问题的一些政策搜索算法和他们似乎运作良好，但我随机初始化网格，不知道确切的最佳解决方案。如果您提供一些额外的细节（测试网格，最大步数以及初始位置是固定的还是随机的），我可以更精确地测试它们。