To check whether I still supervise research projects, please check out my main page on research projects.
(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.)
TLDR:
The Waiter's Tray puzzle is a puzzle game that requires finding the right sequence of actions (moving bottles up and down and flipping the board to allow marbles to move from one bottle into another) to free the Waiter's tray. You have to model this as a planning task so that we won't have to find solutions by hand -- but we can relax and let a planner solve the problem! :)
The slightly longer version:
Many real-world problems -- such as puzzle games -- are actually planning problems, i.e., problems where a sequence of actions must be taken that transform the initial world state into one where all desired properties hold. Such problems can thus be modeled as planning problems, either using the PDDL description language or using HDDL, where the latter is a language for hierarchical planning problems.
In this project, your task is to model the Waiter's Tray puzzle as as planning problem (either as classical or as hierarchical problem, depending on whether you do a 6 pt or 12 pt project) and conduct an empirical evaluation with various state-of-the-art planning systems. As time allows, various extensions are desirable: First, rather than just evaluate the "true" (i.e., default) initial state of the problem, any initial state should be tested. To make the specification of that state for the domain modeler, you are to write your own input format and translate it to PDDL / HDDL. Second, you are to write a random generator that allows to create problems of larger problem size, i.e., trays with an arbitrary number of bottles, not just six. Lastly, you could model the problem in different ways and compare the performance of the different models. If, for example, you create a hierarchical model, you can write two task hierarchies, one that essentially encodes exactly the solution (so that technically no search is required anymore), and one that does not encode any advice but allows to generate all possible action sequences (thus including the solution).
As a nice minor addition to this work, the Tower of Hannoi problem might be evaluated and presented as well. This is a planning problem that shows some close similarities to Waiter's Tray in that it's solution also follows a recursive structure and can thus be described by an HTN task hierarchy. This domain is already modeled in HPDDL, an HTN formalism that is very close to HDDL. Translating it into HDDL should be a matter of a few hours at the most. Adding a description of that domain plus an empirical evaluation should therefore not be much additional work and fits into the project nicely.
Alternatively to modeling this problem from scratch by yourself, another variant of this project is the following: You build on existing models (by other students), "complete them" (they are not perfectly correct) and add convenient extra tools. For example, a simple text-based format to specify arbitrary problem instances (which then gets translated in PDDL or HDDL). The next step would be to create a graphical tool, where any possibly (initial) situation (and desired goal situation) can be configured graphically. This should then also be used to create animations of the solution, once found by creating a sequence of pictures corresponding to all intermediate states when following a plan. Finally, a random generator should be produced to create problems of arbitrary size/hardness. Ideally all these tools run online.
Your task is:
This project is either on classical or on Hierarchical Task Network (HTN) planning. If you are not familiar with either of this planning paradigms yet, here are a few notes to get started:
Relevant Puzzle Games: