Projects 2006-2007

Group ID Supervisor Project title
gp06-nza Natasha Alechina Animation of graph algorithms
gp06-nhn Henrik Nilsson Dynamic Digital Photo Album mk II
gp06-pxb Peter Blanchfield Implementing an on-line alternative to the Monopoly Game
gp06-tjb Tim Brailsford Virtual Molecular Biology Lab
gp06-acc Anthony Cook Robotic Arm use in a Robotic Observatory
gp06-nxg Neil Ghani Game Theory
gp06-gmh Graham Hutton Asteroids
gp06-bnk Boriana Koleva Software for Creating a Museum Visit Montage
gp06-nxk Natalio Krasnogor A java-based artificial intelligence real-world problem solver
gp06-bai Bai Li Natural Interactive Game
gp06-bsl Brian Logan Energy Aware Routing for Ad-hoc Sensor Networks
gp06-cbb-sxp Camille Beyrouthy and Sanja Petrovic Meta-Heuristic Methods for a University Course Timetabling problem

Animation of graph algorithms

Group ID: gp06-nza

Supervisor: Natasha Alechina (nza)

Group mailing list:

Group members:

The purpose of the project is to write a program which helps students to visualise and understand graph algorithms, such as:

The user of the program should be able to input a graph, see the graph displayed, and see an animation of the selected algorithm on the input graph together with some additional information e.g. a gueue of vertices to be processed.

Dynamic Digital Photo Album mk II

Group ID: gp06-nhn

Supervisor: Henrik Nilsson (nhn)

Group mailing list:

Group members:

This project draws from a similar project I set last year. That project was quite successful, and pointed out some interesting avenues for further development that I hope this project will explore in depth.

First, here is the brief from last year (slightly edited):

My digital photo collection is in a bit of a sad state, and I suspect I am not alone. It basically consists a large number of photos stored in sequentially numbered files, subdivided into directories named after the date at which the photos were transferred from the camera to the computer. As the chronological order is maintained, it is not impossible to locate images, but it does take time. And quickly finding all photos relevant to a particular audience, say photos of people from a particular set of friends, or photos from a particular place, is not really feasible. Wouldn't it be great if one could create a photo album containing, say, all pictures of nieces and nephews with just a few clicks and a bit of typing, and if this album then was kept up to date automatically as further images of nieces and nephews are added to the collection of photos?

The objective of this project is to create tools to do something along these lines. JPEG image files do not only contain the actual image data, but also information about the image, such as when it was taken. Additionally, it can contain comments about an image. These can be used to store a caption and indexing terms. Thus, assuming that images have been properly tagged, it would be possible to create dynamic photo albums by specifying search criteria (e.g. certain index terms, certain words in a caption, a range of dates) and sorting criteria (e.g. chronological).

Two tools needs to be created. The first is the "Tagger". This should support adding and editing indexing terms (both pre and user defined) and captions to JPEG images stored in a user-definable set of directories. To facilitate consistent indexing, a small "database" of indexing terms should be maintained.

The second tool is the "Dynamic Album". This is used both to define albums through search and sorting criteria, and to browse defined albums. The search criteria should include matching indexing terms, looking for keywords in captions, dates and date ranges, and logical negation, conjunction and disjunction of these. Sorting criteria should at least include chronological. For displaying the images, EXIF size and orientation information should be taken into account to automatically scale and rotate images. Defined captions should obviously be displayed along with the images.

It should also be possible to export albums in a format that would be accessible over the web. The simplest scenario is to export a simple snapshot of an album by copying all images in the album to a separate directory, possibly reducing their resolution to make them more web friendly, and then generate a simple static HTML web page that shows all the images along with their captions. A more ambitious approach would be to export the entire dynamic album collection in the form of a dynamic web page (using Java script or some similar technology). That would effectively mean that the "Dynamic Album" is a simple, graphical, domain-specific language for creating photo albums, which then gets compiled into "low level" code such as Java script.

The group last year decided to focus on novice users, meaning that a lot of effort went into designing a really nice user interface, and that some of the more advanced features hinted on above were judged to be too advanced for the intended audience. Also some interesting ideas that did emerge during the project were not explored for similar reasons.

This time, the focus is going to be on an expert user, and the overall objective is to develop a sophisticated tool for making dynamic albums available over the web.

You can think of this in the following way. A visitor to the site will encounter a page with links to a number of dynamic albums. When he or she enters one of the album pages, a "canned" database query that defines the album in question is executed. The result is a set of images matching the query that is displayed to the visitor, along with captions for the images. Of course, if the visitor comes back to the same album a different time, the set of images he or she sees may be different since images may have been added or deleted from the underlying database, or since their classification may have changed.

The central aspect of this project is thus the tools and machinery for setting up and maintaining such a site. In particular:

While a nice and convenient user interface is a good thing, solid underlying design and functionality is more important here. For some aspects of the project, a simple textual user interface could even be enough. For example, in a pinch, one could imagine that albums are defined through a textual query stored in a file, even if that's not ideal.

Hint: the programs "rdjpgcom" and "wrjpgcom" from the Independent JPEG Group, and their source code, might be a good starting point for getting to grips with tagging JPEG images.

Implementing an on-line alternative to the Monopoly Game

Group ID: gp06-pxb

Supervisor: Peter Blanchfield (pxb)

Group mailing list:

Group members:

The game should maintain the basic principles of Monopoly - be a family game involving trading some form of property. It would be designed to involve particularly parents to get involved in the game but must also retain the interest of the younger members of a family. The game must however be sufficiently different from Monopoly not to suffer any copyright issues. Previous experience has shown that peoples answer to this takes them towards a version of "Warcraft" - which would not be suitable for whole family use - or Simcity/the Sims. In both cases there are great dangers from infringing copyright on these other products.

Virtual Molecular Biology Lab

Group ID: gp06-tjb

Supervisor: Tim Brailsford (tjb)

Group mailing list:

Group members:

This project involves the creation of a simulator of apparatus that is widely used in the molecular biosciences, which will constitute a "Virtual Laboratory" for use in training undergraduate biologists. This laboratory will allow students to design and carry out investigations in a way that is not possible with the constraints on time and equipment of most undergraduate courses. Each of these simulations should allow the user to carry out a simulated experiment using their own "samples" (i.e. data files representing biological material such as a protein, DNA, or human tissue). The results of these experiments will be further files which may in turn be used in other virtual experiments. In addition, the experiment will often generate some visual result which the user may store and include in their notebook in the same way as they would for a conventional experiment. The main techniques that will need to be simulated is that of the gel electrophoresis of proteins and DNA (see the Wikipedia entry: for some details about this).

Robotic Arm use in a Robotic Observatory

Group ID: gp06-acc

Supervisor: Anthony Cook (acc)

Group mailing list:

Group members:

Telescopes inside observatories must be kept in a clean environment as any dust or dirt that gets blown onto the optics causes the image quality to deteriorate. Dust reduction can be done in two ways, firstly by placing a cover or shade over the big lens end of the telescope when it is not being used, and secondly by sweeping dust off surfaces when the telescope is not being used. For remote unmanned observatories this is especially a problem, however lessons can be learnt from robotic arm use in other applications e.g. the space shuttle.

We have a couple of robotic observtaories on the roof of the Jubilee Campus library. Your task will be to develop a system to work in conjunction with a Movit Robotic arm to:

  1. pick up and place a dust shield over the end of the telescope, when it is not in use. You may move the telescope or move the robot arm, or both in order to achieve this task.
  2. remove and store the dust shield prior to the telescope use.
  3. periodically to pick up a very light weight mop or brush and to sweep this across surfaces in a systematic way so as to reduce possible dust that can be blown up from the floor by wind.

The project falls nicely into two parts: the dust shield docking and undocking, and the periodic "spring cleaning" of dust.

Initially a user interface needs to be constructed to demonstrate command and control of the robotic arm (and indeed to position the telescope) manually. However use of image output from CCTV cameras inside the dome can be used to help position the tools automatically as the project develops.

3D positional information can be determined from the telescope or robotic arm altitude and azimuth etc or by stereo/perspective positional measurements from the internal CCTV cameras.

There is a fair amount of leniency with this project as you get to decide what tools to use and indeed can improvise your own.

Game Theory

Group ID: gp06-nxg

Supervisor: Neil Ghani (nxg)

Group mailing list:

Group members:

This project concerns the development of an implementation of a board game such as Connect4 or Scrabble. The ultimate goal is to produce a piece of software which is both fun to play and which can beat a human opponenent. Thus, in addition to producing a good interface, students will also have to understand the algorithms which allows a computer to decide which move to make and how to efficiently store and search a data structure. Extensions could involve a distributed version allowing the game to be played over the internet.


Group ID: gp06-gmh

Supervisor: Graham Hutton (gmh)

Group mailing list:

Group members:

Description: Asteroids is an arcade game that was produced by Atari in 1979, and went on to become one of the most popular games of all time. The aim of this project is to implement a version of asteroids that is as close to the original as possible in terms of both look and gameplay. The project will involve learning about vector graphics, and utalising some basic trigonometry and physics.

Software for Creating a Museum Visit Montage

Group ID: gp06-bnk

Supervisor: Boriana Koleva (bnk)

Group mailing list:

Group members:

The idea of this project is to develop software that enables school-childern or families to capture information about a visit to a particular place of interest (like a museum or historical site) and then assemble such information into a digital montage on the experience. Further information is available here.

A java-based artificial intelligence real-world problem solver

Group ID: gp06-nxk

Supervisor: Natalio Krasnogor (nxk)

Group mailing list:

Group members:

XXI centurey technology, science, industry and comerce rutinely rely on solving large and complicated problems. Many times the solutions to such problems are afforded by AI methodologies and among them the most frequently used are Genetic Algorithms.

In this project the group will attempt to migrate the Memetic Algorithms Framework (MAFRA, ) to the latest version of Java. The migration process will involve familiarising with a state-of-the-art java based artificial intelligence real-world problem solver software framework. This solver implements the latest Memetic Algorithms, a sophisticated version of Genetic Algorithms, in an old version of java, namely, 1.1.8.

The goal would be to move the framework to the latest java version, refactoring some classes and creating new ones, re-engineering parts of the framework, debugging, testing and benchmarking the new software. The prospective students would proficient with Java object oriented programming, some AI, and software engineering (ideally the students will need to learn design patterns). Another goal of this project would be to seek to build a GUI front end to the framework and to make use of the university compute cluster to distribute the computational load. This project is suitable for groups of between 3 and 5 persons and will work closely within the research project ChellNet (

Natural Interactive Game

Group ID: gp05-bai

Supervisor: Bai Li (bai)

Group mailing list:

Group members:

This project will develop a game system using natural interaction technologies. It will involve the use of Computer Vision techniques to detect and track human hand movement and Computer Graphics techniques to create game pieces that the human hand will be interacting with. It will also involve the use of Augmented Reality techniques so that the game can be viewed on a Head Mounted Display. Finally, the graphics, vision, and augmented reality systems developed will be integrated to create the game.



Energy Aware Routing for Ad-hoc Sensor Networks

Group ID: gp06-bsl

Supervisor: Brian Logan (bsl)

Group mailing list:

Group members:

There has recently been considerable interest in sensor networks -- dense wireless networks of simple computing nodes which collect and disseminate environmental data, e.g., for environmental monitoring and control in buildings or monitoring conditions in a rain-forest. Each node in the network is essentially a low-cost, disposable computer, with sensing, data processing and wireless communication capabilities. Sensor networks are ad-hoc in the sense that the positions of the nodes are often not known in advance; for example, in monitoring a rain-forest, the nodes may be dumped out of the back of an aeroplane flying over the forest.

A key feature of sensor nodes is that they are battery powered; when the battery runs out, the node stops working. Energy conservation is therefore key to the maximising the useful lifetime of the network. However conventional network routing protocols assume that the routers are continuously powered, and often perform poorly in sensor network applications.

The aim of this project is to evaluate the performance of an "energy aware" routing algorithm, such as that proposed by Shah and Rabaey. This will involve:

The network simulator can be fairly basic, e.g, it would be reasonable to assume that the nodes are to be deployed in 2D (e.g., a single floor of a building), and while some model of obstructions is required, detailed modelling of signal propagation is not. There should be several data collection nodes in each network generated, with the rest of the nodes being sensor nodes. The data collection nodes should periodically poll each sensor node for its data value, depleting the battery level in the nodes appropriately. Nodes could be coloured to indicate the battery life remaining in the node, and the links could also show the propagation of data in the network.

The Shah and Rabaey paper can be found here.

Meta-Heuristic Methods for a University Course Timetabling problem

Group ID: gp06-cbb-sxp

Supervisor: Camille Beyrouthy (cbb)

Co-Supervisor: Sanja Petrovic (sxp)

Group mailing list:

Group members:

This project concerns usning an approach known as meta heuristics to address the hard problem of academic timetabling. More details here.

Last updated 24 October 2006.