学习状态抽象以进行长期规划

我们定期执行的许多任务（例如，游览城市，烹饪食品或装载洗碗机）需要计划较长的时间。对我们来说，完成这些任务似乎很简单；但是，长期的推理仍然是当今强化学习（RL）算法的主要挑战。深度RL算法虽然无法长距离规划，但在直接针对像素的短距离任务（例如机器人抓取）方面具有出色的学习策略。同时，经典的计划方法（例如Dijkstra的算法和A $ ^ * $搜索）可以在很长的时间范围内进行计划，但是它们需要人工指定或特定于任务的抽象环境表示作为输入。

为了实现两全其美，最先进的视觉导航方法已将经典搜索方法应用于学习的图。特别是，SPTM [2]和SoRB [3]使用观察的重播缓冲区作为图中的节点，并学习参数距离函数以在图中绘制边缘。这些方法已经成功地应用于长期水平的模拟导航任务，这对于以前的方法来说太难了。

然而，这些方法仍然受到限制，因为它们对学习的图形中的错误高度敏感。规划算法试图利用图拓扑中的单个虫害边缘都像虫洞，这使得将图搜索和RL相结合的现有方法非常脆弱。例如，如果在迷宫中行进的人工代理认为在墙壁的两侧有两个观察员在附近，则其计划将涉及碰撞到墙壁的过渡。通过采用一个简单模型，假设每个边的恒定概率$ p $是有缺陷的，我们看到有缺陷的边的预期数目为$ p | E |。 = O（| V | ^ 2）$。换句话说，图中的错误与图中节点的数量成正比。

如果我们可以最大程度地减少图中的误差，我们可以做得更好。但是，在模拟和现实环境中，观察结果的图形可能会非常大，这甚至很难确定哪些边缘存在故障。为了最大程度地减少图中的误差，我们需要稀疏性。我们希望保留足以进行规划的最少节点集。如果我们有办法将类似的观察结果汇总到图中的单个节点中，则可以减少错误数量并提高计划的准确性。关键挑战在于以尊重时间约束的方式汇总观察结果。如果观察的外观相似但实际上相距较远，则应将其汇总到不同的节点中。

那么，如何在保证图仍然可用于计划的同时稀疏图呢？我们的主要见识是一种称为双向一致性的新颖合并准则。双向一致性可以看作是与目标条件设置无关的值的概括。直观上，双向一致性合并了可以作为起始状态互换的节点（i）和可以作为目标状态互换的节点（ii）。

有关双向一致性的示例，请考虑上图。假设我们的节点合并过程是：是否可以根据双向一致性将节点与粉红色和橙色的瓶子合并？首先，我们注意到从蓝色的瓶子移到粉红色的瓶子所需的工作与从蓝色的瓶子移到橙色的瓶子大致相同。因此带有粉红色和橙色瓶子的节点满足条件（ii），因为它们可以作为目标状态互换。但是，虽然可以从粉红色的瓶子开始移动到蓝色的瓶子，但是如果我们改为从橙色的瓶子开始，橙色的瓶子将掉在地上并崩溃！因此，具有粉色和橙色瓶子的节点将无法通过标准（i），因为它们不能作为起始状态互换。

实际上，我们不能期望遇到两个可以完美互换的节点。相反，我们合并可以互换的节点，直到阈值参数$ \ tau $。通过增加$ \ tau $，我们可以根据需要使结果图稀疏。至关重要的是，*我们在论文中证明，按照双向一致性进行合并可将图形的质量保留到一个误差项，误差项仅与合并阈值$ \ tau $成线性比例关系。

上面讨论的稀疏性的动机是鲁棒性：我们期望较小的图具有较少的错误。此外，我们的主定理告诉我们，可以在保持图质量的同时，根据双向一致性合并节点。不过，从实验上来说，所得的稀疏图是否更健壮？

为了测试稀疏图形内存对学习的距离度量中的错误的鲁棒性，我们对[3]的PointEnv迷宫中的壁进行了细化。虽然PointEnv是具有$（x，y）$坐标观测值的简单环境，但是使壁变薄是参数距离函数的主要挑战。 Learneddistance函数中的任何错误都将导致穿过墙的错误边缘，从而破坏计划的可行性。因此，仅使迷宫壁变薄就足以打破以前的最新技术[3]，成功率为0％。

稀疏图形记忆如何发挥作用？使用更少的边缘，执行自我监督的清理变得很容易：代理可以逐步穿越环境以检测并从其图形中删除有缺陷的边缘。下图说明了此过程的结果。红色显示的密集图具有许多错误的边缘，而绿色显示的稀疏性和自我监督的清理克服了学习距离度量中的错误，从而获得了100％的成功率。

在视觉输入实验中，我们看到了类似的趋势。在ViZDoom [4]和SafetyGym [5]中–需要从原始图像进行规划的迷宫导航任务–稀疏图形内存始终如一地提高了基线方法（包括SoRB [3]和SPTM [2]）的成功率。

除了包含更少的错误外，稀疏图形内存还可以产生更多的最佳计划。在ViZDoom迷宫导航任务[4]上，我们发现SGM在完成简单，中等和困难的迷宫任务时只需很少的步骤即可达到最终目标，这意味着代理遵循一条较短的路线到达终点。

总的来说，我们发现具有双向一致性的状态聚合导致的计划比现有技术要强得多。尽管很有希望，但将经典计划与基于学习的控制相结合仍然存在许多悬而未决的问题和挑战。我们正在考虑的一些问题-如何将这些方法从导航扩展到操纵域？由于世界不是一成不变的，我们应该如何在不断变化的环境上建立图表？在基于图形的计划方法范围之外，如何利用双向一致性？我们对这些未来的方向感到兴奋，并希望我们的理论和实验结果对其他研究延长时间范围的控制的研究者有用。