大量编辑此问题以使其更容易理解 .
鉴于任意尺寸的环境和任意数量障碍物的任意定位，我有一个探测环境的探测器，视野范围有限（障碍物不会阻挡视线） . 它可以在NSEW的四个主要方向上移动，一次一个单元格，并且图形未加权（每个步骤的成本为1） . 下面链接的是一张 Map ，代表了代理商（黄人）当前对规划时的环境信念 . 当代理正在计划时，时间不会通过模拟 .
http://imagizer.imageshack.us/a/img913/9274/qRsazT.jpg
考虑到允许重新访问单元格，我可以使用哪种探索算法来最大化效用的成本效益？每个单元格都包含实用值 . 理想情况下，我会寻求最大化SEEN（未访问）所有单元的效用之和除以路径长度，尽管如果对于任何合适的算法来说太复杂，那么看到的单元数就足够了 . 存在最大路径长度，但通常为数百或更高 . （我的代理上使用的实际测试环境至少要大4倍，尽管理论上可以设置的维度没有上限，因此最大路径长度会相应增加）
我认为BFS和DFS是难以处理的，A *由于缺乏合适的启发式而不是最优的，而Dijkstra不适合生成单一的完整路径 . 有没有你能想到的算法？另外，我需要有关循环检测的帮助，因为我之前从未这样做，因为允许重新访问是我的第一次 .
我考虑过的一种方法是将映射缩减为生成树，除了不将其定义为连接所有单元的树，而是将其定义为可以查看所有单元的树 . 我的方法将产生以下结果：
http://imagizer.imageshack.us/a/img910/3050/HGu40d.jpg
在结果树中，代理可以从节点到达交叉点处0-1转的任何相邻节点 . 就我现在的想法而言 . 使用这棵树生成的解决方案可能不是最优的，但它至少应该接近最优，而算法处理的单元更少，所以如果这会使算法更容易处理，那么我想这是可以接受的交易 . 我仍然在考虑如何为此生成一条路径 .
1 回答
您的问题非常类似于规范的强化学习（RL）问题，网格世界 . 我将其正式化为标准马尔可夫决策过程（MDP）并使用任何RL算法来解决它 .
形式化将是：
States
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（或Gibbs）分布 .
作为求解算法，您可以使用Q学习，这可以保证解决方案的最优性，并提供足够数量的样本 . 但是，如果您的网格太大（并且您说没有限制），我会建议使用策略搜索算法，例如策略梯度或相对熵（尽管它们只保证收敛到局部最优） . 你可以在互联网上的任何地方找到关于Q-learning的东西 . 对于最近的政策检索调查，我建议this .
关于这些方法的一个很酷的事情是它们对策略中的探索进行编码（例如，softmax策略中的温度，高斯分布的方差），并且将尝试最大化MDP所描述的累积长期奖励 . 因此，通常您通过高度探索（例如，完整的随机策略）初始化您的策略，并且通过反复试验，该算法将使其具有确定性并收敛到最优策略（然而，有时候随机策略也是最优的） . 所有RL算法之间的主要区别在于它们如何在每次迭代中执行策略更新并管理权衡探索 - 利用（我应该探索多少VS我应该利用已有的信息） .
正如Demplo所建议的那样，您也可以使用遗传算法（GA），但它们通常较慢且需要更多调整（精英主义，交叉，突变......） .
我也尝试了一些关于你的问题的策略搜索算法，它们似乎运行良好，虽然我随机初始化了网格，但不知道确切的最佳解决方案 . 如果您提供一些额外的细节（测试网格，最大步数以及初始位置是固定的还是随机的），我可以更精确地测试它们 .