# ERL-MPP: Evolutionary Reinforcement Learning with Multi-head Puzzle Perception for Solving Large-scale Jigsaw Puzzles of Eroded Gaps

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Placed in RL for robot locomotion and manipulation, one of 15 directions in Deep reinforcement learning methods.
- Builds on 16 of its 34 references that are in the map.
- First posted on arXiv 13 Apr 2025.

## Placed in

- Deep reinforcement learning methods / [RL for robot locomotion and manipulation](https://mlsanity.com/deeprl/rl-for-robot-locomotion-and-manipulation/)

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

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Swin Transformer: Hierarchical Vision Transformer using Shifted Windows](https://mlsanity.com/paper/2103.14030/) (2021)
- [EfficientNet: Rethinking Model Scaling for Convolutional Neural Networks](https://mlsanity.com/paper/1905.11946/) (2019)
- [Unsupervised Learning of Visual Representations by Solving Jigsaw Puzzles](https://mlsanity.com/paper/1603.09246/) (2016)
- [Unsupervised Visual Representation Learning by Context Prediction](https://mlsanity.com/paper/1505.05192/) (2015)
- [Fine-Grained Visual Classification via Progressive Multi-Granularity Training of Jigsaw Patches](https://mlsanity.com/paper/2003.03836/) (2020)
- [Masked Jigsaw Puzzle: A Versatile Position Embedding for Vision Transformers](https://mlsanity.com/paper/2205.12551/) (2022)
- [Fine-Grained Object Classification via Self-Supervised Pose Alignment](https://mlsanity.com/paper/2203.15987/) (2022)
- [Deepzzle: Solving Visual Jigsaw Puzzles with Deep Learning andShortest Path Optimization](https://mlsanity.com/paper/2005.12548/) (2020)
- [Structure-Preserving Image Super-Resolution](https://mlsanity.com/paper/2109.12530/) (2021)
- [Solving Archaeological Puzzles](https://mlsanity.com/paper/1812.10553/) (2018)
- [Solving Jigsaw Puzzles with Eroded Boundaries](https://mlsanity.com/paper/1912.00755/) (2019)
- [A Genetic Algorithm-Based Solver for Very Large Jigsaw Puzzles](https://mlsanity.com/paper/1711.06769/) (2017)
- [Pictorial and apictorial polygonal jigsaw puzzles from arbitrary number of crossing cuts](https://mlsanity.com/paper/2008.07644/) (2020)
- [Image Reassembly Combining Deep Learning and Shortest Path Problem](https://mlsanity.com/paper/1809.00898/) (2018)
- [Relaxation Labeling Meets GANs: Solving Jigsaw Puzzles with Missing Borders](https://mlsanity.com/paper/2203.14428/) (2022)

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

- [VLHSA: Vision-Language Hierarchical Semantic Alignment for Jigsaw Puzzle Solving with Eroded Gaps](https://mlsanity.com/paper/2509.25202/) (2025)
- [PuzLM: Solving Jigsaw Puzzles with Sequence-to-Sequence Language Models](https://mlsanity.com/paper/2511.06315/) (2025)
- [The Missing GAP: From Solving Square Jigsaw Puzzles to Handling Real World Archaeological Fragments](https://mlsanity.com/paper/2605.12077/) (2026)
- [JigSync: Gauge-Resolved Synchronization for Jigsaw Reassembly under Unknown Piece Orientation](https://mlsanity.com/paper/2609.18379/) (2026)
- [Fix the Match, Not the Solver: STITCH -- a Self-Supervised Compatibility Measure for Eroded Visual Puzzles](https://mlsanity.com/paper/2610.13176/) (2026)

## Abstract (arXiv)

Solving jigsaw puzzles has been extensively studied. While most existing models focus on solving either small-scale puzzles or puzzles with no gap between fragments, solving large-scale puzzles with gaps presents distinctive challenges in both image understanding and combinatorial optimization. To tackle these challenges, we propose a framework of Evolutionary Reinforcement Learning with Multi-head Puzzle Perception (ERL-MPP) to derive a better set of swapping actions for solving the puzzles. Specifically, to tackle the challenges of perceiving the puzzle with gaps, a Multi-head Puzzle Perception Network (MPPN) with a shared encoder is designed, where multiple puzzlet heads comprehensively perceive the local assembly status, and a discriminator head provides a global assessment of the puzzle. To explore the large swapping action space efficiently, an Evolutionary Reinforcement Learning (EvoRL) agent is designed, where an actor recommends a set of suitable swapping actions from a large action space based on the perceived puzzle status, a critic updates the actor using the estimated rewards and the puzzle status, and an evaluator coupled with evolutionary strategies evolves the actions aligning with the historical assembly experience. The proposed ERL-MPP is comprehensively evaluated on the JPLEG-5 dataset with large gaps and the MIT dataset with large-scale puzzles. It significantly outperforms all state-of-the-art models on both datasets.