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

University of Bath Logo
Dr Marina De Vos
Department of Computer Science
Friday, 24-Nov-2017 20:32:23 GMT

Undergraduate Project Suggestions 2006 - 2007

On this page you can find a number of project suggestions for final year students. Feel free to contact me with suggestions of your own.

These are the current project suggestions:

  1. Project 1: General Game Playing in ASP
  2. Project 2: Clima Competition Agent in ASP
  3. Project 3: Finite State Autonoma Generation
  4. Project 4: A Planning Front-End for ASP
  5. Project 5: Modelling Institutions in ASP
  6. Project 6: Compute Time Esitmator for ASP
  7. Project 7: A Logic Programming Agent Framework
  8. Project 8: Estimating Answer Set Density
  9. Project 9: An Open Implementation of DLT
  10. Project 10: A Logic Programming Tutor
  11. Project 11: Modular IDEAS
  12. Project 12: Call Graphing in C

Project 1: General Game Playing in ASP

Task - Write a GGP player with an answer set 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: Clima Competition Agent in ASP

Task - Write an agent capable of entering the Clima Competition.

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

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.



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: A Planning Front-End for ASP

Task - Write a graphical planning front-end to aid novel ASP users.

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



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: 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 7: A Logic Programming Agent Framework

Task - Develop and implement a framework for multi-agent systems where the agents are using ASP to reason.

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



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




Project 10: A Logic Programming Tutor

Task - Write a tutor for novel ASP users.

Description - This project aims to produce a software product capable of explaining undergraduate students how answer set programs and their respective solvers work.



Project 11: Modular IDEAS

Task - Extend IDEAS to allow for increments/decrements of any number of rules.

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



Project 12: Call Graphing in C

Task - Write a tool to support call graphing in C.

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