Text only

CM30076 / CM30082
Individual Project

Project Ideas

Dr Nicolai Vorobjov

nnv@cs.bath.ac.uk

This is Dr Vorobjov's 2003 list of projects. It will be updated with a new list when one is provided. In the meantime, take it as a guide to likely interests.

Program for Solving Two-Person Games
The aim is to design an application for finding optimal strategies in finite two-person games. Such games are called bimatrix. They include all possible situations in which two parties have finite number of possible ways to act (strategies) and the outcomes lead to payoffs depending on the pair of chosen strategies. Chess is an example, though hardly tractable, stone-paper-scissors is another, very simple to solve. The application should be able to accept any pair of pay-off matrices as an input and to output optimal mixed strategies. For games usually defined in the positional form an appropriate universal representation of the input should be designed. The project includes the stage of learning the background game-theoretical material including the existing algorithms for solving bimatrix games.
Pre-requisite knowledge: Some modest knowledge of linear algebra
Indicative reading: any introductory text on game theory
Program for Teaching Game Theory
The aim of the project is to design a program which will help to explain and illustrate the basic concepts of the theory of games. When the number of strategies of one of the players in a matrix game is small (say, two or three) then the optimal strategies can be found by drawing certain two- or three-dimensional pictures. The program will draw such pictures and explain interactively some elements of the theory.
Pre-requisite knowledge: Some modest knowledge of linear algebra
Indicative reading: any introductory text on game theory
Computer Linear Algebra System
The aim is to design a basic linear algebra system as a very simplified analogy (and a part) of usual computer algebra systems, like REDUCE, Maple, etc. It should include algorithms for matrix multiplication (trivial, as well as advanced and more efficient, like Strassen's), for solving systems of linear equations (Gauss, and based on fast matrix multiplication), computing determinants, etc.
The system should have a convenient interactive interface with an ability to extend by adding new commands. Existing systems could be used as examples, but all programming is supposed to be original.
Pre-requisite knowledge: some basic knowledge of linear algebra
Indicative reading: any introductory text on linear algebra, user manual for Maple.
Robot Motion Planning
The aim is to design a graphical application for robot motion planning on the plane in the presence of polygonal obstacles. In one version of the problem the robot is considered as a point and we are looking for a shortest piece-wise linear path connecting "start" and "finish".
In another version the robot is a polygon, and the aim is to decide whether it is possible for him to pass through a corridor of a complex form, and if yes, to plan the move.
Pre-requisite knowledge: some basic knowledge of computer graphics and algorithms
Domino Partners
The game of domino is usually played between two teams of two players in each. Since it might be hard to find enough partners willing to play, it's desirable to have a computer program which can model one, two or three players, breaking them in teams, as required. The project consists of designing such a program together with a graphic interface to show moves.
Indicative reading: web search on the existing software in this area