One of the major drivers of research in the area of humanoid robotics is the desire to achieve motions involving close contact between robots and the environment or people, such as while carrying an injured person, handling flexible objects such as the straps of a knapsack or clothes. Currently, these applications seem beyond the ability of existing motion synthesis techniques due to the underlying computational complexity in an open-ended environment. Traditional methods for motion synthesis suffer from two major bottlenecks. Firstly, a significant amount of computation is required for collision detection and obstacle avoidance in the presence of numerous close contacts between manipulator segments and objects. Secondly, any particular computed solution can easily become invalid as the environment changes. For instance, if the robot were handling an object such as a knapsack, even small deformations of this flexible object and minor changes in object dimensions (e.g., between an empty bag and a stuffed bag) might require complete re-planning in the current way of solving the problem. Similar issues arise in the area of computer animation, where there is a need for real-time control of characters - moving away from static sequences of pre-programmed motion. Although it may seem that this world is much more contained, as it is created by an animation designer, there is in fact a strong desire to create games and simulation systems where the users get to interact with the world continually and expect the animation system to react accordingly. This calls for the same sort of advances in motion synthesis techniques as outlined above.The fundamental problem lies in the representation of the state of the world and the robot. Typically, motion is synthesizes in a complete configuration or state space represented at the level of generalized coordinates enumerating all joint angles and their 3D location/orientation with respect to some world reference frame. This implies the need for large amounts of collision checking calculations and randomized exploration in a very large search space. Moreover, it is very hard to encode higher level, semantic, specifications at this level of description as the individual values of the generalized coordinates do not tell us anything unless further calculations are carried out to ensure satisfaction of relevant constraints. This is particularly inconvenient when searching for a motion in a large database. The focus of this research is to alleviate these problems by developing methods that exploit the underlying topological structure in these problems, e.g., in the space of postures. This allows us to define a new search space where the coordinates are based on topological relationships, such as between link segments. We refer to this space in terms of 'topology coordinates'. In preliminary work, we have shown the utility of this viewpoint for efficient motion synthesis with characters that are in close contacts. We have also demonstrated that this approach is more efficient for categorizing semantically similar motions. In this project, we will develop a more general framework of such techniques that will be applicable to a large class of tasks carried out by autonomous humanoid robots and virtual animated characters. Moreover, we will implement our techniques on industrially relevant platforms, through our collaborators at Honda Research Institute Europe GmbH and Namco Bandai, Japan.

Evolutionary algorithms (EAs) have been applied to solve many stationary problems. However, real-world problems are usually more complex and dynamic, where the objective function, decision variables, and environmental parameters may change over time. In this project, we will investigate novel EA approaches to address dynamic optimisation problems (DOPs), a challenging but very important research area. The proposed research has three main aspects: (1) designing and evaluating new EAs for DOPs in collaboration with researchers from Honda Research Institute Europe, (2) theoretically analysing EAs for DOPs, and (3) adapting developed EA approaches to solve dynamic telecommunication optimisation problems. In this project, we will first construct standardised, both discrete and continuous, dynamic test environments based on the concept of problem difficulty, scalability, cyclicity and noise of environments, and standardised performance measures for evaluating EAs for DOPs. Based on the standardised dynamic test and evaluation environment, we will then design and evaluate novel EAs and their hybridisation, e.g., Estimation of Distribution Algorithms (EDAs), Genetic Algorithms, Swarm Intelligence and Adaptive Evolutionary Algorithms, for DOPs based on our previous research. A guiding idea here is to improve EA's adaptability to different degrees of environmental change in the genotypic space, be it binary or not. Systematically and adaptively combining dualism-like schemes for significant changes, random immigration-like schemes for medium changes, and general mutation or variation schemes for small changes, is expected to greatly improve EA's performance in different dynamic environments. And memory schemes can be used when the environment involves cyclic changes. In order to better understand the fundamental issues, theoretical analysis of EAs for DOPs will be pursued in this project. We will apply drift analysis and martingale theory as the starting point to analyse the computational time complexity of EAs for DOPs and the dynamic behaviour of EAs for DOPs regarding such properties as tracking error, tracking velocity, and reliability of arriving at optima. Based on the above EA design, experimental evaluation, and formal analysis, we will then develop a generic framework of EAs for DOPs by extracting key techniques/properties of efficient EAs for DOPs and studying the relationship between them and the characteristics of DOPs being solved with respect to the environmental dynamics in the genotypic space. Another key aspect of this project is to apply and adapt developed EAs for general DOPs to solve core dynamic telecommunications problems, e.g., dynamic frequency assignment problems and dynamic call routing problems, in the real world. We will closely collaborate with researchers from British Telecommunications (BT) to extract domain-specific knowledge and model dynamic telecommunication problems using proper mathematical and graph representations. The obtained domain knowledge will be integrated into our EAs for increased efficiency and effectiveness. All algorithms and software developed in this project will be made available publicly to benefit as many users as possible, whether they are from academe or industry.

Evolutionary algorithms (EAs) have been applied to solve many stationary problems. However, real-world problems are usually more complex and dynamic, where the objective function, decision variables, and environmental parameters may change over time. In this project, we will investigate novel EA approaches to address dynamic optimisation problems (DOPs), a challenging but very important research area. The proposed research has three main aspects: (1) designing and evaluating new EAs for DOPs in collaboration with researchers from Honda Research Institute Europe, (2) theoretically analysing EAs for DOPs, and (3) adapting developed EA approaches to solve dynamic telecommunication optimisation problems. In this project, we will first construct standardised, both discrete and continuous, dynamic test environments based on the concept of problem difficulty, scalability, cyclicity and noise of environments, and standardised performance measures for evaluating EAs for DOPs. Based on the standardised dynamic test and evaluation environment, we will then design and evaluate novel EAs and their hybridisation, e.g., Estimation of Distribution Algorithms (EDAs), Genetic Algorithms, Swarm Intelligence and Adaptive Evolutionary Algorithms, for DOPs based on our previous research. A guiding idea here is to improve EA's adaptability to different degrees of environmental change in the genotypic space, be it binary or not. Systematically and adaptively combining dualism-like schemes for significant changes, random immigration-like schemes for medium changes, and general mutation or variation schemes for small changes, is expected to greatly improve EA's performance in different dynamic environments. And memory schemes can be used when the environment involves cyclic changes. In order to better understand the fundamental issues, theoretical analysis of EAs for DOPs will be pursued in this project. We will apply drift analysis and martingale theory as the starting point to analyse the computational time complexity of EAs for DOPs and the dynamic behaviour of EAs for DOPs regarding such properties as tracking error, tracking velocity, and reliability of arriving at optima. Based on the above EA design, experimental evaluation, and formal analysis, we will then develop a generic framework of EAs for DOPs by extracting key techniques/properties of efficient EAs for DOPs and studying the relationship between them and the characteristics of DOPs being solved with respect to the environmental dynamics in the genotypic space. Another key aspect of this project is to apply and adapt developed EAs for general DOPs to solve core dynamic telecommunications problems, e.g., dynamic frequency assignment problems and dynamic call routing problems, in the real world. We will closely collaborate with researchers from British Telecommunications (BT) to extract domain-specific knowledge and model dynamic telecommunication problems using proper mathematical and graph representations. The obtained domain knowledge will be integrated into our EAs for increased efficiency and effectiveness. All algorithms and software developed in this project will be made available publicly to benefit as many users as possible, whether they are from academe or industry.

One in six people in the UK have a hearing impairment, and this number is certain to increase as the population ages. Yet only 40% of people who could benefit from hearing aids have them, and most people who have the devices don't use them often enough. A major reason for this low uptake and use, is the perception that hearing aids perform poorly. Perhaps the most serious problem is hearing speech in noise. Even the best hearing aids struggle in such situations. This might be in the home, where the boiling kettle forces conversations with friends to stop, or maybe in a railway station, where noise makes it impossible to hear announcements. If such difficulties force the hearing impaired to withdraw from social situations, this increases the risk of loneliness and depression. Moreover, recent research suggests hearing loss is a risk factor for dementia. Consequently, improving how hearing devices deal with speech in noise has the potential to improve many aspects of health and well-being for an aging population. Making the devices more effective should increase the uptake and use of hearing aids. Our approach is inspired by the latest science in speech recognition and synthesis. These are very active and fast moving areas of research, especially now with the development of voice interfaces like Alexa. But most of this research overlooks users who have a hearing impairment. There are innovative approaches being developed in speech technology and machine learning, which could be the basis for revolutionising hearing devices. But to get such radical advances needs more researchers to consider hearing impairments. To do this, we will run a series of signal processing competitions ("challenges"), which will deal with increasingly difficult scenarios of hearing speech in noise. Using such competitions is a proven technique for accelerating research, especially in the fields of speech technology and machine learning. We will develop simulation tools, models and databases needed to run the challenges. These will also lower barriers that currently prevent speech researchers from considering hearing impairment. Data would include the results of listening tests that characterise how real people perceive speech in noise, along with a comprehensive characterisation of each test subject's hearing ability, because hearing aid processing needs to be personalised. We will develop simulators to create different listening scenarios. Models to predict how the hearing impaired perceive speech in noise are also needed. Such data and tools will form a test-bed to allow other researchers to develop their own algorithms for hearing aid processing in different listening scenarios. We will also challenge researchers to improve our models of perception. The scientific legacy of the project will be improved algorithms for hearing aid processing; a test-bed that readily allows further development of algorithms, and more speech researchers considering the hearing abilities of the whole population.

Optimisation -- the problem of identifying a satisficing solution among a vast set of candidates -- is not only a fundamental problem in Artificial Intelligence and Computer Science, but essential to the competitiveness of UK businesses. Real-world optimisation problems are often tackled using evolutionary algorithms, which are optimisation techniques inspired by Darwin's principles of natural selection. Optimisation with classical evolutionary algorithms has a fundamental problem. These algorithms depend on a user-provided fitness function to rank candidate solutions. However, for real world problems, the quality of candidate solutions often depend on complex adversarial effects such as competitors which are difficult for the user to foresee, and thus rarely reflected in the fitness function. Solutions obtained by an evolutionary algorithm using an idealised fitness function, will therefore not necessarily perform well when deployed in a complex and adversarial real-world setting. So-called co-evolutionary algorithms can potentially solve this problem. They simulate a competition between two populations, the "prey" which attempt to discover good solutions, and the "predators" which attempt to find flaws in these. This idea greatly circumvents the need for the user to provide a fitness function which foresees all ways solutions can fail. However, due to limited understanding of their working principles, co-evolutionary algorithms are plagued by a number of pathological behaviours, including loss of gradient, relative over-generalisation, and mediocre objective stasis. The causes and potential remedies for these pathological behaviours are poorly understood, currently limiting the usefulness of these algorithms. The project has been designed to bring a break-through in the theoretical understanding of co-evolutionary algorithms. We will develop the first mathematically rigorous theory which can predict when a co-evolutionary algorithm reaches a solution efficiently, and when pathological behaviour occurs. This theory has the potential to make co-evolutionary algorithms a reliable optimisation method for complex real-world problems.