发现对称性可提升规划学习效率,否则无法在某些领域训练通用策略。
Symmetries and Expressive Requirements for Learning General Policies
- 将状态转为图,用现成算法检测对称性
- 发现C2逻辑和GNN特征无法区分非对称状态
- 揭示通用策略学习的表达能力瓶颈,适合规划与强化学习研究者
状态对称性在规划和泛化规划中起关键作用:前者可缩小搜索空间,后者可减少训练集规模。但在泛化规划中,区分非对称状态(即非同构关系结构)同样重要。尽管一阶逻辑能区分非对称状态,但当前用于表示和学习通用策略的语言与架构却受限于仅具C₂(含计数的一阶逻辑,变量数≤2)表达力。本文将规划状态映射为普通图,使用现成算法判断两状态是否在目标下同构,并通过着色算法检验由描述逻辑或图神经网络(GNN)提取的C₂特征能否区分非同构状态。实验表明,对称性检测能显著提升学习效率;而无法检测非对称性则会导致某些领域完全无法学习通用策略。
原文摘要 · Abstract (English)
State symmetries play an important role in planning and generalized planning. In the first case, state symmetries can be used to reduce the size of the search; in the second, to reduce the size of the training set. In the case of general planning, however, it is also critical to distinguish non-symmetric states, i.e., states that represent non-isomorphic relational structures. However, while the language of first-order logic distinguishes non-symmetric states, the languages and architectures used to represent and learn general policies do not. In particular, recent approaches for learning general policies use state features derived from description logics or learned via graph neural networks (GNNs) that are known to be limited by the expressive power of C_2, first-order logic with two variables and counting. In this work, we address the problem of detecting symmetries in planning and generalized planning and use the results to assess the expressive requirements for learning general policies over various planning domains. For this, we map planning states to plain graphs, run off-the-shelf algorithms to determine whether two states are isomorphic with respect to the goal, and run coloring algorithms to determine if C_2 features computed logically or via GNNs distinguish non-isomorphic states. Symmetry detection results in more effective learning, while the failure to detect non-symmetries prevents general policies from being learned at all in certain domains.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。