I am offering the following projects in 2016-17 academic year. Each project clearly specifies whether it can be done on the undergraduate, MSci, or MSc level.

All topics are related to my research interests, and some have a potential for a research paper or a continuation as a research topic.

Please note that all projects contain a theoretical and a practical part (implementation). You will be required to submit your source code as a part of the project report, and to include a demo of your implementation in your final project presentation.

The project is done in collaboration with the University of Bristol and Bristol Robotic Lab. n the domain of human-robot interaction (HRI), we need to ensure that systems consisting of robots and human agents perform correctly. Typically, correctness of systems is assessed by testing them. However, when the system contains a robot and a human, it is more complicated to generate interesting tests. Moreover, sometimes we do not know the robot's code completely (maybe it was built by a third party, or maybe it is an upgrade), so we need to deduce its behaviour from test execution. This project consists of the first steps towards deducing the robot behaviour. It is based on the software and robots developed in the University of Bristol.

**The structure of the project is as follows:**

- Execute the existing tests on the human-robot system. Observe the robot's behaviour.
- In the same system, assume that the code for the robot is unknown.
- Use the learning algorithm (available from the open source libalf library) to construct a finite automaton A that represents the behaviour of the robot.
- Compare the results of running tests with A plugged in instead of the original code of the robot.
- Draw conclusions about the possibility of learning the robot behaviour.
- For MSci and MSc: use the learning algorithm to suggest new tests and improve the quality of the test suite.

The first step is reading a paper on modeling robot's behaviour in a human-robot system from the University of Bristol:

Illan, DA, Pipe, AG & Eder, KI, 2016, ‘Intelligent
Agent-Based Stimulation for Testing Robotic Software in Human-Robot
Interactions’. in: *2016 Third Workshop on Model-Driven Robot Software
Engineering (MORSE 16)*. ACM (available from Prof. Eder's home page).

Regular languages given as finite automata are used widely in verification of hardware and software as means to verify the correctness of computations. The computations, which are recordings of executions of real system, are usually very long. If a computation fails (that is, there is a bug in the program), finding the closest non-failing computation might help in fixing the problem. The goal of this project is, given word W and a finite automaton A, such that W is not accepted by A, to compute the closest word to W that is accepted by A. The definition of closest should be researched and several approaches compared. The skills you need for this project include: Good knowledge of the theory of automata; Good ability to search for scientific material and apply critical thinking; Good programming skills in a language of your choice.

**The structure of the project is as follows:**

- Research of different types of distance metrics and choosing the metric.
- An algorithm for computing the closest word and a justification for the choice of metric.
- An implementation of the algorithm.
- Optimisations.
- Experimental results of running the algorithm on a set of words and several different automata.

This
project continues the undergraduate summer research project for computing
causes, responsibility, and blame. The project is based on the defintitions of
structural causality, responsibility, and blame, and it provides an efficient
algorithm together with a graphical interface to compute causes of events and
to visualise the causal paths in the model. The results of the project lend
themselves to detection of efficient interventions, and potentially can be used
for policy making.

**Deliverables:**

- An efficient algorithm for computing structural
causality based on J. Halpern's paper from 2015.
- The extension of this algorithm to compute
responsibility.
- Optimisations and complexity analysis.
- Experiments on real problems, including causes for
radicalisation.

This project can be taken only by the students returning from the year in industry and is done in collaboration with the company in which the student worked during the placement. The project should be useful for the company as well as fulfil the requirements for a final year project. Students interested in taking it should discuss with me and with the company. It is possible to book several students on this project.

Learning algorithms became very popular in the recent years, and especially the classic algorithm by D. Angluin for learning a deterministic finite automaton that accepts an unknown language. This algorithm is now widely used in validation of software programs, for modelling software components, compact representation of log files, and visualising erroneous behaviours of the program.

This project includes understanding of the algorithm and implementing it in Java in an efficient way. The MSci and MSc versions include the optimisation by Rivest&Shapire.

**Relevant
literature: **

- Dana Angluin:

Learning Regular Sets from Queries and Counterexamples. Inf. Comput. 75(2): 87-106 (1987) - Ronald
L. Rivest, Robert E. Schapire: Inference of Finite Automata Using Homing
Sequences. Information and Computation 103(2): 299-347 (1993). - only for the MSci and MSc
levels.

In
avionics software, decisions can depend on complex compound conditions. For
example, decisions on whether to accelerate or to raise the altitude of the
aircraft can depend on the current altitude, weather conditions, reports from
the air traffic control, fuel status, etc. Since the software for avionics
systems is mission-critical, it is very important to construct test suites that
check the software as exhaustively as possible. The goal of this project is,
given a complex compound condition (a Boolean formula) to construct a set of
test cases to check multiple condition coverage and MC/DC. The project should
include a user-friendly GUI. The project, if successful, will serve as a
learning aid for the Software Measurement and Testing / Advanced Software
Engineering module.

**Skills needed for the project:**

- Module 6CCS3SMT/7CCSMASE or equivalent knowledge.
- Good programming skills in a language of your choice

**Deliverables:**

- Intermediate deliverable: a set of test cases (truth
value assignment) to check multiple condition coverage.
- Final deliverable - code part: a set of truth value
assignments to check MC/DC.
- Final deliverable - GUI part: presenting the results in
a user-friendly way.

The
project should be consistent with requirements for an UG, MSci,
or MSc level project. I will consider supervising projects close to my area
of expertise (see my homepage). |