algorithm - 探索算法

Question

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

给定一个具有任意尺寸和任意数量障碍物的任意位置的环境，我有一个代理在有限的视线范围内探索环境(障碍物不会阻挡视线)。它可以在 NSEW 的四个主要方向上移动，一次移动一个单元格，并且图形未加权(每一步的成本为 1)。下面的链接是一张 map ，代表代理人(黄色小人)在规划时对环境的当前信念。代理进行规划时，时间不会在模拟中流逝。

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

在允许重新访问单元格的情况下，我可以使用什么探索算法来最大化效用的成本效率？每个单元格都有一个效用值。理想情况下，我会寻求最大化所有 SEEN(未访问)单元格的效用总和除以路径长度，尽管如果这对于任何合适的算法来说太复杂，那么看到的单元格数量就足够了。存在最大路径长度，但通常为数百或更长。 (在我的agent上实际使用的测试环境至少大了4倍，虽然理论上可以设置的维度没有上限，因此最大路径长度会相应增加)

我认为 BFS 和 DFS 是棘手的，A* 是非最优的，因为缺乏合适的启发式算法，而 Dijkstra 不适合生成单一的不间断路径。有没有你能想到的算法？此外，我需要循环检测方面的帮助，因为我以前从未这样做过，因为允许重新访问是我第一次这样做。

我考虑过的一种方法是将 map 缩减为生成树，只不过不是将其定义为连接所有单元格的树，而是将其定义为可以看到所有单元格的树。我的方法会导致以下结果:

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

在生成的树中，代理可以从一个节点转到任何相邻节点，这些节点在交叉路口处为 0-1 转弯。这就是我现在的想法。使用这棵树生成的解决方案可能不是最优的，但它至少应该接近最优，算法处理的单元格少得多，所以如果这会使算法更容易处理，那么我想这是可以接受的权衡。然而，我仍然在思考如何为此生成路径。

Answer 1

您的问题与典型的强化学习 (RL) 问题非常相似，即网格世界。我会将其形式化为标准的马尔可夫决策过程 (MDP)，并使用任何 RL 算法来解决它。

形式化将是:

• 状态 s:您的 NxM 离散网格。
• Action a:上、下、左、右。
• Reward r:智能体从目标单元格s'可以看到的单元格的值，即r(s,a,s') = 总和(值(看到(s'))。
• 转换函数:P(s' | s, a) = 1如果s'没有越界或黑格，0 否则。

由于您对平均奖励感兴趣，因此折扣因子为 1 并且您必须通过步数对累积奖励进行归一化。您还说过每一步的成本为 1，因此您可以在每个时间步将立即奖励 r 减去 1，但这不会增加任何内容，因为您已经对步数进行了平均。

由于问题是离散的，因此策略可以是简单的 softmax(或 Gibbs)分布。

作为求解算法，您可以使用 Q 学习，它可以保证在提供足够数量的样本的情况下解决方案的最优性。但是，如果您的网格太大(并且您说没有限制)，我会建议使用策略搜索算法，例如策略梯度或相对熵(尽管它们只能保证收敛到局部最优)。您基本上可以在 Internet 上随处找到有关 Q-learning 的内容。对于最近的政策搜索调查，我建议 this .

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

正如 Demplo 所建议的，您也可以使用遗传算法 (GA)，但它们通常速度较慢并且需要更多调整(精英主义、交叉、变异...)。

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