Research Project: On Deadend Detection in Planning and Sokoban

Project still available?

This project has been taken in 2022, so it will only be available again in S1 2024, since I'd like to have some break before I offer it again.

It might however be that I don't have capacities left in general. Please check out the main page on research projects to see whether I'm maxed out. (I don't post this here so that I don't have to update all my project descriptions in case I don't accept more students.)

Requirements

  • This project can be carried out as 12 pt project (but only over two semesters!) or as 24 pt Honours project.
  • You don't need background on AI planning as learning that in the first two weeks should be easy.
  • Since I plan to publish this work at an international top-tier (i.e., A*) conference, you should have very clear HD marks throughout. Please take a look at any of my other projects should your marks not be strong enough.

Project Description

TLDR:

In a very nutshell, this project is about comparing the pruning power of deadend detectors that are specific to the Sokoban game with the pruning power of general planning detectors, but with Sokoban being encoded as planning problem. This comparison should be conducted both in theory as well as empirically.

Sokoban Game

The slightly longer version:

Sokoban is a Puzzle game where an agent (with a given initial position in a 2D board) needs to move n boxes (again, each on an initial position on the same board) to the n pre-defined goal positions. It does not matter which box is on which goal position, the only thing that matters is that all n boxes are on some goal position, and there are always the same number of boxes as there are goal positions. The agent can move in 4 directions: up, down, left, right, but he can only move there if it's either free or if he could push an occupying box, which is only possible if the position next to the box is free (so he can't, for example, push two boxes at once). This game is known to be PSPACE-complete and thus very challenging for any kind of solver. As a consequence, there have been many specialized solvers that do nothing else than solving Sokoban puzzles (some of them optimally, others just find some solution quickly).

AI Planning is, in its simplest form, also PSPACE complete and thus seems well-suited to solve the problem. In fact, there already exist many Sokoban models, modeled in the (well-known) PDDL description language for planning problems. Some techniques applied in Sokoban solvers are similar to those applied in planning, e.g., the detection of dead-end states (e.g., a box moved to a wall can never be "pulled back" from there). So it would be interesting to see how Sokoban-specific solvers perform compared to state-of-the-art techniques in planning. So, in this work, you will compare the runtime of specialized Sokoban-solvers to the runtime of state-of-the-art planning systems. A specific focus will be laid on the deadend detection, i.e., it should be analyzed whether each deadend detected by a Sokoban deadend detector can also be detected by all general planning deadend detectors -- and vice versa. This analysis should be done both in theory and in practice.

Your task is:

  • Understand all existing planning and sokoban deadend detectors.
  • Compare empirically the best-performing state-of-the-art sokoban solvers with (carefully chosen) state-of-the-art planning systems on all existing Sokoban models. These models include all existing PDDL models as well as all "standard Sokoban problems", which have to be translated into PDDL first.
  • Compare empirically as well as theoretically all existing Sokoban deadend detectors with all exiting planning deadend detectors.
  • If the planning detector can identify situations as deadends that the existing Sokoban deadend detectors can not, then consider whether a novel Sokoban-specific deadend detector can be developed based on the domain-independent one.
  • Report on the findings (using my LaTeX template for research projects).
  • Assist me in putting together a scientific paper at an A*, A, or B conference (most likely after the project).

Further Reading

You will have to understand classical planning and most notably PDDL. If you are not familiar with this planning paradigm yet, then please take a look at my recommendations given on my page with resources for students. But please don't invest more than a few minute (if any) before your application, since I don't want you to waste any time before I formally agree to supervise your project.


About the Sokoban game:


Sokoban solvers:


All repositories for the International Planning Competitions (IPC), some of them containing Sokoban Puzzles:


Level generation for Sokoban:

  • Procedural Generation of Initial States of Sokoban, IJCAI 2019


Solving Sokoban:

  • Optimal Sokoban solving using pattern databases with specific domain knowledge, AIJ 2015
  • Improved Heuristic and Tie-Breaking for Optimally Solving Sokoban, IJCAI 2016


Dead-end detection in classical planning:

  • Search and Learn: On Dead-End Detectors, the Traps they Set, and Trap Learning, IJCAI 2017
  • Traps, Invariants, and Dead-Ends, ICAPS 2016


Complexity of Sokoban: