# Graph-based Reinforcement Learning meets Mixed Integer Programs: An application to 3D robot assembly discovery

arXiv: https://arxiv.org/abs/2203.04120 · HTML: https://mlsanity.com/paper/2203.04120/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 35 references that are in the map.
- First posted on arXiv 8 Mar 2022.

## Builds on (most cited first, 16 of 16)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Relational inductive biases, deep learning, and graph networks](https://mlsanity.com/paper/1806.01261/) (2018)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Towards Practical Multi-Object Manipulation using Relational Reinforcement Learning](https://mlsanity.com/paper/1912.11032/) (2019)
- [Reasoning About Physical Interactions with Object-Oriented Prediction and Planning](https://mlsanity.com/paper/1812.10972/) (2018)
- [Form2Fit: Learning Shape Priors for Generalizable Assembly from Disassembly](https://mlsanity.com/paper/1910.13675/) (2019)
- [Structured agents for physical construction](https://mlsanity.com/paper/1904.03177/) (2019)
- [MushroomRL: Simplifying Reinforcement Learning Research](https://mlsanity.com/paper/2001.01102/) (2020)
- [Planning with Learned Object Importance in Large Problem Instances using Graph Neural Networks](https://mlsanity.com/paper/2009.05613/) (2020)
- [Long-Horizon Multi-Robot Rearrangement Planning for Construction Assembly](https://mlsanity.com/paper/2106.02489/) (2021)
- [Learning to Rank for Synthesizing Planning Heuristics](https://mlsanity.com/paper/1608.01302/) (2016)
- [Efficient and Interpretable Robot Manipulation with Graph Neural Networks](https://mlsanity.com/paper/2102.13177/) (2021)
- [Combining Q-Learning and Search with Amortized Value Estimates](https://mlsanity.com/paper/1912.02807/) (2019)
- [Extended Tree Search for Robot Task and Motion Planning](https://mlsanity.com/paper/2103.05456/) (2021)
- [Active Learning of Abstract Plan Feasibility](https://mlsanity.com/paper/2107.00683/) (2021)

## Built on by (most cited first, 6 of 6)

- [A Survey of Optimization-based Task and Motion Planning: From Classical To Learning Approaches](https://mlsanity.com/paper/2404.02817/) (2024)
- [ASAP: Automated Sequence Planning for Complex Robotic Assembly with Physical Feasibility](https://mlsanity.com/paper/2309.16909/) (2023)
- [Learning Physically Realizable Skills for Online Packing of General 3D Shapes](https://mlsanity.com/paper/2212.02094/) (2022)
- [Feudal Graph Reinforcement Learning](https://mlsanity.com/paper/2304.05099/) (2023)
- [Subassembly to Full Assembly: Effective Assembly Sequence Planning through Graph-based Reinforcement Learning](https://mlsanity.com/paper/2409.13620/) (2024)
- [EUPHORIA: Efficient Universal Planning via Hybrid Optimization for Robust Industrial Robotic Assembly](https://mlsanity.com/paper/2605.18872/) (2026)

## Abstract (arXiv)

Robot assembly discovery is a challenging problem that lives at the intersection of resource allocation and motion planning. The goal is to combine a predefined set of objects to form something new while considering task execution with the robot-in-the-loop. In this work, we tackle the problem of building arbitrary, predefined target structures entirely from scratch using a set of Tetris-like building blocks and a robotic manipulator. Our novel hierarchical approach aims at efficiently decomposing the overall task into three feasible levels that benefit mutually from each other. On the high level, we run a classical mixed-integer program for global optimization of block-type selection and the blocks' final poses to recreate the desired shape. Its output is then exploited to efficiently guide the exploration of an underlying reinforcement learning (RL) policy. This RL policy draws its generalization properties from a flexible graph-based representation that is learned through Q-learning and can be refined with search. Moreover, it accounts for the necessary conditions of structural stability and robotic feasibility that cannot be effectively reflected in the previous layer. Lastly, a grasp and motion planner transforms the desired assembly commands into robot joint movements. We demonstrate our proposed method's performance on a set of competitive simulated RAD environments, showcase real-world transfer, and report performance and robustness gains compared to an unstructured end-to-end approach. Videos are available at https://sites.google.com/view/rl-meets-milp .