Learning More Expressive General Policies for Classical Planning Domains

Proceedings of the AAAI Conference on Artificial Intelligence, vol. 39, pp. 26697–26706

Abstract

GNN-based approaches for learning general policies across planning domains are limited by the expressive power of C2, namely; first-order logic with two variables and counting. This limitation can be overcomed by transitioning to k-GNNs, for k=3, wherein object embeddings are substituted with triplet embeddings. Yet, while 3-GNNs have the expressive power of C3, unlike 1- and 2-GNNs that are confined to C2, they require quartic time for message exchange and cubic space to store embeddings, rendering them infeasible. In this work, we introduce a parameterized version R-GNN[t] (with parameter t) of Relational GNNs. Unlike GNNs, that are designed to perform computation on graphs, Relational GNNs are designed to do computation on relational structures. When t=infty, R-GNN[t] approximates 3-GNNs over graphs, but using only quadratic space for embeddings. For lower values of t, such as t=1 and t=2, R-GNN[t] achieves a weaker approximation by exchanging fewer messages, yet interestingly, often yield the expressivity required in several planning domains. Furthermore, the new R-GNN[t] architecture is the original R-GNN architecture with a suitable transformation applied to the inputs only. Experimental results illustrate the clear performance gains of R-GNN[1] over the plain R-GNNs, and also over Edge Transformers that also approximate 3-GNNs.

Authors 3

1. Simon Ståhlberg Aachen

   RWTH Aachen University

   Affiliation as printed

   Rheinisch Westfälische Technische Hochschule Aachen

2. Blai Bonet

   Universitat Pompeu Fabra

   Affiliation as printed

   Universitat Pompeu Fabra

3. Héctor Geffner Aachen

   RWTH Aachen University

   Affiliation as printed

   Rheinisch Westfälische Technische Hochschule Aachen