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

Song, Xingke; Yang, Xiaoying; Yao, Chenglin; Ren, Jianfeng; Bai, Ruibin; Chen, Xin; Jiang, Xudong

Abstract

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.

Citation

Song, X., Yang, X., Yao, C., Ren, J., Bai, R., Chen, X., & Jiang, X. (2025, February). ERL-MPP: Evolutionary Reinforcement Learning with Multi-head Puzzle Perception for Solving Large-scale Jigsaw Puzzles of Eroded Gaps. Presented at The 39th Annual AAAI Conference on Artificial Intelligence, Philadelphia, Pennsylvania, USA

• Presentation Conference Type: Conference Paper (published)
• Conference Name: The 39th Annual AAAI Conference on Artificial Intelligence
• Start Date: Feb 25, 2025
• End Date: Mar 4, 2025
• Acceptance Date: Jan 17, 2025
• Deposit Date: Apr 1, 2025
• Journal: Proceedings of the AAAI Conference on Artificial Intelligence
• Print ISSN: 2159-5399
• Electronic ISSN: 2374-3468
• Publisher: Association for the Advancement of Artificial Intelligence
• Peer Reviewed: Peer Reviewed
• Public URL: https://nottingham-repository.worktribe.com/output/47272528
• Publisher URL: https://ojs.aaai.org/index.php/AAAI/index