Graham Kendall Ideas for 3rd Year Individual Projects
This page has some ideas for third year individual projects that Graham
Kendall would be interested in supervising.
In addition, there is a list (with abstracts and some downloadable dissertations) of the previous projects I have supervised. They may give you an idea of your own, or you light like to develop one of these projects. You might also like to look at my third year project page which has advice on starting your project and producing your dissertation.
But, please do not accept this as an invitation that I will supervise you. There are many factors to consider, many outside of my control.
Due to the number of questions I get I have created a page that gives some advice about third year undergraduate projects.
Can the Travelling Salesman Problem (and others) be a Puzzle?
I have recently published a paper (see draft (available soon)), that looks at various puzzles and how difficult they are. One of the questions posed is how we can develop new puzzles and make them interesting for the player to play. If we take a problem such as the Travelling Salesman Problem (see, for example, here). The aim of this project would be two-fold.
You might also want to look at other puzzles such as the vehicle routing problem, bin packing etc.
Playing Poker
Over the past couple of years I have had a couple of third year projects
that 'learnt' how to play poker. As a result of these projects, as well as
an interest myself, I have built up quite a large set of literature on this
subject, which I can make available to you
Your task, should you choose to accept it, is to write a poker playing program
that plays legal poker and wins money/points against human opponents.
There is a poker site at Poker Paradise
which allows human players to compete against each other either for 'play'
money or for real money. There are also many (many, many) others.
I am not suggesting that you play for real money, but the play money
tables would be an ideal testing ground for your program.
In order to do this project, you must be willing to ensure your program plays
legal poker and not allow yourself to compromise your program in any way,
so that it cannot deal with all eventualities.
There are many aspects you might like to concentrate on.
If the student was interested enough any of these projects could be conducted as a piece of current research which could lead to an academic paper - although this should not be taken on lightly.
Hyper-heuristics
Hyper-heuristics are a new type of heuristic approach we are developing at
Nottingham. In simple terms instead of solving problems directly (using something
like simulated annealing) we try to either choose the best heuristic to apply
at a given point in the search or we try to evolve heuristics themselves.
If you think this might be of interest there are many avenues that could be
explored. For example, but certainly not limited to
If the student was interested enough this could be conducted as a piece of current research which could lead to an academic paper - although this should not be taken on lightly.
Sports
Timetabling
I would like to see a project that takes the fixture lists for the footbal
league (Premier Division, First Division etc.) and produces a schedule that
is better than the schedule that is released by the FA in about June/July
each year. This is quite a tough problem as there are many constraints to
take into account. For example, there are hard constraints (i.e. constraints
which cannot be broken) such as every team has to play every other team both
home and away. But there are also lots of other constraints which can be violated
to varying degrees. For example, certain teams in the same police authority
cannot play at home on the same day (and this might operate across divisions),
the travelling time on boxing day should be minimised, teams in seaside resorts
cannot play at home on bank holiday weekends, FA cup and European matches
must be catered for etc. etc. I have a draft paper though which outlines some
of the constraints and I also have data available that you could use (this
is from the English leagues; 2002/2003).
It would be good to build a model of this problem and then see how the fixture
list produced by the FA fits into this model and then see if the approach
we use to solve the problem does better.
It would also be interesting to post your solution on the web, to newsgroups,
send to clubs, papers etc. to see what they think. How does our schedule compare
with the one relesaed by the FA?
I have written a paper, which might be of interest.
I have done some work in this area and have some data available for the English
leagues for the season 2002/2003.
If you decided to do a project such as this, you would need to model the problem
and then decide how to solve it. You might like to consider algorithms such
as genetic algorithms, tabu search, hyper-heuristics etc.
If the student was interested enough this could be conducted as a piece of
current research which could lead to an academic paper - although this should
not be taken on lightly.
Last Updated 5th June 2001