Sketch Decompositions for Classical Planning via Deep Reinforcement Learning

📄 arXiv: 2412.08574v2 📥 PDF

作者: Michael Aichmüller, Hector Geffner

分类: cs.AI

发布日期: 2024-12-11 (更新: 2025-08-15)

💡 一句话要点

提出基于深度强化学习的规划草图分解方法，提升复杂规划问题的求解效率。

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 深度强化学习 经典规划 草图分解 IW(k)搜索 子目标结构

📋 核心要点

  1. 现有基于特征池和min-SAT求解器的草图学习方法，在可扩展性和表达性方面存在局限性，难以处理复杂问题。
  2. 论文提出将草图分解学习问题建模为深度强化学习任务，旨在学习通用的规划策略，提升问题分解效率。
  3. 实验结果表明，该方法获得的草图分解在多个领域有效，能够通过贪婪搜索序列解决复杂规划问题。

📝 摘要（中文）

在规划和强化学习中，识别跨问题的通用子目标结构对于实现长时程目标至关重要。最近的研究表明，这种结构可以通过基于特征的规则（称为草图）在多个经典规划领域中表达。这些草图将问题分解为子问题，然后可以通过贪婪的IW$(k)$搜索序列在低多项式时间内解决。虽然已经开发了使用特征池和min-SAT求解器学习草图的方法，但它们面临两个关键限制：可扩展性和表达性。本文通过将学习草图分解的问题表述为深度强化学习（DRL）任务来解决这些限制，其中在修改后的规划问题中寻找通用策略，状态s的后继状态被定义为通过IW$(k)$搜索从s可到达的状态。通过这种方法获得的草图分解在各种领域中进行了实验评估，当通过贪婪的IW$(k)$搜索序列达到目标时，问题被认为通过分解解决。虽然我们的DRL方法学习草图分解不会产生规则形式的可解释草图，但我们证明了由此产生的分解通常可以以清晰的方式理解。

🔬 方法详解

问题定义：论文旨在解决经典规划问题中，现有草图学习方法在可扩展性和表达性方面的不足。现有方法依赖特征工程和min-SAT求解器，难以处理大规模、高复杂度的规划问题，导致求解效率低下。

核心思路：论文的核心思路是将草图分解的学习过程建模为一个深度强化学习（DRL）任务。通过学习一个策略，智能体能够自主地将复杂规划问题分解为一系列易于解决的子问题。这种方法避免了手动设计特征和求解复杂约束，从而提升了可扩展性和表达性。

技术框架：整体框架包含一个修改后的规划环境和一个DRL智能体。规划环境的状态转移函数被修改为通过IW$(k)$搜索可达的状态。DRL智能体通过与环境交互，学习一个策略，该策略指导如何进行草图分解。智能体接收环境的状态作为输入，输出一个动作，该动作对应于一种草图分解方式。环境根据智能体的动作更新状态，并返回奖励信号。

关键创新：最重要的创新在于将草图分解问题转化为DRL任务。与传统的基于规则或约束求解的方法不同，DRL方法能够从数据中学习，自动发现有效的草图分解策略。此外，该方法使用IW$(k)$搜索作为状态转移的基础，保证了子问题的可解性。

关键设计：论文中，DRL智能体的网络结构和奖励函数的设计至关重要。具体的网络结构未知，但需要能够处理规划问题的状态表示，并输出合适的草图分解动作。奖励函数的设计需要引导智能体学习有效的草图分解策略，例如，可以根据子问题的可解性和最终目标的达成情况来设计奖励。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

论文通过实验验证了该方法在多个经典规划领域的有效性。实验结果表明，该方法能够学习到有效的草图分解策略，并通过贪婪的IW$(k)$搜索序列成功解决复杂规划问题。虽然论文没有提供具体的性能数据和对比基线，但强调了该方法在可扩展性和表达性方面的优势。

🎯 应用场景

该研究成果可应用于机器人导航、游戏AI、任务调度等领域。通过学习通用的规划策略，可以使智能体在复杂环境中自主完成任务，提高决策效率和鲁棒性。未来，该方法有望扩展到更广泛的规划问题，例如，涉及时间、资源约束的规划问题。

📄 摘要（原文）

In planning and reinforcement learning, the identification of common subgoal structures across problems is important when goals are to be achieved over long horizons. Recently, it has been shown that such structures can be expressed as feature-based rules, called sketches, over a number of classical planning domains. These sketches split problems into subproblems which then become solvable in low polynomial time by a greedy sequence of IW$(k)$ searches. Methods for learning sketches using feature pools and min-SAT solvers have been developed, yet they face two key limitations: scalability and expressivity. In this work, we address these limitations by formulating the problem of learning sketch decompositions as a deep reinforcement learning (DRL) task, where general policies are sought in a modified planning problem where the successor states of a state s are defined as those reachable from s through an IW$(k)$ search. The sketch decompositions obtained through this method are experimentally evaluated across various domains, and problems are regarded as solved by the decomposition when the goal is reached through a greedy sequence of IW$(k)$ searches. While our DRL approach for learning sketch decompositions does not yield interpretable sketches in the form of rules, we demonstrate that the resulting decompositions can often be understood in a crisp manner.