Testing Robotics and Autonomous Systems Using Search-based Techniques

Robotics and Autonomous Systems (RAS) are becoming indispensable for human productivity and it is estimated that there will be a £13 billion global market for RAS by 2025. These are very complex systems (e.g. self-driving cars, unmanned aerial vehicles, medical robots), which have a high impact in our society, are becoming ubiquitous and need rigorous testing, to ensure their correct functioning and also the safety of the humans interacting with them. Testing them is a big challenge previously referred to as `testing the untestable’, due to their continuous interactions with the environment, system uncertainties, deep intertwining of software and hardware, and inclusion of safety critical deep learning software - for example, recent advances in Deep Neural Networks (DNN) have led to the development of DNN-driven autonomous cars.

Despite numerous efforts of the verification and validation community, their verification suffers from problems of scale and practicality. On the other hand, traditional testing methods are not sufficient, as demonstrated by recent studies and autonomous systems prototypes, such as self-driving cars deployed in urban traffic, which caused several car crashes and even fatal accidents.

In this project we propose a search-based testing approach for RAS, complementing metaheuristic search techniques with metamorphic testing and machine learning, in order to provide automated detection of failures and safety-critical scenarios.

Search-Based Software Testing (SBST), the most studied sub-domain of Search-Based Software Engineering (SBSE), represents the application of optimization (or metaheuristic) algorithms to problems in software testing. The metaheuristics are used to explore the very large input spaces, guided by a fitness function designed for the particular testing problem, and direct the search towards more promising candidates. SBST is a mature field with many success stories in automating test generation, such as EvoSuite testing tool for Java, Sapienz for Android, which is used at Facebook, and other industry adoptions at Microsoft, Ericsson and DaimlerChrysler. It is a fast growing area in software testing that provides a comprehensive toolbox for tackling a variety of problems and has been adopted due to its automation potential, versatility in solving complex, NP-hard or multi-objective problems and its flexibility, that makes it possible to hybridize it with other methods.

SBST has been used in recent years for testing some aspects of Cyber-Physical Systems (CPS), such as continuous controllers, automatic generation and prioritisation of reactive test cases, uncertainty-wise test case generation. In the automotive industry SBST has been applied for testing autonomous parking systems, self-driving cars software aspects such as lane keeping, vision-based control and

other driver-assistance features. These initial studies have shown that there is a potential for SBST to fill in the gaps in testing RAS - their complex environment, with large parameter space, would benefit from SBST methods.

The project will focus on applying SBST enhanced with Metamorphic Testing (MT) and Machine Learning (ML) approaches, to achieve the following main objectives.

Objective 1: Automating detection of safety critical scenarios. The project will focus on applying SBST techniques for detecting critical behaviours. As the fitness functions are crucial for guiding the search, defining and improving fitness functions for RAS testing will be one main objective, followed by analysing their landscape and choosing the most appropriate search algorithms.

Objective 2: Testing deep learning components of RAS software. As deep learning is widely used in RAS, for example DNN-self-driving cars, there is a common effort in the ML and also the testing community to ensure their correct behaviour. The current practice includes adversarial ML testing, e.g. finding inputs that, when changed minimally from their original versions, get classified differently, novel metamorphic approaches, which have been applied to driverless cars, and DNN coverage criteria.