Foundations of Artificial Intelligence (FAI) Group


Home
People
Research
Projects
Software
Teaching
Student Projects
Publications
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 MergeandShrink 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 redblack planning, a
framework where a subset of state variables take the "deleterelaxed"
(valueaccumulating) semantics while the remaining variables take the
regular (valueswitching) semantics. Implementing a redblack search
algorithm for an interesting intractable fragment, exploiting the
previously identified tractable fragments for search guidance and
cutoffs.
 Redblack state space search, implementing forward search for
arbitrary (intractable) redblack problems via combining methods
traditionally used for fully black (forward search) and fully red
(relaxed planning graphs) planning.
 Efficient implementation of partially deleterelaxed 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 deleterelaxation
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 stateoftheart heuristic search algorithms for
MDPs, and determinizationbased 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 2player zerosum
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 alphabeta search.
 Automatic extraction of evaluation functions in general game
playing. Exhaustive search algorithms like aplhabeta pruning must
cutoff 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 2player game, a "trap for player B" is a part of the
gamepositions 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, samplingbased 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 singleplayer games described in the Game Description
Language (GDL) into the planning language PDDL, and checking whether
the solvers obtained this way are competitive with gameplaying
programs.
 Encoding multiagent path planning into PDDL, running
offtheshelf 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
parameterreduction), 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.