Research Project: Modeling and Solving Data Structures

Project still available?

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.)

Requirements

• This project can be carried out as 6 pt or as 12 pt project, preferably as 12 pt.
• 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 the respective technology that's being used (i.e., SAT or classical planning) before you start the project. (Still, not strictly required, but it would help if you could work on these foundations before the project formally starts.)
• Depending on the exact topic chosen (see description below), it might be beneficial to have taken the Algorithms course.
• This is a project that can be taken by any student, also if your marks are not primarily in the HD range.

Project Description

TLDR:

In this project we will first decide on some complex problem/procedure to be done, for example an operation on some data structure like the insertion of a node into a search tree. The chosen problem/procedure will then be modeled using AI planning (classical or hierarchical) and then solved with state-of-the-art solvers.

The slightly longer version:

This project primarily aims at producing new benchmark domains for AI planning systems, but a huge additional benefit -- though this would require the project to take 12 pts -- would be to use this benchmark for the automated creation of exam question given certain constraints. We are free in which problem we model, but one possibility is the creation of search trees, such as Binary Search trees (BSTs), AVL trees, or Red/Black trees. Both the insertion as well deletion of nodes might require further operations, like re-balancing of the tree. All these operations should then be implemented via planning. On top of encoding only the (execution of) simple addition and deletions, I'd like to have the option to create exam exercises with this. For this setting, we do not just provide a tree and a given addition or deletion operation, but instead constraints on the size of the tree as well as desired operations that should be required to be carried out by a student after an add or delete operation. The solution is then the input tree as well as the insert/delete operation demanded in the question (plus the resulting solution to this). Once the model is complete, we will evaluate various problems using state-of-the-art planning systems.

Further Reading

This project is either on classical planning. For this, you may find my reading recommendations on my page with resources for students helpful. But please don't invest more than a few minutes (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 advise to listen to (and follow) my hands-on introduction on classical planning that's linked there as well. (If we choose planning to model one of the problems.)