Reliability-Aware Multi-UAV Coverage Path Planning

Abstract

Robotic systems are particularly vulnerable to faults given the real world conditions that
they must operate in. This is best demonstrated in Unmanned Aerial Vehicle (UAV)
systems which can quite easily exceed operational parameters in bad weather conditions
in applications such as structural inspection around exposed bridges or wind turbines. A solution
is a multi-robot system which can not only be fault-tolerant, but increase efficiency as well.
However, this introduces the problem of multi-robot coordination, where this work is interested
in Graceful Degradation in which the mission can still be completed in a performant manner
despite the failure of one or more of its parts. Traditional approaches mostly focus on improving
the reliability of the individual robots, however that does not remove the possibility of failure.
Through the lens of coverage path planning, this thesis explores a novel approach to multi-robot
coordination. Many existing fault tolerant multi-robot planning methods primarily consider
robustness and resilience as primary goals, but these do not quantify performance as the system
degrades. This thesis investigates the use of overall mission reliability as a potential optimisation
metric for multi-robot coverage path planning where reliability can be defined as the probability
of mission completion.
A novel metric called ‘Probability of Completion’ (PoC) is introduced based on a ‘work done’
representation of a path plan and it is explored for the purpose of quantifying reliability. Through
exhaustive evaluation of all possible multi-agent path plans a number of key properties of a
reliable path plan are investigated where it is shown that there exists a trade space of optimal
paths trading off efficiency with reliability. With this metric, the Reliability-Aware Coverage
Path Planning Problem (RA-MCPP) is formally presented, initially for discrete graph-based
environments and later extended to continuous environments. A number of different optimisation
methods are explored for solving the RA-MCPP problem in environments of different sizes,
including a Mixed Integer Linear Program and Genetic Algorithm based approaches. A method
termed the Greedy Genetic Algorithm, which takes advantage of the submodularity of PoC, is
shown to provide reasonably good solutions in a scalable manner in some realistic 3D graph-based
environments. In order to validate these methods, a real life experiment is performed with 3
UAVs where it is shown that the reliability-aware path plan provides a significant increase
in probability of completion compared to existing partition based MCPP methods. An original
container based ‘Starling’ framework developed to enable this experiment, and other single and
multi-UAV research is also described. Finally, a path towards Online RA-MCPP with receding
horizon replanning is briefly explored where it is concluded through simulations that online
re-planning has the potential to improve the probability of completion over a-priori reliability
aware path plans.
Through this thesis it is demonstrated that these reliability-aware methods are both scalable
and applicable to real world problems, and have the potential to improve the reliability of
multi-robot coverage missions in the face of faulty robots

Date of Award	1 Oct 2024
Original language	English
Awarding Institution	University of Bristol
Supervisor	Arthur G Richards (Supervisor) & Mahesh Sooriyabandara (Supervisor)