Student Project Topics
These topics are intended for the consideration of students interested
in the applying a PhD, BCS honours project, or college summer scholarship.
Project descriptions are very general, and intended to be made more precise
depending on students interests and the scope of the project.
For information about how to apply, see:
If you are interested in any of these possibilities, and in working
in the area of AI planning, a good first step is to contact me.
Projects in Automated Planning
Planning is a branch of AI concerned with automating the reasoning
that goes on in formulating plans, in the sense of a series of steps to
be taken, each of which has some effect on the state of (a highly abstract
model of) the world, so as to bring about some desired end state.
As a prototypical example, one may take single-player games ("puzzles")
such as the Freecell card game or the old Rubik's Cube. Possible
applications of automated planning methods (aside from solving puzzles)
are many and diverse: examples include airport ground traffic control,
computing genome edit distances, testing protocols for logical flaws,
or controlling a printer.
The aim of research in planning, as in many other branches of AI, is
to construct domain-independent ("universal") solutions for this kind of
problem. That is, rather than solving each application problem
individually, a general AI planning system should be able to solve any
one of them, provided a formal specification of the problem as input.
Several approaches to achieving this have been tried, such as different
variations of search, or recasting the problem as another kind of general
reasoning (e.g., a CSP, or logical deduction). Yet, efficient general
automated planning remains a challenge.
Within the area of AI planning, a wide variety of projects are possible,
ranging from highly theoretical to practical, implementation-oriented,
and anywhere in between. For example:
- Factored planning
- Factored planning methods aim to achieve efficiency by decomposing
the planning problem into parts, such that each part has only limited
interaction with the others. Plans for each part can then be computed
(mostly) independently, with a possible exponential saving in
computational effort. However, existing factored planning methods
achieve this splendid efficiency only in very limited circumstances.
For further details, see the recent
paper by Eric Fabre, Loig Jezequel, Sylvie Thiebaux and myself.
- The usual factored planning method decomposes the problem into
a tree structure, which is processed in a two-pass scheme, i.e.,
each node of the tree, which represents a part of the original
problem, is processed only twice: each time, the node collects
some information from neighbouring nodes that have already been
processed, adds some of its own, and passes on the result to other
neighbour nodes.
This, however, is not the only way of organising the computation
of a solution. In particular, in the two-pass scheme it is often
the case that the amount of information that needs to be passed
between neighbour nodes grows very large. It is possible that
using more passes, with less information exchanged each time, may
be more efficient.
A possible project is to implement and compare such different
variants of the factored planning method. Existing software provides
a lot of the required infrastructure.
- Theoretical analysis of our factored planning method has revealed
some conditions that are sufficient to guarantee that it runs in
polynomial time. But these conditions are not necessary: we know of
some problem domains where the method runs in polynomial time
(and some where it appears to run in polynomial time)
even though these conditions do not hold.
A possible project is to investigate these cases, with the
aim of formulating a new sufficient tractability condition that
covers them. My current idea is that this may be possible by looking
at the structure of automata (which are used to represent information
about parts of the problem), and the conditions under which the
size of the product of two automata is linearly bounded. I would be
particularly interested in seeing if this can be connected to the
idea of using graph grammars to define restricted classes of planning
problems (see my ICAPS 2008 paper).
- Proving planning problems unsolvable (efficiently)
- Research in automated planning is mostly focused on the problem
of finding a plan: indeed, many planners are "sound
but incomplete", meaning that when they do find a plan, it is a
valid plan, but when they don't find a plan, one cannot know if that
is because no plan exists or simply because the planner failed.
However, the problem of deciding plan existence, i.e., to answer the
question "does the problem have a solution?" is important
in some contexts. (In particular, it is closely related to the model
checking problem.)
Existing methods for answering this question are all based on
exhaustive search, in one form or another, that is, one tries,
systematically and exhaustively, in all ways to find a plan, and if
no plan is found one can conclude that none exists. Such methods are
somewhat unsatisfactory: they scale up very poorly (in particular,
the difficulty of proving plan non-existence this way is related to
the size of the problem, but not to how complicated the reason for
non-existence is) and they fail to provide a succinct and understandable
explanation for the failure to construct a plan.
As an alternative, I am looking at methods that explicitly search
for a proof of plan non-existence. While I have some ideas for how
this can be done, they have yet to be put into practice. Thus, this
is (at the current stage) mostly an algorithm design and implementation
project.
- Incremental lower bound functions
- A lower bound function is a function that takes a (planning)
problem and return a lower bound on the cost of any solution (plan)
for the problem; in other words, it proves that we cannot do better
than f(P). The closer the bound is to the true optimal cost,
the better is the function. However, a stronger lower bound is
typically also more expensive to compute. I'm interested in
incremental lower bound functions, i.e., functions that can be run
for a variable amount of time and return increasingly better (i.e.,
higher) bounds the longer they're allowed to run. One way to design
such a function is by "iterative de-relaxation": solve a relaxation
of the problem (optimally); if the relaxed solution is not a real
solution, use it as a guide to selectively "un-relax" the relaxation,
and repeat. I created one incremental lower bound based on this idea,
using the common planning delete relaxation
(see the workshop paper for details).
But there are other possibilities, not least using abstraction. Trying
them out will involve some theory, implementation and experimentation.
New projects based on student's ideas can of course also be considered.
Various Combinatorial Optimisation Problems
Although research in AI planning aims to construct fully general,
domain-independent, planning systems, systems are often evaluated
and compared by testing them on a collection of benchmark domains,
accumulated over time by the research community. Many of these
benchmarks resemble well-known combinatorial optimisation problems,
such scheduling/sequencing, allocation, etc., or at least contain
parts that do, but each also has its own peculiarities and tweaks.
For a majority of benchmark domains, it is known that finding optimal
solutions is difficult (NP-hard or worse) while just finding any
solution is relatively easy (there exists efficient, and often simple,
domain-specific algorithms), providing further evidence that the
underlying problems encoded in these benchmark domains are, at heart,
about optimisation.
This project consists in picking up one (or more, depending on
project time frame, problem difficulty, etc) of the commonly used
planning benchmark domains that encode optimisation problems, and
attack the underlying problem using whatever methods/tools seem most
suitable, including for example LP/MILP, CSP/COP/SAT, local search
methods, or anything else. The aim is to obtain a better understanding
of the problems that underlie planning benchmarks -- how hard are
they, in a practical, rather than complexity-theoretical, sense, and
what instance parameters determine that hardness? how well do
domain-independent planning systems compare, in terms of effectiveness
and solution quality, to a domain-specific solution? -- but also to
learn something about the different combinatorial optimisation
technologies -- how difficult are they to apply to a given problem?
which is more suited to what kind of problem?
Planning a Story
The plot (or narrative) of a story has some similarity with a plan, as
it is usually defined in classical AI planning. It is a sequence of
events, each of which can be viewed as an action that changes the state
of the world. For a story to be perceived as coherent and plausible,
the event sequence must be logically possible (i.e., preconditions
achieved before an action takes place) and connected by causes and
effects (i.e., each event contributes something to the story, by
setting the stage for later events; this corresponds to a notion of
non-redundancy in plans). The "goal" of a story, in this view, is the
end state that the story's author has in mind.
However, there more requirements on a narrative than on a plan: in
addition to being logically sound, it should be believable, and perhaps
also entertaining. One aspect of this is the believability of the
actions of characters in the story: the characters actions should not
only be possible, and be contributing to the overall goal of the story,
but should be perceivable as contributing to the goals that the
character has (which are not necessarily the same as the goal of the
story). This can be seen as an extension of the non-redundancy
requirement to parts of the story: each action done by each character
in the story should be motivated by (i.e., directly or indirectly
contribute to achieving) a goal of the character. Of course, goals of
a character can change throughout the course of the story, as they are
influenced by other characters, or events in the world around them.
But each such change of a characters goals must also have a cause.
Using the connection between narratives and planning, Reidl and
Young ("Narrative
Planning: Balancing Plot and Character", Journal of AI Research,
vol. 39, p. 217-268, 2010) created a "narrative planner",
by extending an traditional partial-order causal link planner with a
mechanism to enforce the extra constraint of respecting character
motivations. Their planner, however, is woefully inefficient: they
report that a tiny example problem, generating a story with just 14
events, took over 13 hours of CPU time.
On the other hand, an idea that has appeared in recent planning
research, and that has been put to good use, is problem compilations.
A compilation, in this setting, is an efficiently computable function
that takes a planning problem P belonging to one class of
problems (typically, a class that has some extra feature or complication),
and generates a problem P' that belongs to another class
(typically a simpler class, for which efficient planning methods
already exist), such that a plan for P' can be mapped back to
a plan for P. Compilations have been used to handle complex
action models (e.g., conditional effects) and goal conditions (e.g.,
trajectory constraints, "soft goals"), and much more. Even
certain planning problems with uncertainty (incomplete information)
can be compiled to the classical planning form (which deals only with
complete information problems), and solved more efficiently using
state-of-the-art classical planners.
Thus, the research question is: Can the extra requirement that
characters' actions are coherent with their goals be compiled away,
to produce a classical planning problem? If so, will solving the
compiled problem using current classical planners be more efficient
that specialised planners that incorporate this constraint? (The answer
to the second question of course depends on which those specialised
planners are. Hence another research question is how to adapt, e.g.,
current heuristic state-space search-based planners, which are at
the moment generally much more efficient than partial-order causal
link planners, to respect the constraint. Recent work on enforcing
non-redundancy in state-space search may be relevant to investigate.)