What Planning Problems Can A Relational Neural Network Solve?
This provides theoretical insights for designing neural networks in planning, but it is incremental as it builds on existing analysis methods.
The paper tackles the problem of understanding when and how efficiently goal-conditioned policies can be learned using relational neural networks, by showing that planning problems fall into three classes based on circuit width and depth growth with object count and horizon.
Goal-conditioned policies are generally understood to be "feed-forward" circuits, in the form of neural networks that map from the current state and the goal specification to the next action to take. However, under what circumstances such a policy can be learned and how efficient the policy will be are not well understood. In this paper, we present a circuit complexity analysis for relational neural networks (such as graph neural networks and transformers) representing policies for planning problems, by drawing connections with serialized goal regression search (S-GRS). We show that there are three general classes of planning problems, in terms of the growth of circuit width and depth as a function of the number of objects and planning horizon, providing constructive proofs. We also illustrate the utility of this analysis for designing neural networks for policy learning.