Student Project Topics

These topics are intended for the consideration of students interested in the applying a PhD, honours project, or college summer scholarship. Some 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:

The College Masters and PhD programs (see also ANU information about PhD studies).
The College honours program.
The College summer scholarship program.

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 returns 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 ICAPS'12 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.

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). 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. However, it is also possible to compile the narrative planning problem into a classical planning problem, and solve it using any classical planner. (This is also much more efficient than Riedl &: Young's planner.) The compilation is described in a recent research note ("Narrative Planning: Compilations to Classical Planning", Journal of AI Research, vol. 44, p. 383-395, 2012).

The study of compilations revealed that there are many limitations to the current narrative planning model: for example, it does not allow for characters that make mistakes or fail to achieve their goals, or for characters' state of knowledge. Perhaps some of these limitations can be removed by developing more comprehensive compilations. This is a topic for future research. At the same time, however, the compiled problems are already somewhat difficult for a classical planner to deal with (even when not very large), and will only become more so as more complications are added to the model. Thus, another question to explore is why these compiled problems are so difficult for current planners, and if that can be remedied by changing either the compilations or the planners.

Computing Optimal Genome Edit Distances via Heuristic Search

Comparison of the arrangement of genes in mitochondria or chloroplasts is a tool used in determining the evolutionary history of life on Earth. One way to measure similarity between genomes is by their edit distance: the minimal (weighted) sequence of rearrangement events needed to transform one genome into another. An edit distance metric is defined by a set of edit operations (and their relative weights). While polynomial-time algorithms for calculating the optimal edit distance are known when the only operation considered is inversion, no such algorithm is known for more general sets of edit operations, such as the commonly considered inversion, transposition and transversion operation set. The genome rearrangement problem under these operations (and, indeed, under many other edit operation sets) is naturally formulated as a search problem. Thus, we can try to solve it optimally using optimal informed search algorithms like A*, together with admissible heuristics. However, the genome edit distance problem challenges existing heuristic search methods in ways that other puzzle-type problems (which are often used as benchmarks in research into heuristic search) don't. A* search, even with state-of-the-art admissible heuristics such as pattern databases, does not scale up to solve problems as large as we would like. The next step in this research project is to examine more advanced optimal search enhancements, such as symmetry reduction, partial expansion, and others.

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?