改进经典规划中的广义策略学习,提升效率与可扩展性。
Efficient Lookahead Encoding and Abstracted Width for Learning General Policies in Classical Planning
- 用关系图神经网络统一编码搜索树,单次前向传播评估所有转移。
- 通过抽象化原子类型,将新颖性检查复杂度从原子降至对象级别。
- 在IPC 2023大规模基准上超越现有方法,包括经典规划器LAMA。
广义规划旨在学习可跨同一经典规划领域内多个实例泛化的策略。近期基于图神经网络(GNN)的方法已在多个领域实现近乎完美的策略。本文改进了最近提出的迭代宽度(IW)策略:原方法通过IW-前瞻搜索扩大后继状态范围,能“跳过”多步转移以简化问题结构,但每次转移需单独评估,导致计算成本不可扩展且表达能力受限。尽管IW(1)因线性依赖原子数而具有吸引力,但在包含数千对象的国际规划竞赛(IPC)2023基准中仍显低效。本文解决上述两问题:首先提出一种高效的整体搜索树编码,仅通过当前状态与可达状态的关系差异表示,使关系图神经网络(R-GNN)可在一次前向传播中评分所有转移;其次定义抽象化IW(1),在新颖性检测中引入关系抽象:将每个原子除一个参数外均替换为其类型,只要任一抽象形式为新即判定原原子为新。该结构压缩使新颖性搜索复杂度从原子降至对象,同时保留有意义的子目标结构。我们在超大规模的IPC 2023基准及多样化领域上验证,所提策略达到新最佳性能,显著优于此前工作,包括经典规划器LAMA。
原文摘要 · Abstract (English)
Generalized planning aims to learn policies that generalize across collections of instances within a classical planning domain. Recent Graph Neural Network (GNN) approaches have learned nearly perfect policies for several domains. This work improves on the recently published idea of Iterated Width (IW) policies. Therein, the policy broadens its successor scope through an IW-lookahead search that can "jump" over multiple transitions, simplifying the problem structure. Yet, each transition is evaluated individually, leading to unscalable compute costs and expressivity limitations. Furthermore, although IW(1) is attractive because it scales linearly with the number of atoms, it becomes inefficient once thousands of objects are considered, as in the International Planning Competition (IPC) 2023 benchmark. We address both limitations. First, we introduce a vastly more efficient holistic encoding of the entire search tree. It jointly represents IW(1)-reachable states only by their relational differences to the current state, enabling Relational GNNs (R-GNNs) to score all transitions in a single forward pass. Second, we define Abstracted IW(1) to improve scaling through relational abstraction during novelty checks. Rather than testing fully instantiated atoms, it abstracts each atom by replacing all but one argument with its type. The original atom is novel if any of its abstracted forms is novel. This structural compression shifts novelty search scaling from atoms to objects, while preserving meaningful subgoal structure. We evaluate our contributions on the hyperscaling IPC 2023 benchmark and across diverse domains, including domains requiring features beyond the $C_2$ logic fragment. Our policies achieve new state-of-the-art performance, significantly surpassing prior work, including the classical planner LAMA.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。