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.)
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.
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:
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:
All repositories for the International Planning Competitions (IPC), some of them containing Sokoban Puzzles:
Level generation for Sokoban:
Dead-end detection in classical planning:
Complexity of Sokoban: