A Novel Automated Curriculum Strategy to Solve Hard Sokoban Planning
  Instances
  In recent years, we have witnessed tremendous progress in deep reinforcement
learning (RL) for tasks such as Go, Chess, video games, and robot control.
Nevertheless, other combinatorial domains, such as AI planning, still pose
considerable challenges for RL approaches. The key difficulty in those domains
is that a positive reward signal becomes {\em exponentially rare} as the
minimal solution length increases. So, an RL approach loses its training
signal. There has been promising recent progress by using a curriculum-driven
learning approach that is designed to solve a single hard instance. We present
a novel {\em automated} curriculum approach that dynamically selects from a
pool of unlabeled training instances of varying task complexity guided by our
{\em difficulty quantum momentum} strategy. We show how the smoothness of the
task hardness impacts the final learning results. In particular, as the size of
the instance pool increases, the ``hardness gap'' decreases, which facilitates
a smoother automated curriculum based learning process. Our automated
curriculum approach dramatically improves upon the previous approaches. We show
our results on Sokoban, which is a traditional PSPACE-complete planning problem
and presents a great challenge even for specialized solvers. Our RL agent can
solve hard instances that are far out of reach for any previous
state-of-the-art Sokoban solver. In particular, our approach can uncover plans
that require hundreds of steps, while the best previous search methods would
take many years of computing time to solve such instances. In addition, we show
that we can further boost the RL performance with an intricate coupling of our
automated curriculum approach with a curiosity-driven search strategy and a
graph neural net representation.
