What Planning Problems Can A Relational Neural Network Solve?
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910432821772288 |
|---|---|
| author | Mao, Jiayuan Lozano-Pérez, Tomás Tenenbaum, Joshua B. Kaelbling, Leslie Pack |
| author_facet | Mao, Jiayuan Lozano-Pérez, Tomás Tenenbaum, Joshua B. Kaelbling, Leslie Pack |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_03682 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | What Planning Problems Can A Relational Neural Network Solve? Mao, Jiayuan Lozano-Pérez, Tomás Tenenbaum, Joshua B. Kaelbling, Leslie Pack Machine Learning Artificial Intelligence Neural and Evolutionary Computing 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. |
| title | What Planning Problems Can A Relational Neural Network Solve? |
| topic | Machine Learning Artificial Intelligence Neural and Evolutionary Computing |
| url | https://arxiv.org/abs/2312.03682 |