The n-city problem and other probabilistic optimisation problems.

The aim of this thesis is to design and analyse probabilistic reinforcement-learning optimisation algorithms inspired by real-life phenomena such as ants finding the shortest path between their nest and a source of food, or a slime mold called physarum being able to ``compute'' optimal transport networks between several sources of food.

State of the Art: Ant Colony Optimisation
A whole branch of computer science, called Ant Colony Optimisation (ACO) - see the book ACO of Dorigo and Stutzle - is inspired by the phenomenon of ants being able to find shortest paths with no means of communication besides the pheromones they lay behind them. This natural phenomenon is modelled by computer scientists by reinforcement-learning algorithms, and the algorithms they have designed can solve difficult optimisation problems such as finding the shortest paths between two nodes in a network.
In a series of two papers, Kious, Mailler and Schapira have introduced the first probabilistic model for this phenomenon of ants finding the shortest paths between their nest and a source of food. They are able to show rigorous results about these models: eg, in what they call the ``loop-erased ants process'', the ants do indeed find the shortest paths between two nodes in a series-parallel graph.

Subject of the PhD thesis: a model for finding optimal transport networks
The physarum is a slime mold capable of finding ``optimal transport networks'' (see Rules for Biologically Inspired Adaptive Network Design, by Tero et al, Science, January 2010). Just as ants finding shortest paths, it is believed that this phenomenon can be modelled using reinforcement-learning. The aim of this PhD thesis is to design a probabilistic model for this phenomenon and prove that it indeed finds ``optimal'' transport networks.
The first attempt in this direction will be to generalise the ant process of Kious, Mailler and Schapira to a model with more than two special nodes: the nest and the source of food will be replaced by an arbitrary number of ``cities''; the aim of the ``ants'' will be to find the optimal transport network between these cities. The two main challenges of this first objective of the PhD thesis are: 1- the ants process is already difficult to analyse rigorously (Kious et al only obtain partial results) and we expect this generalisation to be even more intricate, and 2- the definition of an ``optimal'' transport network is not unique.
The second attempt will be to design a probabilistic version of a mean-field version from the PDE literature: see Physarum Can Compute Shortest Paths, by Bonifaci, Mehlhorn, and Varma. It will then be interesting to 1- show that this probabilistic algorithm indeed return (some) optimal transport network, and 2- compare this algorithm to the ``multi-city'' version of the ants process of Kious et al.

Combining specialised modelling techniques with complex data analysis in order to deliver prediction with quantified uncertainties lies at the heart of many of the major challenges facing UK industry and society over the next decades. Indeed, the recent Government Office for Science report "Computational Modelling, Technological Futures, 2018" specifies putting the UK at the forefront of the data revolution as one of their Grand Challenges.

The beneficiaries of our research portfolio will include a wide range of UK industrial sectors such as the pharmaceutical industry, risk consultancy, telecommunications and advanced materials, as well as government bodies, including the NHS, the Met Office and the Environment Agency.

Examples of current impactful projects pursued by students and in collaboration with stake-holders include:

- Using machine learning techniques to develop automated assessment of psoriatic arthritis from hand X-Rays, freeing up consultants' time (with the NHS).

- Uncertainty quantification for the Neutron Transport Equation improving nuclear reactor safety (co-funded by Wood).

- Optimising the resilience and self-configuration of communication networks with the help of random graph colouring problems (co-funded by BT).

- Risk quantification of failure cascades on oil platforms by using Bayesian networks to improve safety assessment for certification (co-funded by DNV-GL).

- Krylov regularisation in a Bayesian framework for low-resolution Nuclear Magnetic Resonance to assess properties of porous media for real-time exploration (co-funded by Schlumberger).

- Machine learning methods to untangle oceanographic sound data for a variety of goals in including the protection of wildlife in shipping lanes (with the Department of Physics).

Future committed partners for SAMBa 2.0 are: BT, Syngenta, Schlumberger, DNV GL, Wood, ONS, AstraZeneca, Roche, Diamond Light Source, GKN, NHS, NPL, Environment Agency, Novartis, Cytel, Mango, Moogsoft, Willis Towers Watson.

SAMBa's core mission is to train the next generation of academic and industrial researchers with the breadth and depth of skills necessary to address these challenges. SAMBa's most sustained impact will be through the contributions these researchers make over the longer term of their careers. To set the students up with the skills needed to maximise this impact, SAMBa has developed a bespoke training experience in collaboration with industry, at the heart of its activities. Integrative Think Tanks (ITTs) are week-long workshops in which industrial partners present high-level research challenges to students and academics. All participants work collaboratively to formulate mathematical
models and questions that address the challenges. These outputs are meaningful both to the non-academic partner, and as a mechanism for identifying mathematical topics which are suitable for PhD research. Through the co-ownership of collaboratively developed projects, SAMBa has the capacity to lead industry in capitalising on recent advances in mathematics. ITTs occur twice a year and excel in the process of problem distillation and formulation, resulting in an exemplary environment for developing impactful projects.

SAMBa's impact on the student experience will be profound, with training in a broad range of mathematical areas, in team working, in academic-industrial collaborations, and in developing skills in communicating with specialist and generalist audiences about their research. Experience with current SAMBa students has proven that these skills are highly prized: "The SAMBa approach was a great template for setting up a productive, creative and collaborative atmosphere. The commitment of the students in getting involved with unfamiliar areas of research and applying their experience towards producing solutions was very impressive." - Dr Mike Marsh, Space weather researcher, Met Office.