On the Design, Analysis, and Evaluation of Online Strategies for the Multi-Robot Patrolling Problem

Abstract

Environmental monitoring and infrastructure security with teams of mobile autonomous robots has utility within a variety of scenarios. Within this field, the concept of the “multi-robot patrolling problem” presents the formalisation of multi-agent teams moving throughout graph-structured environments to achieve frequent visits to graph vertices, representing points of interest in the environment. The use of decentralised online strategies for multi-agent decision making in the multi-robot patrolling problem has seen significant attention in the literature, but comparisons of patrol strategy performance are inconsistent and do not present unified, thorough analysis of patrol behaviours. In this thesis, we address this problem. We present a range of novel decentralised online patrol strategies, resulting in not only leading levels of patrol performance but also significant insight into effective patrol strategy
design. We then consider complications to patrol which reflect plausible real-world scenarios: the presence of intelligent attackers attempting to gain undetected access to the patrol scenario, dynamically varying patrol graph weights within a patrol scenario, and the impact of imperfect communications on inter-agent coordination.
Beyond new patrol strategies, the findings presented in this thesis represent an important step towards effective analysis of patrol behaviours in practical scenarios. This is of significant value to potential future real-world deployments, as it allows greater levels of confidence in high levels of performance and robustness in complex scenarios.

Date of Award	6 Feb 2026
Original language	English
Awarding Institution	University of Bristol
Supervisor	Edmund R Hunt (Supervisor) & Arthur G Richards (Supervisor)