Group Projects: 1999-2000

Supervisor Project Title
Dr. Natasha Alechina Creature
Dr. Natasha Alechina Playing a game
Dr. Helen Ashman Map projections
Dr. Helen Ashman Markup language browser
Prof. Roland Backhouse Administration of conference programmes
Prof. Steve Benford Applications of a 3D flythough of our new building
Prof. David Brailsford Dynamic dinner parties with SVG
Dr. Edmund Burke Designing wooden railways
Dr. Peter Cowling A toolkit for team choice in fantasy football leagues
Prof. Dave Elliman Proving originality
Dr. Chris Greenhalgh Camera control in a virtual environment
Dr. Chris Greenhalgh Tools for collaboration in virtual environments
Dr. Leon Harrison A virtual library tour
Dr. Colin Higgins Modular on-line cursive script recognition system
Dr. Graham Hutton Pac-Man 2000
Dr. Graham Hutton Automatic processing of module feedback forms
Mr. Graham Kendall Visual tool to demonstrate ant algorithms
Mr. Graham Kendall Create artificial life
Dr. Brian Logan Tileworld in Java
Dr. Brian Logan Psychotherapy over the web
Dr. Mark O'Brien Geological strata
Dr. Sanja Petrovic Case-based reasoning software tool
Dr. Sanja Petrovic Decision support system for discrete multicriteria problems
Dr. Tony Pridmore A visual programming environment for image processing




Creature

Supervisor: Dr. Natasha Alechina (room B34)

Group mailing list: gp-nza1

Team members:

Project description:

There are lots of successful electronic pets: tamaguchi and the like. The basic idea of an electronic pet is cute animation plus display of dependency on the owner (the pet needs to be fed and entertained, it acts hurt or grateful depending on the circumstances).

In this project, you are required to write a similar "creature". It will run in its own window. It should be fun and/or useful to have around. It should interact with its environment in a non-trivial way. For example, you could concentrate on making it a good model of a living being (AI-style project). Or it could "live" in your browser and comment on the pages you are accessing and the time you spend browsing.


Playing a game

Supervisor: Dr. Natasha Alechina (room B34)

Group mailing list: gp-nza2

Team members:

Project description:

The project requires you to write a program which allows two people (or a person and a computer) to play the battleships game over the internet. The main challenges are: design of the application; taking into account eventualities like cheating; strategy for the computer player. (Actually, if you don't like the battleships game, you can take any other simple board game).


Map projections

Supervisor: Dr. Helen Ashman (room C37)

Group mailing list: gp-hla1

Team members:

Project description:

The aim of this project is to build and test an application which draws geographical maps. The application should be able to draw maps in at least one projection, namely the flat mapping, and preferably other projections (such as Universal Mercator).

As well as drawing maps, the application should provide features which allow a user to zoom in or out, pan, select area for closer look, plus other features that may be required.

The software should be written in a non-trivial programming language. Data is available from public sources online (e.g. CIA World Factbook).


Markup language browser

Supervisor: Dr. Helen Ashman (room C37)

Group mailing list: gp-hla2

Team members:

Project description:

The brief of this project is to design and implement a Web browser which will be able to parse and display HTML-like documents.

In the first stage, the group will develop an HTML browser, which parses and displays HTML. This browser should only support the basic HTML tags, perhaps tables and frames as well, but not active content (such as Java applets) or forms. Also, http requests such as to get documents at URLs should not be implemented at this stage (this includes hypertext links).

In the second stage, the group will extend the tag set supported by the browser, to include some special formats, for example, mathematical formulae, specialised image formats or other special data formats which basic HTML cannot support but which are important for writing about Computer Science. The special formats to be supported should be formalised in an XML-compliant specification, called "CSML" (Computer Science Markup Language).

Depending on time, the group will also implement the third and final stage of the project. This is the support of http requests for the loading of documents, as triggered by hypertext links (the A tags).


Administration of conference programmes

Supervisor: Prof. Roland Backhouse (room B30)

Group mailing list: gp-rcb1

Team members:

Project description:

The goal of the project is the development of a tool set to support the chair of a conference or workshop in arranging the programme. The project would involve a requirements analysis (obtained by interviewing a number of conference chairs), an analysis of currently available software, the implementation of a software package, and the creation of high quality documentation of the software package that can be used "at a distance".

Background:

Worldwide, thousands of conferences and workshops are organised each year. Usually the conference programme is put together by the conference chair assisted by a programme committee. This involves the chair in

Nowadays it is quite common for all of these tasks to be carried out entirely electronically -- submissions are electronic, the committee "meeting" occurs electronically, etc. Only the conference involves a physical meeting of the participants.

Software is available to help a chair with some of these tasks but it typically requires expert assistance to use, is oriented to one particular type of meeting, and does not keep pace with the latest developments on the web.

The Task:

The task will involve four (overlapping) phases.


Applications of a 3D flythough of our new building

Supervisor: Prof. Steve Benford (room C30)

Group mailing list: gp-sdb1

Team members:

Project description:

There are two goals to this project.

The first is to build a virtual reality flythrough of our new building. Rob Ingram in the Communications Research Group has already made a start on this and you could extend his work. Ideally, it should run in the MASSIVE system on a standard PC (if possible). MASSIVE is a multi-user virtual reality system and so many users could share the model at the same time.

The second is to think of interesting applications that might exploit such a model and then to choose and develop one of them. This might eventually involve installing the application in a public place somewhere on the new campus.


Dynamic dinner parties with SVG

Supervisor: Prof. David Brailsford (room B31)

Group mailing list: gp-dfb1

Team members:

Project description:

Last year a Group Project was set up which explored a well-known problem in Ramsey Theory but in the context of the Internet game "The Six Degrees of Kevin Bacon". Kevin Bacon was conjectured to be one of the "best connected" bit-part actors in Hollywood because he seems to have co-starred with almost everyone, at one stage or another of his career.

The Oracle of Kevin Bacon (http://www.cs.virginia.edu/misc/news-bacon.html) interrogates the online Internet Movie Database (http://www.imdb.com/). By typing in an actor's name the Bacon number is established and the chain of connection to Kevin Bacon is exhibited (with embedded links in the answer that point into IMDB, in order to reference the appropriate movies). The reason for "6 degrees" is that, until recently it was believed that Kevin could be connected with any other actor in the database, via co-starring relationships in movies, in at most 6 steps. The idea is to find a chain such as: "A has co-starred with B who has co-starred with C who has co-starred with Kevin Bacon" . If such a chain were found then A has a Bacon Number of 3 because (s)he is 3 co-starring hops away from Kevin. It has now been established that there is an actress in the database with a Bacon Number of 8 -- but you are very unlikely to find any well-known actor with a Bacon Number of more than four.

Last year a Group in this School went one stage further and set up a Frank Ramsey game but using Kevin Bacon data. Ramsey was a brilliant mathematician (and brother of Michael Ramsey -- who was Archbishop of York and then of Canterbury in the 1950s) Ramsey theory is one of the hardest areas of Graph Theory/ Combinatorics but the classic Ramsey problem is easy to understand when formulated in terms of kevin bacon:

"If Kevin Bacon hosts a dinner party, what is the minimum number of guests (M) he needs to invite to ensure that either there is a group of n people that have (pairwise) co-starred with each other OR that there is a grouping of n people that have not co-starred with each other each other"

For n=3 the answer is that you need M=6 people. However with one fewer guest i.e. parties of M=5, there is a particularly interesting possibility. In most cases, with M=5, one can still set up a dinner party where one finds the groupings of 3 mutual co-stars or 3 mutual `non-co-stars' described above, but there is one "successful" case where you cannot (which is why M=6 is the minimum to guarantee success). Last year's project enabled people to type in actor's names in an attempt to find "successful" dinner parties, as above, all of which must feature Kevin Bacon.

This year's project will build on last year's results but will move off in a very different direction. The Electronic Publishing Research Group has been testing plugins for Internet Explorer and Netscape Navigator which implement the new Scalable Vector Graphics (SVG) standard for Web Browsers. The new project will exhibit successful or unsuccessful dinner parties using the full power of multi-colour graphics within SVG (with the possibility of animation). Considerable experience has been gained locally with SVG coding (based on the recent XML metasyntax standard) but we have no experience of downloading it from a website as this project will demand. Animation is a possibility (using JavaScript).

This project requires *serious* thought on how to do efficient searches for graphs with the correct connectivities, the refreshing of our current local copy of the movies database; the display and explanation of the answer to a non-expert Web visitor, making the very maximum use of SVG. Although it uses XML metasyntax the semantics of SVG are based on PostScript and we do have a prototype PERL library that can generate simple SVG (at its simplest this will involves drawing coloured pentagons showing why given Dinner Parties are (un)successful). Moreover the SVG needs to be generated and downloaded *dynamically* in response to user input in trying to guess "successful" parties.

If time permits, parties with larger numbers of guests and/or involving "trio" relationships (i.e. A has co-starred with B has co-starred with C **all in the same movie**) could be attempted.


Designing wooden railways

Supervisor: Dr. Edmund Burke (room C72)

Group mailing list: gp-ekb1

Team members:

Project description:

My little boy (aged 18 months) has got a (rather extensive) wooden railway set (made by Brio). There is a wide variety of pieces of track: Single (and double) long curved pieces, Single (and double) short curved pieces, Single (and double) straight pieces of varying sizes, points, parallel switches, Y-switches, T-junctions etc. In addition there are lots of different bridges, stations, level crossings etc. The Brio catalogue lists all the items that are currently available.

Designing layouts can be very complicated (especially if one sets constraints such as "I must use every piece of track I own and leave no dead ends"). The main aim of this project will be to implement a Brio Design Layout tool. It should have the following features:


A toolkit for team choice in fantasy football leagues

Supervisor: Dr. Peter Cowling (room C78)

Group mailing list: gp-pic1

Team members:

Project description:

The project will develop an easy-to-use (and hence powerful) interface to allow the evaluation and user-guided selection of a football team for a fantasy league such as is run by several of the broadsheet daily newspapers, and develop algorithms and heuristics to allow automatic choice of the players in the team. Principal components of the software package will include:


Proving originality

Supervisor: Prof. Dave Elliman (room B32)

Group mailing list: gp-dge1

Team members:

Project description:

It would be extremely useful to be able to prove beyond reasonable doubt that a document is an original one. It would be good to know if it has been changed, and if so where. This is an unsolved and rather difficult problem. It is important that small changes due to temperature variation, humidity chages, and ageing of the paper and ink do not make the document seem a forgery, while changes such as adding a zero to an amount of money are spotted reliably. The project will use scanned images, perhaps scanned to a microscopic resolution, and will we written as a Java 2 application.


Camera control in a virtual environment

Supervisor: Dr. Chris Greenhalgh (room C36)

Group mailing list: gp-cmg1

Team members:

Project description:

In the TV and film industries there are established techniques for capturing both live and staged events. These industries use a range of specialised cameras, mounts, shots and transitions (plus lighting and staging) to construct the final visual record. Collaborative Virtual Environments are 3D audio-graphical computer-generated worlds which can be shared by a number of simultaneous participants, each of whom is graphically represented within the virtual world. The aim of this project is to research, design, implement and evaluate appropriate methods for controlling cameras in these virtual environments. The system used will be the Communications Research Group's MASSIVE-3.


Tools for collaboration in virtual environments

Supervisor: Dr. Chris Greenhalgh (room C36)

Group mailing list: gp-cmg2

Team members:

Project description:

Collaborative Virtual Environments are 3D audio-graphical computer-generated worlds which can be shared by a number of simultaneous participants, each of whom is graphically represented within the virtual world. The aim of this project is to identify the tools and facilities required to support small-group collaboration in a virtual environment, and to design, implement and evaluate several such tools or facilities. The system used will be the Communications Research Group's MASSIVE-3.


A virtual library tour

Supervisor: Dr. Leon Harrison (room C31)

Group mailing list: gp-leon1

Team members:

Project description:

The Learning Resource Centre (LRC) on the Jubilee Campus has an innovative design based on an inverted cone with a spiral floor arrangement. The undergraduate tours of the library at the start of the academic year present problems to the librarians in showing new students the facilities of the LRC. Any significant number of students form a trail around the spiral walkway that cannot all hear or see a guide.

The library has asked the School to create a virtual tour system for the library. The design elements at this stage are open but must be flexible, and the underlying data must be easy to update. An initial phase of consultation with the librarian is essential.

As a best guess it expected that the use of VRML and other Web technology would be a good staring point.


Modular on-line cursive script recognition system

Supervisor: Dr. Colin Higgins (room C70)

Group mailing list: gp-cah1

Team members:

Project description:

Automatic handwriting recognition has been an aim of researchers since the early 60's. With regards connected handwriting (cursive script) this has yet to be successfully achieved. This group project will aim to build a recognition system based around the AI concept of a "blackboard system". It will be designed and built in a modular manner allowing new and more components to be added at a later date.


Pac-Man 2000

Supervisor: Dr. Graham Hutton (room B35)

Group mailing list: gp-gmh1

Team members:

Project description:

The arcade game Pac-Man was released in 1980, and is recognised as one of the most popular arcade games of all time. The aim of this project is to implement a version of Pac-Man for PCs. The implementation should include as many aspects of the original game as possible, except that the fixed maze will be replaced by randomly generated mazes that satisfy the Pac-Man property of having no dead ends and being left-to-right symmetrical. The following web site is a good source of information about the game: http://www.classicgaming.com/pac-man/.


Automatic processing of module feedback forms

Supervisor: Dr. Graham Hutton (room B35)

Group mailing list: gp-gmh2

Team members:

Project description:

At the end of each module, students complete a check-box form to give feedback on various different aspects of the module. The information gained from these forms is useful and important, but processing the forms by hand is tedious and time consuming. The aim of this project is to produce a system that automatically extracts the check-box responses from sets of completed feedback forms that have been scanned in, and allows the results to be summarised in the form of statistics, tables, and graphs.


Visual tool to demonstrate ant algorithms

Supervisor: Mr. Graham Kendall (room C80)

Group mailing list: gp-gxk1

Team members:

Project description:

Marco Dorigo recently introduced a search algorithm based on the way ants forage for food. The method is based on the fact that ants are practically blind and they find their way around by following pheromone trails. This search algorithm has been applied to problems such as the Travelling Salesman Problem (TSP), the Quadratic Assignment Problem (QAP) and Vehicle Routing. The aim of this project is to develop a visual teaching/demonstration tool. The tool should show the ant algorithm as it progresses. It should include the various variants of the ant algorithm and should show how the variables (e.g. trail and visibility levels, number of ants at each location) change as the algorithm runs. I would like to see this presented as a visual application that also collects statistics for future analysis.


Create artificial life

Supervisor: Mr. Graham Kendall (room C80)

Group mailing list: gp-gxk2

Team members:

Project description:

Craig Reynold's Flocking Boids is (arguably) an example of artificial life (Alife). Boids simulate birds following simple rules, yet when the individual boids interact they exhibit the flocking behaviour of real birds without having been programmed with this behaviour. For this project you are asked to implement your own version of boids. I would like to see at least the following in the final application.

It would be nice if your implementation showed the flocking behaviour observed by Reynolds as well as showing some other types of complex, non-programmed behaviour.


Tileworld in Java

Supervisor: Dr. Brian Logan (room B43)

Group mailing list: gp-bsl1

Team members:

Project description:

The Tileworld is a simple environment for experimenting with agent architectures developed by Martha Pollack and her students. The environment is a two-dimensional grid on which are located different kinds of objects, including tiles, holes, obstacles and a `gas station'. The environment is dynamic and unpredictable: objects can appear and disappear during a Tileworld run. The experimenter can control of variety of characteristics associated with the objects in the environment, such as the average rate at which they appear or disappear. The agent tries to fill the maximum number of holes with tiles. The aim is to find (or learn) a policy for which holes to fill using which tiles which maximises the agent's score.

The project has several parts: implementing the Tileworld environment, one or more Tileword agents and an interface to allow easy experimentation. It would involve obtaining or re-implementing the Tileworld (the original system is implemented in Lisp and C) and then designing and implementing one or more simple Tileworld agents. A good starting point might be recreating one of the agent designs in the literature and then enhancing it. More details on the Tileworld can be found at: http://www.cs.pitt.edu/~pollack/distrib/tileworld.html.


Psychotherapy over the web

Supervisor: Dr. Brian Logan (room B43)

Group mailing list: gp-bsl2

Team members:

Project description:

ELIZA was an early AI program developed by Joseph Weizenbaum which embodied some knowledge about the rules of conversation. Descriptions of ELIZA can be found in: Margaret Boden: 'Artificial Intelligence and Natural Man', pages 96, 106 etc Bertram Raphael: 'The Thinking Computer', table 6.4, page 199.

The original ELIZA simulated a Rogerian psychotherapist. The aim of this project is to make the advantages of ELIZA's analysis available over the web. This would involve some basic parsing, a pattern matcher/rule interpreter and some conversational rules. There are many existing descriptions and implementations of ELIZA in various languages, but in this case there is the added problem that ELIZA should be able to handle several conversations simultaneously and the conversations have to be stateless or use cookies.


Geological strata

Supervisor: Dr. Mark O'Brien (room C71)

Group mailing list: gp-mark2

Team members:

Project description:

The Earth's rocks are made up of layers of different strata. Some rocks were laid down on ancient seabeds, others by rivers on floodplains. More violently some rocks were the result of volcanic activity. Yet even after these rocks were formed they were subject to metaphosis, lateral movement, upheaval, subsidence and erosion. Geological maps show the resultant complex 3D structures; yet even so they are difficult to understand. The aim of this project is to create a system which simulates the formation of rock strata. The resultant system will present a visualisation of the precise processes in action over time.


Case-based reasoning software tool

Supervisor: Dr. Sanja Petrovic (room C76)

Group mailing list: gp-sxp1

Team members:

Project description:

Case-based reasoning is a new type of reasoning appropriate for building real-world expert systems. The idea of case-based reasoning is to memorise the ways the experts solve actual problems and to utilise the memorised knowledge and experience for solving new problems. An actual problem and its solution constitute a case. The memorised cases are organised in a case base. Given a description of the new problem, the case from the case base which is the most similar and therefore the most useful for the new problem solving is retrieved. If it is necessary, the retrieved solution is adapted to be applicable in the new problem. The new problem with its solution is integrated in the case base. Solving new problems leads to enrichment of the case base with new knowledge and experience. The aim of the research project is to develop an interactive case-based reasoning software tool that enables development of the case-based reasoning systems. The interface has to be designed to make it simple for the domain expert to input new cases, to define the similarity measure which is used in the retrieval process and to define the rules that are needed to adapt cases to new problems.


Decision support system for discrete multicriteria problems

Supervisor: Dr. Sanja Petrovic (room C76)

Group mailing list: gp-sxp2

Team members:

Project description:

In most real-world problems there is a need to analyse a finite number of alternatives described by many criteria. Criteria are usually expressed in different units of measures and different scales and they are totally or partially conflicting and incommensurable. The aim of multicriteria decision analysis is to help the decision maker explore the multicriteria problem at hand, express his/her preferences, and eventually lead to a preferred course of action. The aim of the research project is to develop a decision support system that is based on the simple additive weighting method for multicriteria decision analysis. A decision maker expresses his/her preferences by assigning relative importance (weight) to each criterion. The decision support system consists of (a) the problem editor which enables a decision maker to describe the problem in terms of alternatives and criteria, (b) the simple additive weighting method and (c) the output module which offers a flexible and user-friendly environment for presenting the result and for performing experiments using different preference information (a kind of sensitivity analysis).


A visual programming environment for image processing

Supervisor: Dr. Tony Pridmore (room C46)

Group mailing list: gp-tpp1

Team members:

Project description:

Image processing applications typically comprise sequences of filters, each applying a single parameterised transformation to the input image (or images) to produce a modified output image (or images). Many such filters have been developed and applied, making large libraries of image processing operations commonplace. Most of these libraries are supplied as C/C++ source and/or binaries, which must be included or linked to their user's application programs in the standard way. Novice users often find this method of working frustrating: successful application of image processing libraries requires a significant amount of knowledge and experience of the capabilities of the available techniques and the effects of varying their parameters, this is acquired only slowly from the standard compile-run-debug cycle.

The aim of the project is to produce a graphical interface to a small library of image processing operations, producing an environment in which a user may explore and experiment with operations and their parameters without writing any code. This might best be achieved by taking a visual programming approach, following WIT and KHOROS, though the group is free to reach its own decision. The final environment should allow a novice user to create and execute processing chains, vary the parameters of individual operations and view the results of each operation in a windows-based environment. The size of the initial library is not important, though it should be large enough to demonstrate the system. It is important, however, that the system be extendable. Clear instructions should be given in the project report as to how new image processing operations can be added.


Last modified on 1st November 1999 by Graham Hutton.