A search tree visualiser can be used to look at the search tree Minion creates during search and identify possible sources of contention and insufficient propagation.
The most basic form of such a visualiser would take Minion output and generate the search tree from it. It should also have a facility to hide irrelevant parts of the tree to make it feasible to look at large search trees.
Improvements over a basic implementations might include: interactive exploration of the search tree, ability to save the visualisation to e.g. PDF, more sophisticated visualisations which make it easier to grasp all the information the search tree represents (e.g. something based on this).
There are several visualisers for other constraint solvers (Choco, Gecode, Eclipse) which could be used as a starting point. The visualiser can be implemented as a standalone program which reads Minion output or as a component of Minion that allows to control the search interactively. If implemented as a standalone program, there is no preference for a programming language.
The visualiser should be cross-platform.
Successful applicants should have strong programming skills in C++ or a language of their choice and experience in software engineering and testing. Experience in Computer Graphics and/or Artificial Intelligence is a plus, but not required.
Mentors: Chris Jefferson, Karen Petrie, Lars Kotthoff
A domain-specific search visualiser shows the state of the search depending on the problem. For example in Sudoku, it would show a 9x9 grid with numbers in each cell.
There exists a basic visualiser like that which shows the domains of variables in a grid (similar to Sudoku) written in Haskell. This can be used as a starting point, but does not have to. There are also domain-specific visualisers for other constraint solvers (Choco) which can be used as a starting point.
The final program should take a description of the type of visualisation and Minion output as inputs and produce a visualisation of the search process. Alternatively, it could be implemented as a part of Minion. It should have a set of predefined types of visualisation and allow to create new ones (easily). It could also be made interactive and provide a facility for saving visualisations.
The visualiser should be cross-platform.
Successful applicants should have strong programming skills in Haskell/C++ or a language of their choice and experience in software engineering and testing. Experience in Computer Graphics and/or Artificial Intelligence is a plus, but not required.
Mentors: Chris Jefferson, Karen Petrie, Lars Kotthoff
Our projects give you an exciting opportunity to work with researchers and push the borders computer science further. You will be able to bring your own ideas into the project and realise them. You will be expected to work independently and deliver high-quality results.
For all applications you should submit an outline of what you are planning to do specifically, possibly mentioning decisions such the programming language which you want to use and other implementation details. You should convey to us that you know what you are meant to do and that you know how to do it.
If you have an idea for a project that is not listed here, but fits in with what we are doing, by all means let us know!
Prospective applicants are encouraged to discuss their application with Lars Kotthoff at larsko@cs.st-andrews.ac.uk.
For all projects, we require students to assign the copyright for their work to us.