Plain text version | Style: Default, Black and White, Bath

University of Bath Logo
Dr Marina De Vos
Department of Computer Science
Thursday, 19-Oct-2017 00:59:23 BST

Undergraduate Project Suggestions 2008 - 2009

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 Project Coordinator for such a project).

These are the current project suggestions:

  1. Project 1: General Game Playing in ASP
  2. Project 2: APE: An IDE for ASP (Continuation)
  3. Project 3: "SETI@Home" Style Answer Set Solver
  4. Project 4: Situation/Event Calculus in ASP
  5. Project 5: Modelling Institutions in ASP
  6. Project 6: Reasoning about Web-Services with ASP
  7. Project 7: Automatic generation of plug-ins for MiniSAT
  8. Project 8: UltraSPARC T1 or ccNuma core for Platypus
  9. Project 9: Implementing an Answer Set Solver
  10. Project 10: LaTeX support for CS projects

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.





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.





Project 3: "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.





Project 4: Situation/Event Calculus in ASP

Task - Develop an ASP front-end and back-end for the Situation or Event Calculus

Description -The situation and event calculi are both temporal logics that are used in multi-agent systems. For the computational side they are traditionally mapped to a Prolog program. For this project, we would like to change Prolog to Answer Set Programming. This requires both a front-end and back-end. The former is responsible for mapping the calculus to an ASP program while the latter translates the answer sets to the requested query. A good starting point for investigations could be the incremental solver developed by the University of Potsdam.





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.





Project 6: Reasoning about Web-Services with ASP (Joint with Dr. Padget)

Task - Develop an ASP reasoning toold for Web-Services

Description - Web-services are (in an ideal world) semantically annotated programmes that have a web-presence and can be run remotely run. They are often used in workflows. Given a description of a task is the responsibility of the broker and the matchmaker to find the appropriate web-service(s) to successfully complete the task. For this project, we want to investigate the appropriateness of Answer Set Programming, a logic programming language, for the description of and the reasoning about web-services.





Project 7: Automatic generation of plug-ins for MiniSAT (assisted by Mr. Martin Brain)

Task - Write a plug-in for Minisat that allows for arbitrary boolean constraints.

Description - MiniSAT and it's derivatives and descendants represent the state of the art in propositional automatic reasoning. They are used as the 'reasoning engine' in a variety of applications from circuit and processor verification to planning and scheduling. The MiniSAT algorithm has suitable interfaces so that objects representing arbitrary constraints to be 'plugged in'. This project is to write a program that takes an arbitrary boolean constraint and generates the /source code for the plug in.


Prerequisites: An understanding of (classical) propositional logic. An interest in theorem proving automatic reasoning. As most MiniSAT implementations are written in C or C++, thus experience in these languages would be an advantage.





Project 8: UltraSPARC T1 core for Platypus (assisted by Mr. Martin Brain)

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 programmer for this project. Platypus is written in C++. Also an active interest in machine architectures is necessary.





Project 9: Implementing an Answer Set Solver(Assisted by Mr. Martin Brain)

Task - Implement and test your own answer set solver

Description - Answer Set Programming is a declarative programming paradigm in which the programmer represents the problem using a logical style language, and uses an Answer Set Solver to compute solutions. This project is to write such a solver using the MiniSAT algorithm as a basis. An extension to this would be to adapt the solver to make efficient use of highly parallel, multi-core processors, such as the UltraSPARC T1.

Prerequisites: Reasonable programming ability, preferably in C / C++, although Java would also be an possibility. An interest in declarative programming and / or automated reasoning. A familiarity with multi-threaded / shared memory parallel programming would be an advantage.





Project 10: LaTeX support for CS projects (jointly with Prof. Davenport)

Task - Design a format and the accompanying preprocessor that allows a latex dissertation to pass through TurnItIn without false positives.

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.


Other projects on low level systems hackery, experimental work using ASP, implementation of ASP/SAT/CSP solvers and parallelism are possible.