I teach a range of computer science modules, and supervise undergraduate and postgraduate project students.
I teach a range of computer science modules, and supervise undergraduate and postgraduate project students.
Course materials for all my undergraduate modules are available on KEATS.
Over time, I am recording lectures and tutorials in AI planning, given by myself and my others.
Here are the MSc projects I am offering in the academic year 2014–2015.
When writing a planning problem, it is possible to include a list of preferences that we would like a plan to respect, but are willing to forego if the preference simply cannot be met (we would prefer to stay in bed but get a day's work done), or if the cost of adhering to them is too high — the extra effort would make meeting the preference not net-beneficial. The planning domain definition language (PDDL) has language specifications for capturing preferences, written on the 'trajectory' of a solution plan. For instance, taken from the 'Trucks' benchmark domain:
(preference p1B (sometime-before (delivered package2 l2) (delivered package1 l1)))
(preference p4A (within 919.7 (delivered package1 l1))) (preference p4B (within 919.7 (delivered package2 l2))) (preference p4C (within 1813.7 (delivered package3 l2)))
(forall (?p - package) (preference p2A (at-most-once (exists (?t - truck ?a - truckarea) (in ?p ?t ?a)))))))
Or, in the Rovers Metric Simple Preference domain:
(:goal (and (preference g0 (communicated_soil_data waypoint7)) (preference g1 (communicated_soil_data waypoint3)) (preference g2 (communicated_soil_data waypoint0)) (preference g3 (communicated_rock_data waypoint8)) (preference g4 (communicated_rock_data waypoint6))))
(:metric minimize (+ (* (is-violated g4) 334.3) (* (is-violated g3) 76.5) (* (is-violated g2) 177.9) (* (is-violated g1) 116) (* (is-violated g0) 457.4) (sum-traverse-cost))))
The PDDL preference extensions are an elegant way of expressing preferences, but are not supported by many planners. In this project, you will look at 'compiling away' preferences, producing a model where extra dummy actions, and extra preconditions/effects, do the job of preferences – instead of them being stated explicitly, as above. Keyder and Geffner have shown that soft-goals, such as those above in the Rovers domain, can be compiled away. This project will carry on from there, producing a tool for compiling away a wider class of preferences (such as within, sometime and sometime-before). Several compilations are possible for the different preferences, so you will have the opportunity to explore the different possibilities, performing experiments to see encodings allow better plans to be found, in practice, given the planners available. You will also be able to explore the benefits and trade-offs of using a planner that handles preferences natively, versus using a planner provided with a compiled domain.
The tool, once written, will be open-sourced and made available online.
You will need to be comfortable with writing C++ code, and working with existing code to parse and support reasoning with planning models written in PDDL. Doing this from scratch, in another language, would take too long - the current codebase is circa 100k lines of code.
You need to be able to understand how Keyder and Geffner's compilation (link above) works. Your approach will likely build on these ideas.
Planning problems are defined by an initial state, a collection of actions, and some desired goals. The task of planning is to find a sequence of actions that, when executed, transform the initial state into one in which the goals are satisfied: a goal state. One of the key barriers to the scalability of planning to large problems is the size of the problem, for instance, in terms of how many actions are available, or how many goals need to be achieved
In this project, you will develop a 'wrapper' around planners, that attempts to solve a planning problem one goal at a time. For instance, if the original task is to reach goals [A,B,C,D,E] then your wrapper would call the planner five times:
Note that each goal is to be achieved as well as the one before it. This stops the planner from un-doing one goal in achiving the next.
This project has good potential for obtaining interesting research results. For instance, without modifying the planner: how best to order the goals — e.g. here, A,B,C,D,E might not necessarily the best order, other orders might give shorter plans. Or, you could explore making minor changes to a planner to allow it to e.g. plan to reach goal A, but to make sure that B,C,D and E are still reachable (even if, for now, the plan doesn't reach them).
If you don't know how to start one process from within another, and capture its output, this project is probably not for you: your code will need to run a planner, passing it some files; then read the plan it produces.
You need programming skills in a suitable programming language. Java, python, perl, C++ etc. would work. As all our planners are compiled to run on Linux, you will need to use something that works on Linux.
Planners are large systems, making use of a range of techniques to solve problems efficiently: different ways of exploring the space of possible plans, different ways of estimating how far given choices are away from the goal, and so on. One of the key aims of planning systems is that they are domain-independent, so the combination of techniques used is chosen to maximise overall performance. But, if one is really concerned about just one problem (e.g. if one wishes to deploy planning in some application), then what one wants is an automated means of picking the best techniques from those implemented.
In this project, you will apply the 'ParamILS' parameter learning system to the planner OPTIC. ParamILS is an 'automatic algorithm configuration system' that evaluates many different parameter settings for a problem solving system. To apply ParamILS to a planner, ParamILS needs to be told which parameters to change. As such, your task in this project is to detail the parameters available to the planner OPTIC. This will involve:
Once ParamILS is working with the planner, you will evaluate how well its performance can be tuned to a range of different tasks.
ParamILS is a command-line application that runs on linux. As such, for practical reasons, you must not be fazed by this.
Planning problems are defined by an initial state, a collection of actions, and some desired goals. The task of planning is to find a sequence of actions that, when executed, transform the initial state into one in which the goals are satisfied: a goal state. To find such a plan, a planner uses search: at a high level, it incrementally visits more and more states, until it finds one which satisfies the goal. The main bottleneck in planning is typically the memory used in storing these states:
In this project, you will implement and evaluate different data structures for use in planning. There are three important considerations for the data structure storing memoised states:
We also need some sort of efficient way of storing states with their associated additional data:
There are various data structures described in the literature and online, that you could use for either of these. Whichever you use, you will perform 'before-and-after' testing: compare your approach to a naïve implementation, using e.g. maps as described above.
This project must be implemented in C++: all the planners that could make use of the data structures to be developed, are written in C++. For portability, your data structures should be written as C++ templates, that can be instantiated with different classes. (This is particularly important, as as well as making your code portable to different planners, it frees you up from needing to necessarily work with planner source code in your project: you can make your own test classes to represent states, associated data etc.)
I'll start booking in undergraduate project students in October. I haven't decided what projects I'm offering yet, but here are my ideas from the academic year 2014-2015 - I'll probably remove some and add some others, and as usual am interested in hearing from students who have good ideas of their own.
This week sees thousands of new students at King's trying to find their way around the Strand campus. Due to the vagueries of the laws surrounding planning permission, the layout that has evolved over time could be described, generously, as 'idiosyncratic'; or, less so, as 'a chuffing maze'. Conveniently, though, navigation beacons, disguised as wireless access points, have been installed throughout the buildings; and to tell these apart, each of these has a unique ID (a MAC address). In this project, you will write software someone can use to find where they are on campus, based on which wireless access points are visible, and the signal strength to each.
The basic components of the project are:
LOST1: Data mining
There are so many techniques for wireless location sensing, that in fact you could do the entire project on this. For instance:
LOST2: Interact with a user
Alternatively, having developed basic wireless location-sensing techniques, you could do something interesting with the data. For instance:
As gathering wireless access point data (for the basic requirement) is somewhat mundane, I am happy to take two students on this project (one working on LOST1, another on LOST2) and for you to share the data you have collected.
You can use your choice of platform and programming language. To gather data, it should be able to run on something with a wireless connection. If you're aiming for the user-interface direction, then you might want to consider using a mobile device.
To have a look at some data I gathered from level 6 of the King's building, have a look at this spreadsheet. I walked at a steady pace from north to south along K6, with my laptop scanning for wireless networks every 3 seconds. The columns denote wireless access point MAC addresses; the cells record the signal strength (up to a maximum of 70). As you can see, there's a strong relationship between where one is on K6, and what ths signal strengths are. (I got this data using a Linux laptop and a few lines of code - you're welcome to have this.)
Videos of lectures and technical talks are an increasingly popular way of connecting with the public and willing learners. A common format is:
These then need to be combined together, for instance:
In this project, you will develop a system for combining the raw materials of a video talk, into a final product. The key aspects are:
In addition, it would be nice if:
As with most projects, there's a good deal of scope here for creative flexibility. The aim is not to make a full-scale video editing package, but something tailored to technical talks that can be used to quickly turn the materials recorded in the lecture theatre into a finished product.
You need to be able to program. Java is a reasonable choice, in which case look at JavaFX Media for being able to e.g. play video files in Java without too much fuss.
If you have an idea for your own project, write up a summary and send it to me. Key points: