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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.).

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.