Learning General Policies for Classical Planning Domains: Getting Beyond C$_2$
<|reference_start|>Learning General Policies for Classical Planning Domains: Getting Beyond C$_2$: GNN-based approaches for learning general policies across planning domains are limited by the expressive power of $C_2$, 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 $C_3$, unlike $1$- and $2$-GNNs that are confined to $C_2$, they require quartic time for message exchange and cubic space for embeddings, rendering them impractical. In this work, we introduce a parameterized version of relational GNNs. When $t$ is infinity, R-GNN[$t$] approximates $3$-GNNs 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 $C_3$ features 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 input states only. Experimental results illustrate the clear performance gains of R-GNN[$1$] and R-GNN[$2$] over plain R-GNNs, and also over edge transformers that also approximate $3$-GNNs.<|reference_end|>
@article{ståhlberg2024learning,
    title={Learning General Policies for Classical Planning Domains: Getting Beyond
  C$_2$},
    author={Simon Str{a}hlberg, Blai Bonet, Hector Geffner},
    journal={arXiv preprint arXiv:2403.11734},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.11734},
    primaryClass={cs.AI cs.LG}
}