Undergraduate modules

Course materials for all my undergraduate modules are available on KEATS.

Video Lectures and Tutorials

Over time, I am recording lectures and tutorials in AI planning, given by myself and my others.

MSc Student Projects

Here are the MSc projects I am offering in the academic year 2014–2015.

[AICM01] Compiling away trajectory preferences in planning problems

Introduction

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:

  • Some time before we delivered package 2, we delivered package 1:
              (preference p1B (sometime-before (delivered package2 l2)    (delivered package1 l1)))
  • Ideally, we want to have delivered these packages by this time:
              (preference p4A (within 919.7 (delivered package1 l1)))
              (preference p4B (within 919.7 (delivered package2 l2)))              
              (preference p4C (within 1813.7 (delivered package3 l2)))
  • (Roughly) For each package, we only store it in each truck once:
              (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:

  • At the end, we prefer to have completed various science-gathering tasks:
        (: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))))
  • However, whilst these each have a defined cost benefit, we also must account for the overall distance the rover travels — the plan quality trades off preference satisfaction against this:
        (: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))))

Project

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.

Initial reading

Pre-requisites

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.

[AICM02] Goal serialisation in AI planning

Introduction

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

Project

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:

  • Call the planner with the task of planning from the initial state, to reach the goal 'A'. This reaches some state (call it S1) in which the goal 'A' is satisfied.
  • Call the planner with the task of planning from S1, to reach the goals 'A' and 'B', reaching a state S2;
  • Call the planner with the task of planning from S2, to reach the goals 'A', 'B' and 'C', reaching a state S3;
  • Call the planner with the task of planning from S3, to reach the goals 'A', 'B', 'C' and 'C', reaching a state S4;
  • Call the planner with the task of planning from S4, to reach the goals 'A', 'B', 'C', 'D' and 'E'.

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).

Initial reading

Pre-requisites

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.

[AICM03] Learning good parameters for the planner OPTIC

Introduction

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.

Project

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:

  • For simple 'yes/no' parameters (use this technique, or not), handing these to ParamILS;
  • For continuous parameters (e.g. numeric values in some range), exploring how to best choose values in this range;
  • Noting the dependencies between any parameters -- e.g. 'if parameter X is set to 'no', then parameter Y is ignored'. This allows ParamILS to only consider the parameter settings that are meaningful.

Once ParamILS is working with the planner, you will evaluate how well its performance can be tuned to a range of different tasks.

Initial reading

Pre-requisites

ParamILS is a command-line application that runs on linux. As such, for practical reasons, you must not be fazed by this.

[AICM04] Memory-efficient state memoisation for forward-chaining AI planning

Introduction

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:

  • To stop search from going around in circles (visiting the same states repeatedly), each state that has ever been seen, is stored – memoised – and once visited once, can never be visited again.
  • To guide search, each state has several associated pieces of information, such as a heuristic value, or the 'parent' state from which each state was reached. These, too, need to be stored. But, for flexibility, this information cannot go inside the state itself, as that would fix what sort of information could be recorded.

Project

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:

  • At a low-level, a state is an array of integers, of a fixed size. If we take care over memory management, we can represent a state by its pointer to this array; or we could put several states into one large array, and represent a state by its index into this large array. (i.e. where its array starts). The latter might be preferable, particularly on 64-bit systems, as points are 64-bits, but an array index can be 32-bits.
  • The planner needs to be able to use the memoised states data structure to find if a state has been seen before. Thus, typically, some sort of hash set, or binary search tree set, is used: these are both much faster for this task than e.g. iterating over a list of states.
  • The data structure for the memoised states needs to be dynamic: states are repeatedly added to it, during search.
  • The data structure for the memoised states needs to be memory-efficient. For instance, each node in a binary search tree has two pointers (one to the left, one to the right), as well as storing the state itself (a pointer to it, or its ID). If the tree is balanced, then testing whether a state is in the search tree is O(log(N)) where N is the number of states in the tree. This is time-efficient, but if the pointers and the state are 32-bits in size, this means two-thirds of the memoised states data structure is taken up with storage overheads (the pointers) rather than the actual state.

We also need some sort of efficient way of storing states with their associated additional data:

  • As data is associated with each state, this motivates an associative data structure, e.g. a hash map, or binary search tree map, where the keys are states, and the values are associated data.
  • But, as before, one needs to be careful of storage overheads. If we actually added an extra int variable 'h' to the state (which we cannot do) that would use 32-bits of memory per state. If we instead have a binary-search-tree map, from states to their 'h' values, this uses at least 96-bits of memory per state: two points, plus the 32-bit h value. (In fact, it will use more than this, as there is an allocation overhead for the object that represents a BST node - giving a total space usage of around 160-bits to store this 32-bit variable, associated with a state.)

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.

Pre-requisites

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.)

Undergraduate Projects, 2015–2016

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.

Last year's ideas

[LOST1, LOST2] Help! I'm lost somewhere on the Strand campus

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.

Overview

The basic components of the project are:

  • A means of recording wireless access point data. For instance, the user should be able to walk at a steady speed on a known trajectory (e.g. south to north on level 6 of the King's building), and the software will continuously scan for wireless access points along that trajectory.
  • A approximate means of establishing the user's current position, using previously gathered wireless access point data. This will be achieved by comparing the user's current wireless access point visibility, to the recorded benchmark data, and reporting the most likely position. This could be done in many ways - there are several published and documented techniques, look up 'wireless geolocation' or 'wireless location sensing' etc. At a basic level, anything that is near enough will suffice.

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:

  • Work with data mining tools such as WEKA, to build different models for determining location.
  • Combine wireless network scans of each floor of a building, and the stairwells, to provide a 3D route-map.

LOST2: Interact with a user

Alternatively, having developed basic wireless location-sensing techniques, you could do something interesting with the data. For instance:

  • Where TF am I? Add landmarks to the wireless access point data (e.g. 'outside Safra'), give the user a description of where they are.
  • I give up, where's the bar? Direct the user how to get to the waterfront, from their current location. Or to other locations on campus. (Except maybe the Norfolk building, or we might not see them again.).
  • Which one is Dumbledore's office? Add highlights from the self-guided Strand campus tour to the data, so that to the college can have a tour-guide app on their tablet.
  • I can has Internet plz? Point the user towards their nearest location that offers a better signal strength than where they currently are.

Collaboration

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.

Other notes

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.)

[VIDEO] Video Compositing for Lectures and Technical Talks

Introduction

Videos of lectures and technical talks are an increasingly popular way of connecting with the public and willing learners. A common format is:

  • A video feed of the speaker, recorded using a camera (such as a DSLR). These might be in e.g. 20 minute segments, rather than being one continuous video.
  • A microphone recording of the speaker, recorded e.g. using a lapel microphone or high-quality off-camera mic.
  • A slideshow (e.g. in powerpoint format), which may itself contain animations or video clips. (For best quality, this isn't recorded with a camera.)

These then need to be combined together, for instance:

Project

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:

  • Allowing multiple input videos to be used, providing a convenient interface for positioning these with respect to the audio track (to make sure they are in sync)
  • Allowing the timing for the slides to be specified: i.e. the times at which to move onto the next slide.
  • Supporting different layouts - e.g. speaker in the bottom left, speaker in the bottom right

In addition, it would be nice if:

  • Sections of the talk could be cut out
  • A 'virtual laser pen' could be used to point to various parts of the screen -- like one would with a real laser pen. (As noted above, as the slides are not recorded with camera, the real-life laser pen dot the speaker may have cast on the screen doesn't make it to the final recording.)

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.

Other notes

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.

[YOUR] Your own idea

If you have an idea for your own project, write up a summary and send it to me. Key points:

  • Think 'basic implementation plus extensions': just like all the ideas higher up on this page. You probably have a grand idea, but what would be the most basic acceptable version of the project that would still be interesting, and could be done in one term by the average student?
  • You should be able to quite clearly articulate what the basic idea would involve: how much code, what languages or APIs, etc. If you don't, carry on thinking.
  • The basic idea should take one term, or slightly less. This ensures you can actually get a project out of your work. The second term would be spent extending the idea. to get you a better mark.
  • For the avoidance of doubt – it has to involve programming. (This a requirement of the project module, not just me.)