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 (with state-of-the-art dead-end detection). Given the available time, we also want to extend a graphical front end for a publicly available Sokoban level generator, solver, and game (https://www.sokoban-online.de/) to execute planning systems directly and to simulate their found solutions (the mentioned tool can be used to generate levels, play them manually, or to see a simulation how they are solved autonomously).
- Conduct Literature survey on:
- Optimal Planning Heuristics
- Techiques for dead-end detection in classical planning
- Level Generation for Sokoban
- Solving Techniques for Sokoban
- Competitions for Sokoban and Planning Competitions, where Sokoban was used
- Conduct an exhaustive empirical Evaluation on
- Sokoban using planning technology (taking into account several existing Sokoban models as well as different planners and configurations)
- Sokoban using specialized Sokoban solvers
- If time is sufficient: Extend an existent GUI for Sokoban to include planning technology
- It would be great if you had prerequisites in AI Planning or any kind of Constraint Solving, thought that's not essential
- For conducting the empirical evaluation, knowledge in any language for the evaluation of large data sets, such as "R", is highly recommended (though not essential)
Please send me:
- The course code.
- The URL of your course.
- The number of points your course has (i.e., 6, 12, 24, or 24 honours final project).
- When you would like to do your project.
- About the Sokoban game:
- The Software project that can be used as basis:
- 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: https://www.ijcai.org/Proceedings/2019/646
- Solving Sokoban:
- Optimal Sokoban solving using pattern databases with specific domain knowledge, AIJ 2015: https://www.sciencedirect.com/science/article/pii/S0004370215000867
- Improved Heuristic and Tie-Breaking for Optimally Solving Sokoban, IJCAI 2016: https://www.ijcai.org/Proceedings/16/Papers/100.pdf
- Dead-end detection in classical planning:
- Search and Learn: On Dead-End Detectors, the Traps they Set, and Trap Learning, IJCAI 2017: https://www.ijcai.org/Proceedings/2017/0614.pdf
- Traps, Invariants, and Dead-Ends, ICAPS 2016: https://people.eng.unimelb.edu.au/nlipovetzky/papers/icaps16_trapper.pdf
- Complexity of Sokoban:
- Sokoban is PSPACE-complete, technical report 1997: https://era.library.ualberta.ca/items/f551dfd8-c8e6-4e78-883d-3afbee5bce83
- SOKOBAN and other motion planning problems, Computational Geometry 1999: https://www.sciencedirect.com/science/article/pii/S0925772199000176
- Being able to survey existing literature
- Being able to conduct an exhaustive empirical evaluation, which includes both running a range of systems (carrying out the evaluation) and evaluating and reporting the respective data.
- AI in Games
- Empirical Evaluation
- (Graphical User Interface)