Foundations of Artificial Intelligence (FAI) Group

About this page. To give you a rough idea of the kind of topics we offer, below we include an exemplary list of example topics that have been addressed in the past. The list is very much incomplete. This is just to give you an impression of the kind of thing students in our group do.

We always offer topics at all levels (BSc, MSc, Master Praktikum, Research Immersion Lab). Please write an email to Joerg Hoffmann if you are interested. In this email, please provide information about your background (course of study; FAI courses/seminars taken and final grades; other relevant courses and final grades), and explain in a few sentences why you are interested in working with FAI, and what topics you might be interested in. For an overview of our current main research lines, see our Research page.

Planning Algorithms:

• Using abstraction refinement to collect the label set defining the bisimulation approximation in recent Merge-and-Shrink lower bounding methods. In a nutshell, such approximated bisimulations are exact with respect to a subset of the planning actions (the labels in the state space graph), and the question is which actions we should choose to obtain good lower bounds at reasonable computational cost. Abstraction refinement collects these actions by iteratively computing abstract solutions and repairing the reasons why those fail when applied to the original problem.
• Learning bad action choices. In most prior works on applying learning to planning, the learning methods attempt to learn a characterization of good action choices. A major limitation of this is that, in complex domains (think "Rubic's Cube"), good actions are difficult to characterize and hence to learn. By contrast, even in such domains many action choices are very obviously bad. Thus the idea is to learn to characterize (a subset of) the bad choices instead, which later on serves to speed up the search for a plan by pruning away these choices. Main issues researched are (a) how to obtain suitable training data, and (b) which learning methods lead to good results in practice.
• Experimenting with automatic parameter tuning techniques to make the best out of learned pruning rules as in the previous item, in combination with all the other techniques that have been develop0ed in the planning community. Exploit the insights gained for the design of highly effective planner portfolios.
• Identifying new tractable fragments in red-black planning, a framework where a subset of state variables take the "delete-relaxed" (value-accumulating) semantics while the remaining variables take the regular (value-switching) semantics. Implementing a red-black search algorithm for an interesting intractable fragment, exploiting the previously identified tractable fragments for search guidance and cut-offs.
• Red-black state space search, implementing forward search for arbitrary (intractable) red-black problems via combining methods traditionally used for fully black (forward search) and fully red (relaxed planning graphs) planning.
• Efficient implementation of partially delete-relaxed planning with explicit conjunctions, without going via a compilation introducing artificial state variabls to represent these conjunctions. Instead treat them like "mutex relations" and adapt prior work on effective implementation of delete-relaxation heuristics.
• Learning good pattern collections: Pattern databases are a highly effective method to compute lower bounds on goal distance, however finding good patterns (variable subsets) to define them is typically way too costly to be done online. Learn good pattern collections for a domain offline instead, and just use the learned knowledge online, for free.
• Assemnbling state-of-the-art heuristic search algorithms for MDPs, and determinization-based heuristic functions, in a unified system and evaluating its efficiency on benchmarks from planning competition and simulated penetration testing.

General Game Playing Algorithms:

• Adapting planning techniques to play 2-player zero-sum games. Based on a simple extension of PDDL to describe this kind of game, extend the preprocessing to handle that extended language, and replace the A*-style search with an alpha-beta search.
• Automatic extraction of evaluation functions in general game playing. Exhaustive search algorithms like aplha-beta pruning must cut-off the search at a limited depth of the search tree. Evaluation functions for assessing the quality of these positions, from a player's point of view, are typically written by human experts. In general game playing, we need to do so automatically. The basic idea is to adapt heuristic functions from Automatic Planning; it does not seem feasible to compute very accurate estimates that way (estimating "goal distance" is quite different from "evaluating a game position"), however it is possible to identify when "shit happened", ie the opponent just did something very bad for us, like, taking out our queen in Chess.
• Automatic learning of evaluation functions in general game playing: Like above, but using Machine Learning techniques to derive the evaluation functions from experience.

Search Space Analysis:

• Designing search space features in heuristic search based planning systems, and measuring their correlation with planner performance.
• Analyzing the search space topology of the delete relaxation heuristic h+: That topology is known for the planning competition benchmarks up to 2004 only. How do the more recent benchmarks behave?
• Understanding the power of explicitly represented conjunctions: How many conjunctions do we need to compile into a planning task in order to render the delete relaxation heuristic h+ perfect? For which benchmark domains is there a polynomial upper bound on that number? Can we characterize that number in general, or at least identify sufficient criteria for it to be small?
• In a 2-player game, a "trap for player B" is a part of the game-positions space in which player A has a winning strategy; the "quality" of the trap can be assessed in terms of its size (number of different positions it contains), its depth (length of the winning strategy), etc. Intuitively, sampling-based algorithms like UCT are bad at recognizing large traps. How many traps, of which sizes, appear in the standard games used for benchmarking in the general game playing competitions?
• Desingning controlled benchmarks for simulated penetration testing, by identifying network structures for which the exact goal probability can be computed easily, and systematically varying the parameters.

Compilations:

• Translating single-player games described in the Game Description Language (GDL) into the planning language PDDL, and checking whether the solvers obtained this way are competitive with game-playing programs.
• Encoding multi-agent path planning into PDDL, running off-the-shelf planning algorithms against the state of the art heuristic search algorithms.
• Automatically "splitting up" the action schemas in a PDDL domain file, into a sequence of smaller schemas with less parameters. This reduces the number of ground actions exponentially (in the size of the parameter-reduction), and thus has the potential to dramatically improve performance. Domain optimization methods were desgined to choose automatically which splits to make.
• Checking whether any given action is "undoable", i.e., whether after applying it to any state we can always find a sequence of actions that leads back to that state. Compilation of that problem as planning under initial state uncertainty where the "uncertainty" serves to encode the set of states we could potentially apply the action to.