a postdoc or assistant/associate professor to work with us on AI planning, learning for planning and neurosymbolic RL (see our ongoing projects and publications for examples).
There will be more openings for PhD students and postdocs in the near future. If you are interested in working with us, please contact Jendrik Seipp.
MSc Theses
We offer interesting topics for master theses in the field of AI/ML, often with a focus on AI planning.
If you are interested, please contact us by email, preferably including a short CV.
Together, we will then develop a topic that suits your interest and background.
Here are some example topics:
Planning With Large Language Models
Various topics are possible in this area.
Deep Learning for Planning
Various topics are possible in this area.
Deep Reinforcement Learning vs. Classical Planning for Solving Puzzles
A recent
paper
developed the ML pipeline
DeepCubeA that learns how to
solve Rubik's cube tasks (and other puzzles). DeepCubeA compares favorably
against optimal classical planning algorithms in experiments, but in contrast to
the optimal baselines, DeepCubeA doesn't guarantee to find optimal solutions. To
obtain a fair comparison, we want to evaluate DeepCubeA against several
suboptimal algorithms from the literature. For this evaluation we'll use
algorithms that are bounded suboptimal or improve their found solutions over
time, in order to come close to optimal solutions. In addition to Rubik's Cube
tasks, we will use tasks from Lights Out, n-puzzle and Sokoban.
Automatically Detecting and Fixing Errors in Planning Models
The performance of modern planning systems depends on many factors.
One important factor is whether the input planning tasks contain redundant information.
An example for this are unused action parameters. These are present
in many planning benchmarks and can result in many duplicate ground actions.
This thesis aims to fix standard benchmark sets using a validation tool developed within our lab and to run an
empirical analysis to test whether this improves the performance of existing planning systems.
Beyond Shortest Paths: Maximizing Rewards in Classical Planning
Planning is a fundamental aspect of artificial intelligence and involves devising
a sequence of actions to guide an intelligent agent from its current state to a
goal state. Classical planning typically seeks a cost-optimal plan, where actions
have associated costs, with the objective of minimizing the total cost of the
sequence. In practice, some problems are better addressed by maximizing
rewards associated with actions, spanning applications as diverse as computational
linguistics, power grid reconfiguration, and error-correcting code theory.
This project focuses on exploring the challenge of finding a reward-optimal plan or,
in a unit cost setting, the longest plan. For a more detailed description of the
project, see the attached document.
Visualizing Action Plans With Generative Machine Learning Models
Generative models are now powerful enough to generate realistic images and
videos from natural language texts (see e.g. Du et
al.). In this project we want to test whether
such deep learning models can be used to generate visualizations of action plans
obtained with AI planners. The goal is to generate visualizations that are easy
to understand for humans and that can be used to improve the plans.
Using LLMs to Convert Logic Formulas to Natural Language
Large language models (LLMs) such as GPT-4 can generate natural language text
that is indistinguishable from human-written text. In this project, we want to
explore whether LLMs can be used to convert logic formulas to natural language.
This will be useful for explaining the meaning of logic formulas to non-experts,
for example in the context of AI planning. For example, for the first-order
logic formula \forall x \exists y: on(x,y), the LLM should generate a sentence
like "For every object x, there is an object y such that x is on y". We will
focus on Description Logic formulas generated by the
DLPlan system developed within our
group.
Applying Contrastive Reinforcement Learning to Learn General Policies for Classical Planning Domains
Generalized planning asks for policies that solve multiple problem instances of the same domain rather than a single instance. Traditional symbolic approaches construct compact general plans or policies using domain knowledge and combinatorial search; more recently, learning-based approaches have attempted to learn policies that generalize across instances using supervised and reinforcement learning. Concurrently, contrastive representation learning has proven effective at learning robust, sample-efficient representations in RL for robotics domains. This project will explore whether contrastive RL objectives can facilitate learning of domain-general policies for classical planning tasks. For more info about this project, see this document.
Comparing Visual and Graph-Based Representations for Learning General Policies in Classical Planning Domains
Learning generalized policies for classical planning domains has traditionally relied on symbolic or graph-based representations that explicitly encode the relational structure of PDDL states. Graph neural networks (GNNs) have shown particular promise due to their ability to capture permutation invariance and relational reasoning, leading to policies that generalize across instances with varying object counts and configurations. On the other hand, deep reinforcement learning with visual observations has achieved remarkable success in complex domains like Atari games, robotics, and 3D navigation. Convolutional neural networks (CNNs) can learn powerful spatial features from raw pixels, and modern RL algorithms combined with visual encoders have solved tasks previously thought to require explicit symbolic reasoning. This raises a natural question: Can RL methods, using CNN encoders on image-based state representations, learn generalized policies that transfer across classical planning instances as effectively as GNN-based methods? Understanding the answer has both theoretical implications (what inductive biases are necessary for generalized planning?) and practical implications (can we leverage the extensive visual RL tooling for planning tasks?). See this document for more information.
Completed Theses
Discovering Human-Interpretable Value Functions for Classical Planning
It has been shown that generalized policies for classical planning can be discovered through supervised learning, by training a model to act as a value function, mapping planning problems to goal distance values. A policy can then be defined by taking the action that minimizes this distance function. While the resulting policies has demonstrated the ability to solve several classical planning benchmarks reliably, the underlying model architectures used are black-box in nature. This work evaluates different approaches for extracting human-interpretable representations of the behaviors learned by these models. Two different methods are evaluated. The first involves distillation of internal model components into mathematical expressions. The second method involves using vector quantization to compress embedding vectors to a fixed set of codes, enabling interpretability by observation of how these codes are created and transmitted throughout the model. The results show that the degree to which human-interpretable policies can be discovered depends on the difficulty of the planning problem being solved. For simpler problems, the learned policies can be reliably explained and statements can be made confidently about whether the policies generalize beyond the training set. However, as the difficulty of the problem increases, simpler-to-understand behaviors either fail to capture the required domain knowledge, or harder problems are solvable at the cost of reduced interpretability. Some general characteristics of the learned behavior can be observed, opening up for future work on how to exploit these more efficiently.
Learning Partial Policies for Intractable Domains on Tractable Subsets
Viktor Carlsson
Master's thesis, August 2023. Download:(PDF)(DiVA)
An important objective in generalized planning is to find general strategies that allow for efficiently finding a goal-achieving action sequence for any given planning problem from a class of problems over a common domain. Assuming that P != NP, such strategies do not exist in NP-hard, also referred to as intractable, classes of problems. However, partial strategies can be used to guide the search towards the goal. Partial strategies are challenging to find because they tend to overfit the training data. In this work, an intractable class of problems was simplified in such a way that the resulting class of problems became tractable and permitted finding a general strategy. These strategies only efficiently solve the simplified class of problems. However, these strategies are very compact and easy to understand. The general strategies are partial strategies for the respective intractable class of problems. In the experiments, it was shown that the partial strategies provide strong guidance for efficiently solving the intractable class of problems but without guarantees for efficiency. This work considers two classes of NP-hard problems: a version of a traveling salesperson and the Nurikabe puzzle. The problem of finding simplified versions of a class of problems is challenging and needs to be addressed in the literature.
Compact Representations of State Sets in State Space Search
Modern day technological advancements are moving at a rapid pace. In the field of Artificial Intelligence, algorithms are becoming ever faster and process larger amounts of data. These fast algorithms call for data structures that can store this processed data compactly. This premise also holds true in the AI subfield of planning. In the common planning approach of state space search, found states are memorized as to not unnecessarily revisit them. Research has put a big focus on improving the speed of state space searches which in turn leads to a lot of states being stored. A crucial bottleneck then occurs when memory runs out due to storing these large amounts of states. This is where this project, with its exploration of compact state set representations, comes into the picture.
This project's focus is on exploring memory usage for planning by state space search. More specifically, the project investigates compact state set representations for an A* state space search's closed- and open lists. It was hypothesized that the closed list would be the larger of the two which is why a focus was put on testing compact representations of that state set. Results from this project confirm this hypothesis as it is shown that the closed list is the largest and most critical of the two (although the differences between the two become increasingly small for strong heuristics).
Four different state set representations were tested for use as closed lists in an A* algorithm: Level-Ordered Edge Sequences (LOES), compressed LOES (cLOES), Binary Decision Diagram (BDD) and an explicit representation. A primary focus was put on exploring the LOES data structure because of the limited amount of research done on the data structure. Explicit representation was used as the main point of comparison with it being a very commonly used standard in state space search.
The results from this project show that LOES managed to lower memory usage significantly for large tasks when compared to the explicit representation. The lower memory usage did, however, come at the cost of speed with LOES being noticeably slower. Although less drastic, the same differences could be seen when comparing LOES to its compressed version, cLOES. Out of all the tested state set representations, cLOES was shown to be the most compact but also the slowest. Moreover, the results indicated that, even if most tasks didn't benefit from the additional compression provided by cLOES in comparison to normal LOES, the tasks that did, benefited a lot. Lastly, the BDD data structure gave more inconclusive results. The poor BDD results were seemingly caused by an unfit implementation for the closed list use case. The results did, however, suggest that BDD was faster but less compact than LOES for large tasks.
The different closed list state set representations were also tested with four different heuristics: blind, max, CEGAR and Merge-and-Shrink heuristic. A takeaway from these tests was that stronger heuristics resulted in fewer states being stored in the open- and closed list. Moreover, the closed states made up a smaller portion of the total amount states for the stronger heuristics. This smaller number of stored closed states made, as a consequence, the differences between the tested state set representations less pronounced. For large tasks, however, the closed list did get big enough to experience the effect of the efficient closed list implementations.
Conclusively, LOES and cLOES proved strong replacements to explicit representation. Especially in use cases where compactness is more critical than speed such as in embedded systems. Additionally, even though strong heuristics lessened the effect of efficient state set representations, there are still notable advantages to be found for big tasks where the closed list grows large enough.