the*_*edi 5 algorithm search artificial-intelligence agent
大量编辑此问题以使其更容易理解.
鉴于任意尺寸的环境和任意数量障碍物的任意定位,我有一个探测环境的探测器,视野范围有限(障碍物不会阻挡视线).它可以在NSEW的四个主要方向上移动,一次一个单元格,并且图形未加权(每个步骤的成本为1).下面链接的是一张地图,代表了代理商(黄人)当前对规划时的环境信念.当代理正在计划时,时间不会通过模拟.
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转的任何相邻节点.就我现在的想法而言.使用这棵树生成的解决方案可能不是最优的,但它至少应该接近最优,而算法处理的单元更少,所以如果这会使算法更容易处理,那么我想这是可以接受的交易.我仍然在考虑如何为此生成一条路径.
您的问题与典型的强化学习 (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在每个时间步的直接奖励中减去 1，但这不会增加任何内容，因为您已经按步数进行了平均。
由于问题是离散的，因此策略可以是简单的 softmax（或吉布斯）分布。
作为求解算法，您可以使用 Q 学习，它保证了提供足够数量的样本时解决方案的最优性。但是，如果您的网格太大（并且您说没有限制），我会建议策略搜索算法，例如策略梯度或相对熵（尽管它们保证仅收敛到局部最优）。您基本上可以在互联网上随处找到有关 Q-learning 的信息。对于最近一项关于政策搜索的调查，我建议这样做。
这些方法最酷的一点是，它们对策略中的探索进行编码（例如，softmax 策略中的温度、高斯分布中的方差），并且将尝试最大化 MDP 所描述的累积长期奖励。因此，通常您会通过高度探索（例如，完全随机策略）来初始化策略，并且通过反复试验，算法将使其具有确定性并收敛到最佳策略（但是，有时随机策略也是最佳的）。所有 RL 算法之间的主要区别在于它们如何在每次迭代中执行策略更新以及如何管理探索与利用之间的权衡（我应该探索多少 VS 我应该利用我已有的信息多少）。
正如 Demplo 所建议的，您也可以使用遗传算法 (GA)，但它们通常速度较慢并且需要更多调整（精英主义、交叉、突变...）。
我还针对您的问题尝试了一些策略搜索算法，它们似乎运行良好，尽管我随机初始化了网格并且不知道确切的最佳解决方案。如果您提供一些额外的详细信息（测试网格、最大步数以及初始位置是固定还是随机），我可以更精确地测试它们。