Genaral areas of interest:
Algorithms, complexity, robotics.


PROJECT I
Dr Nicolai Vorobjov
nnv@cs.bath.ac.uk

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.

A similar project:

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


PROJECT II
Dr Nicolai Vorobjov
nnv@cs.bath.ac.uk

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.


PROJECT III
Dr Nicolai Vorobjov
nnv@cs.bath.ac.uk

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 plane the move.

Pre-requisite knowledge: some basic knowledge of computer graphics
and algorithms
Indicative reading: see NNV



PROJECT IV
Dr Nicolai Vorobjov
nnv@cs.bath.ac.uk
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.

Pre-requisite knowledge: non-special
Indicative reading: web search on the existing software in this area