Research Project: Modeling the Waiter's Tray Puzzle as Planning Problem

Project still available?

The project is not yet taken by another student.

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 6 pt or as 12 pt project.
  • You don't need background on AI planning as learning that in the first two weeks should be easy. But since this is only a 12 pt or even a 6 pt project (meaning that time is limited) it'd be quite beneficial if you had at least a basic understanding of classical planning before you start the project. (Still, not strictly required, but it would help if you could work on the planning basics a week before the project formally starts.)
  • This is a project that can be taken by any student, whether your marks are primarily in the pass or in high HD range, it's fun for everybody!

Project Description

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.

Your task is:

  • Model the Waiter's Tray puzzle either as classical planning problem using PDDL or as HTN planning problem using HDDL.
  • As time allows (also depending on the number of points that are chosen),
    • write your own input format and translate it to PDDL/HDDL
    • write a random generator that creates problem instances with any number of given bottles
    • write multiple models and compare their performance
  • Conduct an empirical evaluation for all your models with state-of-the-art planning systems.
  • Report on the findings (using my LaTeX template for research projects).
  • Depending on how we go, we could write a workshop paper about the created domain.

Further Reading

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:

  • HTN planning is a planning formalism that's concerned with the step-wise refinement of abstract tasks until a primitive plan is found -- so hierarchical planning is quite similar to formal grammars, where an initial non-terminal symbol is refined into a sequence of terminal symbols. The main differences are that (a) primitive tasks (corresponding to terminal symbols) have preconditions and effects, to not every plan is executable and (b) the means to refine compound tasks (which correspond to production rules from formal grammars) are only partially ordered rather than totally as in formal grammars.
  • You find further reading recommendations 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. I very strongly advice to listen to (and follow) my hands-on introduction on classical planning that's linked there as well.

Relevant Puzzle Games: