Text only

CM30076 / CM30082
Individual Project

Project Ideas

Dr Marina De Vos

mdv@cs.bath.ac.uk

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 Dr. Barry for such a project). More information and additional project ideas can be found on my webpage

Area of Logic Programming and Knowledge Representation

General Game Playing in ASP (challenging)
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.
Clima Competition Agent in ASP
This project seeks to implement an agent capable of entering the Clima VII competition. The agent should use ASP as its core computational logic formalism.
Finite State Autonoma Generation (challenging)
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.
A Planning Front-end for ASP
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. One popular application of ASP is in planning and scheduling problems. However implementing these can be somewhat daunting to users without any knowledge of ASP. This project is to create a suit able GUI to help convert between intuitive concepts, such as the dependance between tasks, number of staff, amount of resources, etc. and ASP. It is envisaged that the user would have a way of specifying the number of people, tasks, resources, objects, location and time steps involved in a plan as well as the dependan cies between them and then have the tool generate a suitable plan of action.
Modelling Institutions in ASP
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.
Compute Time Estimator for ASP
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.
A Logic Programming Agent Framework
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. One of application areas for answer set programming is the representation of agents' knowledge and reasoning capabilities exist. The aim of this project is to write a multi-agent framework where the internals of the agents are represented as answer set programs.
Estimating Answer Set Density
Answer set density can be computed as the total number of an swer sets divided by the number of answer sets and number of conflicts found (and is thus solver dependant - but this s 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.
An open Implementation of DLT
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 licence. It is suggested that either perl or the C preprocessor is used to handle macro expansion.
A Logic Programming Tutor
This project aims to produce a software product capable of explaining undergraduate students how answer set programs and their respective solvers work.
Modular IDEAS (challenging)
IDEAS is an incremental answer set solver developed by a past student. This project aims to extend both theory and implementation such that multiple rules can be added or subtracted.

Area of Programming Tools

Call Graphing in C
Understanding large and often complex programs in a short space of time is a very common task. It is difficult not because of the lack of information - the source code contains everything that is needed, the key problem is accessibility. It is very difficult to get an overview of how a program works by simply reading sections of the source code. Tools such as LXR help as they make it easier to read the code but there is still room for an whole range of tools that summarise the information in the s ource code and display it in a useful format. This project aims to implement a prototype of such a tool. The first step is to create a graph from a series of in files containing C, with nodes representing functions and directed links representing the 'is called by' relation and to be able to output the graph in some pictorial form (a tool such as DaVinci is recommended for this). Extensions could be adding different types of arrow for 'may be called', 'definitely called', 'called repeatedly', etc. adding outline of control flow structures to the nodes so how the functions are called is easier to see, tracing which variables are passed between functions, handling callbacks and handling other languages.