Undergraduate Project Suggestions 2007 - 2008
On this page you can find a number of project suggestions for final year students. Do not hesitate to contact me if you would like more information on any of the project mentioned below or if you would like me to supervise one of your own project idea (you need approval from the DoS for such a project).
These are the current project suggestions:
- Project 1: General Game Playing in ASP
- Project 2: APE: An IDE for ASP (Continuation)
- Project 3: Estimating Answer Set Density
- Project 4: "SETI@Home" Style Answer Set Solver
- Project 5: Modelling Institutions in ASP
- Project 6: Modelling Argumentation
- Project 7: An Institutional Repository and Methodology
- Project 8: UltraSPARC T1 core for Platypus
- Project 9: An Open Implementation of DLT
- Project 10: Experimental: SAT random competition
- Project 11: Experimental: Order Heuristics for CLASP
- Project 12: SSH Key Distribution
- Project 13: A Teaching Compiler
Project 1: General Game Playing in ASP
Task - Write a GGP player with an answer set program as its core.
Description - A General Game Playing System is one that can accept a formal description of an arbitrary game and, without further human interaction, can play the game effectively.
This projects seeks to develop a GGP player partially based on answer set programming. All other tools and techniques can be freely chosen.
ASP (Answer Set Programming) is an up and coming field in logic programming. Programs consist of a series of logical rules which are then put into a solver, which produces a list of 'possible world views' that are consistent with the information provided by the rules.
More information on GGP and support tools can be found on the GGP homepage.
Description - A General Game Playing System is one that can accept a formal description of an arbitrary game and, without further human interaction, can play the game effectively.
This projects seeks to develop a GGP player partially based on answer set programming. All other tools and techniques can be freely chosen.
ASP (Answer Set Programming) is an up and coming field in logic programming. Programs consist of a series of logical rules which are then put into a solver, which produces a list of 'possible world views' that are consistent with the information provided by the rules.
More information on GGP and support tools can be found on the GGP homepage.
Project 2: APE: An IDE for ASP (Continuation)
Task - Extend APE with new functionality
Description - ASP (Answer Set Programming) is an up and coming field in logic programming. Programs consist of a series of logical rules which are then put into a solver, which produces a list of 'possible world views' that are consistent with the information provided by the rules. It has a lot of potential for tasks such a knowledge representation, scheduling, planning, data mining, etc. At the moment a number of solvers exist but there are very few support tools to help programmers. Two years ago, Adrian Sureshkumar, an undergraduate from Bath, created APE, an IDE for ASP. APE is written as an Eclipse plug-in. The development files are available from http://krr.cs.bath.ac.uk/index.php/APE. Adrian also investigated the features that the community would like to have in an IDE. This project's aim is to further develop APE by including debugging features, conversion tools between the various systems and other useful tools. Furthermore, the requirement elicitation should continue. One could also consider drafting a possible input language that all current state-of-the art systems would accept.
Description - ASP (Answer Set Programming) is an up and coming field in logic programming. Programs consist of a series of logical rules which are then put into a solver, which produces a list of 'possible world views' that are consistent with the information provided by the rules. It has a lot of potential for tasks such a knowledge representation, scheduling, planning, data mining, etc. At the moment a number of solvers exist but there are very few support tools to help programmers. Two years ago, Adrian Sureshkumar, an undergraduate from Bath, created APE, an IDE for ASP. APE is written as an Eclipse plug-in. The development files are available from http://krr.cs.bath.ac.uk/index.php/APE. Adrian also investigated the features that the community would like to have in an IDE. This project's aim is to further develop APE by including debugging features, conversion tools between the various systems and other useful tools. Furthermore, the requirement elicitation should continue. One could also consider drafting a possible input language that all current state-of-the art systems would accept.
Project 3: Estimating Answer Set Density
Task - Attempting to experimentally discover what the link between
answer set density and the effects of
probing/restarting on a variety of different problems. If the link is
sufficiently strong this could be used to
as an estimate of the solubility of NP problems.
Description - Answer set density can be computed as the total number of answer sets divided by the number of answer sets and number of conflicts found (and is thus solver dependant - but this shouldn't effect the underlying curve). The speed up that probing gives as verses normal solving is easy to measure. Graph one against the other against different types of program against different probing parameters. See what trends can be found. If the link is sufficiently strong then by timing the amount of time before probing (with different parameters) gets an answer set we can estimate the density of answer sets and thus the solubility. Bonus points for doing this automatically.
Description - Answer set density can be computed as the total number of answer sets divided by the number of answer sets and number of conflicts found (and is thus solver dependant - but this shouldn't effect the underlying curve). The speed up that probing gives as verses normal solving is easy to measure. Graph one against the other against different types of program against different probing parameters. See what trends can be found. If the link is sufficiently strong then by timing the amount of time before probing (with different parameters) gets an answer set we can estimate the density of answer sets and thus the solubility. Bonus points for doing this automatically.
Project 4: "SETI@Home" Style Answer Set Solver
Task - Implementing a new distribution model for Platypus (the client)
and a central server to handle solving very
large ASP problems in a distributed, ad-hoc fashion.
Description - The distribution system of Platypus works by distributing partial assignments - points within a tree of computations in which the leaves are conflicts or answer sets. The probing module allows an implementer change partial assignment after a fixed number of conflicts have been reached. This allows the work to be divided up into packets in such a way that a packet of work is deterministic and repeatable. The central server stores these packets of work as files in a file-system and assigns them to clients. This allows clients to work at their own rate, using a distributed, ad-hoc networking model and not needing interaction between them. Using the file-system to store the computation tree means that tools (such as monitoring, logging, partial recomputes, etc.) can be greatly simplified and the server is fault tolerant and easily distributed.
Description - The distribution system of Platypus works by distributing partial assignments - points within a tree of computations in which the leaves are conflicts or answer sets. The probing module allows an implementer change partial assignment after a fixed number of conflicts have been reached. This allows the work to be divided up into packets in such a way that a packet of work is deterministic and repeatable. The central server stores these packets of work as files in a file-system and assigns them to clients. This allows clients to work at their own rate, using a distributed, ad-hoc networking model and not needing interaction between them. Using the file-system to store the computation tree means that tools (such as monitoring, logging, partial recomputes, etc.) can be greatly simplified and the server is fault tolerant and easily distributed.
Project 5: Modelling Institutions in ASP (Joint with Dr. Padget)
Task - Write a tool kit for modelling and reasoning about institutions in ASP.
Description - Institutions can be seen as multi-agent systems where agents are governed by norms. Agents should follow the norms imposed on them or face the penalties that come with breaking them. Recently we developed here in Bath a formalism that allows to characterise these institutions using an action language, called InstAl, that can be translated into an answer set program to allow reasoning of the represented institution. The aim of this project is to develop a tool that helps the user to write the specification of the institution and to reason about it.
Description - Institutions can be seen as multi-agent systems where agents are governed by norms. Agents should follow the norms imposed on them or face the penalties that come with breaking them. Recently we developed here in Bath a formalism that allows to characterise these institutions using an action language, called InstAl, that can be translated into an answer set program to allow reasoning of the represented institution. The aim of this project is to develop a tool that helps the user to write the specification of the institution and to reason about it.
Project 6: Modelling Argumentation (Joint with Dr. Padget)
Task - Implementation of institutional argumentation frameworks
Description - Argumentation has been the subject of study for centuries but in the last several decades one focus has been on its formalization through the characterisation of statements as undercutting, defeating or supporting earlier statements, thus creating a dialogical structure that can be reasoned about. Furthermore, once argumentation is formalized, it becomes possible to argue about the framework in which an agent is operating and potentially reach positions of agreement to change that framework. The objective of this project is to build an institutional representation of argumentation using software tools already developed (an implementation of a a simple action language InstAL, Answer Set Program parsers and solvers, graphviz) to explore the usefulness of several existing argumentation frameworks.
Description - Argumentation has been the subject of study for centuries but in the last several decades one focus has been on its formalization through the characterisation of statements as undercutting, defeating or supporting earlier statements, thus creating a dialogical structure that can be reasoned about. Furthermore, once argumentation is formalized, it becomes possible to argue about the framework in which an agent is operating and potentially reach positions of agreement to change that framework. The objective of this project is to build an institutional representation of argumentation using software tools already developed (an implementation of a a simple action language InstAL, Answer Set Program parsers and solvers, graphviz) to explore the usefulness of several existing argumentation frameworks.
Project 7: An Institutional Repository and Methodology (Joint with Dr. Padget)
Task - Develop a repository for common virtual institutions and
a methodology for constructing them
Description - Institutions can be seen as multi-agent systems where agents are governed by norms. Agents should follow the norms imposed on them or face the penalties that come with breaking them. Recently we developed here in Bath a formalism that allows to characterise these institutions using an action language, called InstAl, that can be translated into an answer set program to allow reasoning of the represented institution. The necessary tools to construct these institutions. You just have to develop and write them. This project can be extended to the development of a methodology of writing institutions in InstAl.
Description - Institutions can be seen as multi-agent systems where agents are governed by norms. Agents should follow the norms imposed on them or face the penalties that come with breaking them. Recently we developed here in Bath a formalism that allows to characterise these institutions using an action language, called InstAl, that can be translated into an answer set program to allow reasoning of the represented institution. The necessary tools to construct these institutions. You just have to develop and write them. This project can be extended to the development of a methodology of writing institutions in InstAl.
Project 8: UltraSPARC T1 core for Platypus
Task - Write a new core (a specific part of the program)
for the Platypus system such that the distributed answer set solver can run efficiently on a UltraSparc TI machine.
Description - The distribution system of Platypus works by distributing partial assignments - points within a tree of computations in which the leaves are conflicts or answer sets. The probing module allows an implementer to change partial assignment after a fixed number of conflicts have been reached. This allows the work to be divided up into packets in such a way that a packet of work is deterministic and repeatable. The central server stores these packets of work as files in a file system and assigns them to clients. This allows clients to work at their own rate, using a distributed, ad-hoc networking model and not needing interaction between them. Using the file system to store the computation tree means that tools (such as monitoring, logging, partial recomputes, etc.) can be greatly simplified and the server is fault tolerant and easily distributed. The implementation of Platypus is very machine dependent. For this project you are asked to alter the Platypus code so it can run on a UltraSPARC T1.
Prerequisites: You need to be a good program for this project. Platypus is written in C++. Also an active interest in machine architectures is necessary.
Description - The distribution system of Platypus works by distributing partial assignments - points within a tree of computations in which the leaves are conflicts or answer sets. The probing module allows an implementer to change partial assignment after a fixed number of conflicts have been reached. This allows the work to be divided up into packets in such a way that a packet of work is deterministic and repeatable. The central server stores these packets of work as files in a file system and assigns them to clients. This allows clients to work at their own rate, using a distributed, ad-hoc networking model and not needing interaction between them. Using the file system to store the computation tree means that tools (such as monitoring, logging, partial recomputes, etc.) can be greatly simplified and the server is fault tolerant and easily distributed. The implementation of Platypus is very machine dependent. For this project you are asked to alter the Platypus code so it can run on a UltraSPARC T1.
Prerequisites: You need to be a good program for this project. Platypus is written in C++. Also an active interest in machine architectures is necessary.
Project 9: An open implementation of DLT
Task - Re-engineer the DLT system.
Description - DLT is a system that allows a programmer to create templates for commonly used concepts in declarative programming languages. This saves having to re-implement common ideas such as sets, lists, etc. DLT is a closed source product that is only compatible with a very limited range of tools. This projects is to re-implement the functionality of DLT (matching the syntax if possible) such that it can be used with a range of tools and can be released under an open source license. It is suggested that either perl or the C pre-processor is used to handle macro expansion.
Description - DLT is a system that allows a programmer to create templates for commonly used concepts in declarative programming languages. This saves having to re-implement common ideas such as sets, lists, etc. DLT is a closed source product that is only compatible with a very limited range of tools. This projects is to re-implement the functionality of DLT (matching the syntax if possible) such that it can be used with a range of tools and can be released under an open source license. It is suggested that either perl or the C pre-processor is used to handle macro expansion.
Project 10: Experimental: SAT random competition
Task - Implement an algorithm to compete in the SAT random competition.
Description - We believe it might be possible to win the SAT random instance contest by "cheating". Most of the programs are relatively small, the smallest maybe have 80 literals and 1700 clauses and are 5 SAT. By using offsets instead of pointers, it should be possible to store the entire program in less than 64K, i.e. L1d cache on a modern processor. This should give a constant speed up which might be enough if a good algorithm was used. Obviously some profiling would have to be done to tell if this was likely to be enough to make the difference but it could be an entertaining (and perhaps rewarding) project for someone who likes low level bit twiddling.
Description - We believe it might be possible to win the SAT random instance contest by "cheating". Most of the programs are relatively small, the smallest maybe have 80 literals and 1700 clauses and are 5 SAT. By using offsets instead of pointers, it should be possible to store the entire program in less than 64K, i.e. L1d cache on a modern processor. This should give a constant speed up which might be enough if a good algorithm was used. Obviously some profiling would have to be done to tell if this was likely to be enough to make the difference but it could be an entertaining (and perhaps rewarding) project for someone who likes low level bit twiddling.
Project 11: Experimental: Order Heuristics for Claps
Task - Create a heuristic for program ordering in clasp, or show why one
is not possible.
Description - The efficiency of the answer set solver Claps seems to be highly dependent on the ordering of the rules in the logic program it tries to solve. The objective of this project is come up with a heuristic for the rule ordering.
Description - The efficiency of the answer set solver Claps seems to be highly dependent on the ordering of the rules in the logic program it tries to solve. The objective of this project is come up with a heuristic for the rule ordering.
Project 13: SSH Key Distribution
Task - Write a collection of scripts to allow easy and safe distribution of ssh keys.
Description - TecSH or SSH is the most widely used technology for remote access and administration on Linux and UNIX systems. It uses public key cryptography to authenticate the remote server and symmetric key cryptography to protect against eavesdropping and modification. The one key weakness in the system is the lack of a widely used system to distribute the keys of SSH servers, allowing for 'man in the middle' style attacks. A number of solutions have been proposed but none have been implemented widely. This projects aims to create a simple series of scripts that allow a group of users, possibly in different administrative domains to publish and share keys and verification information - all of which are then available via an SSH session to a central server. Users can then use their own criteria for deciding whether they trust the key(s) they receive from the system (i.e. trusting that the person running the central server as sufficiently verified all users, checking GPG signatures supplied with each key, etc.).
Description - TecSH or SSH is the most widely used technology for remote access and administration on Linux and UNIX systems. It uses public key cryptography to authenticate the remote server and symmetric key cryptography to protect against eavesdropping and modification. The one key weakness in the system is the lack of a widely used system to distribute the keys of SSH servers, allowing for 'man in the middle' style attacks. A number of solutions have been proposed but none have been implemented widely. This projects aims to create a simple series of scripts that allow a group of users, possibly in different administrative domains to publish and share keys and verification information - all of which are then available via an SSH session to a central server. Users can then use their own criteria for deciding whether they trust the key(s) they receive from the system (i.e. trusting that the person running the central server as sufficiently verified all users, checking GPG signatures supplied with each key, etc.).
Project 13: A Teaching Compiler
Task - Write a compiler designed to assist novel programmers
Description - Many students learning programming for the first time find compilers and particularly compiler error message s very confusing and intimidating. Compiler error messages are conventionally written from the point of view of what is technically incorrect in a section of code while most novice users want to know /what/ they can do to solve the problem. The aim of this project is to build a compiler for helping to teach people C. Error messages need to be clear, concise and written with the intention of helping the student not only understand what they need to do to fix their program, but why it was wrong. It is strongly suggested that the 'back end' of another compiler suite, such as GCC is used to minimise the amount of code that must be written. Speed, quality of code and size of the language subset implemented are less important than how useful it is for students learning C.
Description - Many students learning programming for the first time find compilers and particularly compiler error message s very confusing and intimidating. Compiler error messages are conventionally written from the point of view of what is technically incorrect in a section of code while most novice users want to know /what/ they can do to solve the problem. The aim of this project is to build a compiler for helping to teach people C. Error messages need to be clear, concise and written with the intention of helping the student not only understand what they need to do to fix their program, but why it was wrong. It is strongly suggested that the 'back end' of another compiler suite, such as GCC is used to minimise the amount of code that must be written. Speed, quality of code and size of the language subset implemented are less important than how useful it is for students learning C.
Other projects on low level systems hackery, experimental work using ASP, implementation of ASP/SAT/CSP solvers and parallelism are possible.