What Planning Problems Can A Relational Neural Network Solve?
Jiayuan Mao Tomás Lozano-Pérez Joshua B. Tenenbaum Leslie Pack Kaelbling
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.