Final Year Project Suggestions
Academic Year 2007-2008
Dr. Barry O'SullivanDepartment of Computer Science
University College Cork
|
|
Final Year Project SuggestionsAcademic Year 2007-2008Dr. Barry O'SullivanDepartment of Computer Science University College Cork |
My research interests lie in artificial intelligence, constraint satisfaction, human-computer interaction, and visualisation. My set of final year project proposals for 2007-2008 are as follows:
My office is located in the Cork Constraint Computation Centre (14 Washington Street - opposite the Kino).
[ Back to Top ]
We encounter configuration problems in a broad variety of application domains. The one that people are most familiar with is configuring a PC on a web-site. However, large configuration problems have large numbers of decision variables (e.g. hard-disk size in our PC example), and extremely large numbers of solutions. As a result, unless we have access to some convenient representation of these solutions, it is impossible to make response-time guarantees when we configure a product interactively.
In this project we will build an interactive configurator based on binary decision diagrams (BDDs) [1]. The basis for the implementation of this configurator will be the CLab system [2]. The first objective of this project is to develop a graphical tool for loading, compiling and interacting with BDD-based representations of configuration problems. The second objective of the project will be to undertake an empirical evaluation of the configurator using a suite of well known benchmarks problems available in CLib [3]. While much of this project is based on reusing existing tools, marks will be awarded based on the overall look and feel of the graphical user-interface to the configurator and the quality of its evaluation.
This project is suited to a student with both strong coding capabilities and an interest in algorithms and artificial intelligence. Analytical skills are required in order to design experiments and evaluate their results.
[ Back to Top ]
Visualisation is an important component in successful human-computer interaction. This project considers ways of visualising large combinatorial problem formulations and their search spaces. One possible visualisation is to consider Treemaps [1], as an approach to visualising large combinatorial search spaces expressed in a compact manner in terms of decision variables, possible values to those decision variables and restrictions on the compatible combinations of such values. However, other visualisations are possible using libraries such as Graphviz [2].
The first objective of this project is to develop a generic visulation tool that can read in a problem specification, and render it appropriately. The second objective is to consider different ways in which large problem formulations can be displayed and the effects of these on the efficiency with which users of constraint-based systems can support either interactive problem solving activities, model debugging, or model refinement.
This project is suited to a student with both strong coding capabilities and an interest in algorithms and artificial intelligence. Analytical skills are required in order to design experiments and evaluate their results.
[ Back to Top ]
The satisfiability (SAT) problem is one of the most widely studied combinatorial problems in computer science. It is the classic NP-complete problem. Over the past number of decades a significant amount of research work has focused on solving SAT problems with both complete and incomplete solvers. Furthermore, many researchers have considered the problem of generating hard SAT problems using various techniques, many of which are extremely mathematical in nature.
In this project we take a different approach to generating hard SAT problems. We will consider the problem of generating hard SAT problems with respect to a particular SAT solver as an optimisation problem, similar to the work presented in [1]. The search effort required by the SAT solver will be used as a measure of the fitness of a problem for a genetic algorithm, i.e. the harder the problem, the fitter it is. The task for the genetic algorithm is to evolve a SAT problem by maximising the search effort required to solve the problem using a specific solver.
This project will benefit from the many SAT solvers that are currently available on the web in both source-code and executable form. A well-known genetic algorithm library [2] will be used to implement the genetic algorithm component. The primary objective of this project is to demonstrate how a genetic algorithm can be used to generate hard SAT problems. The second objective is to study to what extent hard problems for one SAT solver are hard for other solvers. For higher marks, the student could develop a graphical user interface to a workbench for generating and studying hard SAT problems.
This project is suited to a student with a strong interest in artificial intelligence and an interest in algorithms. From an implementation perspective, the student is required to become familiar with a number of freely available tools and software libraries to build the genetic algorithm. An ability to setup, run and interpret experiments is also important.
[ Back to Top ]
Traditionally, researchers who develop solvers for satisfiability problems have focused on developing better algorithms to incorporate into their solvers. However, recently, people have become very interested in gathering together a set of distinct solvers and defining a set of rules for selecting which specific solver to run on a given instance. The most famous algorithm portfolio for SAT is called SATzilla [1]. SATzilla uses a linear runtime prediction model to select from its portfolio of algorithms.
The objective of this project is to build upon SATzilla, but use a case-based reasoning approach to the problem of selecting the best solver. In this case, selecting the best solver becomes a classic classification task [2].
This project is suited to a student with both strong coding capabilities and an interest in algorithms and artificial intelligence. Analytical skills are required in order to design experiments and evaluate their results.
[ Back to Top ]
The Killer Sudoku is a mathematical puzzle [1]. A Killer Sudoku can be naturally formulated as a constraint satisfaction problem [2,3]. The objectives of this project include formulating a Killer Sudoku as a constraint satisfaction problem and developing a graphical interface for solving it using inference-based constraint satisfaction techniques. In addition, generators for Killer Sudoku puzzles should be developed. Finally, for higher marks, the student should develop a specific type of constraint for solving these problems.
This project is suited to a student with both strong coding capabilities and an interest in puzzles and mathematics.
[ Back to Top ]
Given a satisfiability problem, the standard task is to decide whether it is satisfiable or not. Typically, satisfiability solvers are either based on exhaustive search, or incomplete local search. The former has the disadvantage that it does not scale. The latter has the disadvantage that it cannot guarantee unsatisfiability. In this project we take a different approach: we learn a classifier that attempts to answer the SAT/UNSAT question based on a number of low-level problem features that we can extract from a satisfiability instance quite efficiently.
The objective of this project is to devise a set of features we can extract from an instance of the satisfiability problem [1]. Based on these features we will use various machine learning algorithms to learn classifiers for the data we gather from instances whose classification is known [2]. We will then apply these classifiers to unseen instances from various domains and evaluate the quality of the results [3].
This project is suited to a student with both strong coding capabilities and an interest in puzzles and mathematics.
[ Back to Top ]
From Wikipedia: A Costas array can be regarded geometrically as a set of n points lying on the squares of a n×n checkerboard, such that each row or column contains only one point, and that all of the n(n-1)/2 displacement vectors between each pair of dots are distinct. This results in an ideal 'thumbtack' auto-ambiguity function, making the arrays useful in applications such as Sonar and Radar.
A Costas array may be represented numerically as an n×n array of numbers, where each entry is either 1, for a point, or 0, for the absence of a point. When interpreted as binary matrices, these arrays of numbers have the property that, since each row and column has the constraint that it only has one point on it, they are therefore also permutation matrices. Thus, the Costas arrays for any given n are a subset of the permutation matrices of order n.
The objective of this project is to model the Costas Array as a constraint satisfaction problem. Based on this model we will apply variable constraint solvers to it. For high marks the student needs to focus on developing a good model of the problem, i.e. better performing than the naive model..
This project is suited to a student with both strong coding capabilities and an interest in puzzles and mathematics.
[ Back to Top ]
Alesia is a simple two-player game. Each player starts with an initial capital of 50 points. At each turn, each player secretly decides a number of points (at least one) and writes it down. Then, both papers are revealed simultanously and the player who wrote the largest number moves next towards the opponent's "castle". The amount of points played by the two players are then removed from their initial capital. When the capital of a player falls to zero, the game continues and the corresponding player is forced to play zero until the end, thus losing against any choice of his opponent. In practice, the opponent player will be able to move as many times as the amount of his capital (by playing one point at each step). A player wins if he successfully moves to his opponent's castle. If the capital of both players falls to zero and none of them has reached the the other'scastle, the game is considered a draw.
The goal of this project is to design software with a graphical interface to allow two human players to play Alesia. Secondly, after having carefully analyzed the game, one or several AI techniques should be implemented to play Alesia and their performance compared against each other, a human player and a random player.
This project is suited to a student with both strong coding capabilities and an interest in puzzles and mathematics.
[ Back to Top ]
Develop a tutorial for the Choco constraint programming system (add more info.)
This project is suited to a student with both strong coding capabilities and an interest in puzzles and mathematics.
[ Back to Top ]
Develop a tutorial for the Comet constraint programming system (add more info.)
This project is suited to a student with both strong coding capabilities and an interest in puzzles and mathematics.
[ Back to Top ]
RSS is a news feed format used to announce frequently updated content on the web [1]. It offers web users the opportunity to customise the delivery of the content they wish to monitor. A nice opportunity is to allow users to build their own personalised newspapers by combining RSS news items from traditional news sites, and typesetting them into documents with the look and feel of a printed newpaper.
The objective of this project is to develop an RSS reader that has the capability of laying out a collection of newsfeeds in newspaper format on A4 pages so it can be printed on a conventional printer. A similar solution is available online called Feed Journal [2]. One possible solution might be to use the LaTeX package paperTeX to help with the typesetting component [3].
This project is suited to a student with both strong coding capabilities and an interest in web programming and document layout.
[ Back to Top ]
Develop a suite of software tools to help children do fun things with pictures, web-sites and audio (more details to come).
This project is suited to a student with both strong coding capabilities and an interest in human-computer interaction.
[ Back to Top ]
b.osullivan@cs.ucc.ie
Return to Barry's Home Page