用深度强化学习自动发现可高效求解长程规划问题的子目标结构。
Sketch Decompositions for Classical Planning via Deep Reinforcement Learning
- 将学习子目标分解转化为深度强化学习任务，利用IW(k)搜索扩展状态空间。
- 在多个经典规划领域中，使用贪心序列的IW(k)搜索能快速解决多数问题。
- 虽不生成可解释规则，但分解结果清晰有效，适合复杂规划场景。
在长期规划与强化学习中，识别跨问题的共性子目标结构至关重要。近期研究发现，可通过基于特征的规则（称为草图）在多个经典规划领域中表达这些结构，使问题可通过贪心的IW(k)搜索序列在低多项式时间内求解。现有基于特征池和min-SAT求解器的学习方法存在可扩展性与表达力不足的局限。本文将草图分解学习建模为深度强化学习任务：在修改后的规划问题中，状态s的后继状态定义为通过IW(k)搜索可达的状态。实验评估表明，该方法获得的分解可在多个领域中通过贪心的IW(k)搜索序列成功求解问题。尽管所学草图不以可解释规则形式呈现，但其分解结果往往具有清晰的结构性。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。