# Solving Hard AI Planning Instances Using Curriculum-Driven Deep Reinforcement Learning

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Jun 2020.

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

- [Variational Automatic Curriculum Learning for Sparse-Reward Cooperative Multi-Agent Problems](https://mlsanity.com/paper/2111.04613/) (2021)
- [Optimize Planning Heuristics to Rank, not to Estimate Cost-to-Goal](https://mlsanity.com/paper/2310.19463/) (2023)
- [A Novel Automated Curriculum Strategy to Solve Hard Sokoban Planning Instances](https://mlsanity.com/paper/2110.00898/) (2021)
- [Reinforcement learning with combinatorial actions for coupled restless bandits](https://mlsanity.com/paper/2503.01919/) (2025)
- [Solving Sokoban with forward-backward reinforcement learning](https://mlsanity.com/paper/2105.01904/) (2021)
- [Untangling Braids with Multi-agent Q-Learning](https://mlsanity.com/paper/2109.14502/) (2021)
- [Left Heavy Tails and the Effectiveness of the Policy and Value Networks in DNN-based best-first search for Sokoban Planning](https://mlsanity.com/paper/2206.14298/) (2022)
- [A Differentiable Loss Function for Learning Heuristics in A*](https://mlsanity.com/paper/2209.05206/) (2022)
- [Transfer Learning and Curriculum Learning in Sokoban](https://mlsanity.com/paper/2105.11702/) (2021)
- [Graph Value Iteration](https://mlsanity.com/paper/2209.09608/) (2022)
- [Practical Graph Optimisation and AI-Driven Models for Active Directory Security Hardening](https://mlsanity.com/paper/2607.22009/) (2026)

## Abstract (arXiv)

Despite significant progress in general AI planning, certain domains remain out of reach of current AI planning systems. Sokoban is a PSPACE-complete planning task and represents one of the hardest domains for current AI planners. Even domain-specific specialized search methods fail quickly due to the exponential search complexity on hard instances. Our approach based on deep reinforcement learning augmented with a curriculum-driven method is the first one to solve hard instances within one day of training while other modern solvers cannot solve these instances within any reasonable time limit. In contrast to prior efforts, which use carefully handcrafted pruning techniques, our approach automatically uncovers domain structure. Our results reveal that deep RL provides a promising framework for solving previously unsolved AI planning problems, provided a proper training curriculum can be devised.