Undergraduate project suggestions

John Bell

I would like to supervise projects in the following areas of Artificial Intelligence.

Planning and rationality

A planning system is a program which, given a set of initial conditions and a set of action types (actions it can perform), generates a plan (or plans) to achieve the goal. The following are some possible projects:
  1. Implement a planning system; say a simple version of the continuous partial order planner discussed in [R&N 03, Sec. 12.6]. (An implementation project.)
  2. Consider how to link this account of planning with decision theory. A discussion of this is given in [Po95]. (A theory project.)
  3. Consider how to link plan generation and scheduling; suppose that several plans are being generated which achieve goals of different importance. How should work on the plans progress. (Links to job-shop scheduling.) (Could be either an implementation project or a theory project.)

Behaviour-based robotics

Kephera robots are small research robots. A simulator program can be found at: http://diwww.epfl.ch/lami/team/michel/khep-sim/.
  1. An initial project would be to use this simulator as part of a larger system which enabled the user to define and test robot behaviours; as described in [Ar98]. Ideally the system should enable the user to define simple environments (obstacle courses, mazes, etc.), to define simple behaviours (e.g. to define functions for avoiding objects or keeping on a path), and to define how these behaviours are to be combined (e.g. to give more weight to goal seeking, than to obstacle avoidance, or vice-versa). (Implementation)
  2. This program could be extended in many ways; e.g. to allow for multiple robots and co-ordination/competition between them.

AI teaching projects

A great deal of software is becoming available on the web which can be used for teaching purposes. Some of this is collected at: http://www.dcs.qmul.ac.uk/~cfshan/AIhomepage.htm. The aim of this type of project would be to investigate this software and to use it to develop teaching tools/demos. For example, it would be useful to have a program which demonstrated edge-detection. (Analysis and design, or implementation)

Game playing

  1. Implementation of game playing programs, such as one for Chess [Ne96,R&N03 Ch. 6]. The program could be restricted to simple positions (say king and pawn vs king), and would aim to use heuristics (rules of thumb for endings of this kind) to play the endings well [Fi41]. (Implementation)
  2. Su Doku algorithms. Type `Su Doku algorithms' at Google and you will find that a great deal of work has been done on the design and analysis of Su Doku algorithms. One type of project could consist of a survey of this work and its significance for computer science. In effect this would be a study of an NP-complete problem. (Theory) Another type of project could consist of the design and implementation of an algorithm which tried to solve puzzles in the way humans do; again using heuristics and, possibly, A* search [R&N03, Ch 4-5]. (Implementation)

References

[Ar98] Ronald C. Arkin, `Behavior-Based Robotics', MIT Press, 1998.
[Fi41] Reuben Fine, `Basic Chess Endings', G. Bell and Sons, 1941.
[Ne96] Monty Newborn, `Kasparov versus Deep Blue; Computer Chess Comes of Age', Springer, 1996.
[Po95] John L. Pollock, `Cognitive Carpentry; A Blueprint for How to Build a Person', MIT Press, 1995.
[R&N03] Stuart Russell and Peter Norvig, `Artificial Intelligence; A Modern Approach', Second Edition, Prentice Hall, 2003.

Return to John Bell's home page