## Msc. Project Suggestions 2005 - 2006

On this page you can find a number of project suggestions for students on the Msc. in Computer Science and Msc. Multi-Media Technology. Feel free to contact me with suggestions of your own.

These are the current project suggestions:

- Project 1: Estimating Answer Set Density
- Project 2: "SETI@Home" Style Answer Set Solver
- Project 3: Finite State Autonoma Generation
- Project 4: Incremental Propositional OCLP
- Project 5: Compute Time Estimator for ASP
- Project 6: Precomputing branching strategies for Logic Programs
- Project 7: An open implementation of DLT
- Project 8: DLV - Smodels Converter
- Project 9: Argumentation Frameworks
- Project 10: Playing Answer Set Programs as Games

### Project 1: 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 dependent - 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 2: "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 implementor 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 3: Finite State Autonoma Generation

**Task**- Implementing a program that translates a logic program into a finite state automaton that generates the same semantics

**Description**- When creating "intelligent systems" there are a variety of approaches that can be used. Finite State Autonoma are very fast and efficient to implement but are difficult and unintuitive to design and often difficult to prove. Logic programming gives a very simple and intuitive way of designing of creating sophisticated 'intelligent' systems but are often too slow to be used in time critical applications, such as games.

This project seeks to combine the advantages of both by generating finite state autonoma from logic programs. A logic program is developed that will plan one step of a solution, it is evaluated with respect to all possible states of the world and this used to build a planning graph with nodes corresponding to actions and links to changes in the state of the world, from the graph a finite state autonoma is then created.

The first step of the project would be to create tool to automate the process of creating autonoma from logic programs. Possible extensions are taking results on adding rules to logic programs and using them to update the finite state autonoma, creating a 'learning' system or to compare the performance of the tool against similar systems, such as qsmodels - a Quake 3 bot implemented using logic programming.

### Project 4: Incremental Propositional OCLP

**Task**- Implement an answer set solver for OCLP that solves a additions to a program incrementally.

**Description**- Logic Programming is a growing research field in artificial intelligence. With the introduction of answer set programming, logic programming has taken a new step in finding new application areas and efficient algorithms for solving represented problems. A good example is the use of answer set programming for the propulsion of the NASA space shuttles.

Ordered Choice Logic Programming (OCLP) is a recent logic programming formalism designed to model decision-making in an elegant and intuitive way such that the solutions of the represented problem can be obtained as the models of the logic program. The programs are equipped with two semantics: the skeptical and credulous answer set semantics.

Recently we have developed a program, called IASAI, that is capable of producing of computing the answer sets of a program incrementally. Whenever the program changes, the solver will use the previous answer sets to compute the new ones.

The goal of this project is to extend IASAI to ordered choice logic programs.

### Project 5: Compute Time Estimator for ASP

**Task**- Implement a mechanism for estimating the time it will take an answer set solved to return one or all answer sets of a given program.

**Description**- AnsProlog is a declarative logic programming system that is used at the University of Bath. Programs are made up of a series of rules, each of which expresses a simple statement about logical inference. There are no ways of estimating roughly how much compute time a program will need to produce answers - it can vary, largely independently of the size of the program. This projects aims at developing a rough heuristic for how long the program will take to compute. This can either be an absolute measure or relative to another program. In the case of a relative metric it may be useful to develop some common 'benchmarks' to check against. Implementing a tool that could assess this metric would be a useful extension.

### Project 6: Precomputing branching strategies for Logic Programs

**Task**- Design and possibly implement an algorithm that can suggest the best branching strategies for a solver given an answer set solver.

**Description**- AnsProlog, a declarative logic programming language used at the University of Bath works by computing what possible world views are consistent with the input program. The algorithms that compute these 'answer sets' all work in a similar fashion - they extend the set of information that is known as far as possible using inference rules, then they pick one of the unknown atoms and branch. One branch assume it to be true, the other assumes it to be false. Picking which atom to branch on makes a very significant difference to the performance of a system and currently a number of 'local' heuristics are used. These consider the short term effect of branching on each algorithm but do not consider the 'whole picture'.

This project aims to devise (and if possible implement) and algorithm that will take a logic program and produce an ordered list of which atoms it is best to branch on and in which order this should be done. This should help reduce the amount of compute time required to compute the answer sets of this program.

### Project 7: 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 preprocessor is used to handle macro expansion.

### Project 8: DLV - Smodels Converter

**Task**- Write program that translate ASP programs written in Smodels syntax to DVL syntax and vice versa.

**Description**- AnsProlog is a declarative logic programming system that is used at the University of Bath. Programs are made up of a series of rules, each of which expresses a simple statement about logical inference. Programs that compute the answer sets of a given program are called solvers. At present, Smodels and DLV are the most popular solvers, although others exist. Unfortunately, both solvers use different syntax for the answer set programs

The main aim of this projects is to design and implement a C program that can is capable of translating the syntax of DLV to Smodels and the other way around. Bonus points can be obtained if other solvers are also taken into account.

### Project 9: Argumentation Frameworks

**Task**- Write a program that generates the robust labellings of an argumentation framework or answer set program

**Description**- Labellings were designed to find the solutions of argumentation frameworks, which can elegantly be represented by means of graphs. Argumentation frameworks have demonstrated their usage in for example game theory and law. The first step of this project is to write a program with a graphical user interface that produces the robust labellings of an argumentation framework. For logic programs it was shown that they have an elegant representation as argumentation frameworks with a transformation based on proof trees. The second part is to incorporate this transformation into your program such that you can also take logic programs as input.

### Project 10: Playing Answer Set Programs as Games

**Task**- Write a program that takes an answer set program as input and returns its game tree and winning strategies

**Description**- AnsProlog is a declarative logic programming system that is used at the University of Bath. Programs are made up of a series of rules, each of which expresses a simple statement about logical inference. One way of looking at the semantics these programs is using logic games such that the answer sets and the winning strategies correspond.

The aim of this project to implement an algorithm and interface for computing the winning strategies of a program.