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.
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. New projects based on student's ideas can also be considered.
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?