Decentralised Algorithms for Area Coverage

  • Sam J Young

Student thesis: Master's ThesisMaster of Science (MSc)

Abstract

Decentralised area coverage is a fundamental problem in swarm robotics, in which robots seek to disperse evenly across an area. Area coverage is the basis for many swarm applications from environmental monitoring and network deployment to cancer treatment using nanobots. Yet most implementations chose an area coverage strategy without a clear understanding of the tradeoffs they entail in terms of optimal performance, robot design, and environmental constraints.

In this paper we derive analytic lower bounds for optimal area coverage when the number of robots is large. We compare four popular algorithms for area coverage: Langevin Dynamics, Run and Tumble, Electrostatic Repulsion and Local Repulsion. We derive analytic approximations for the distribution of robots and performance for the first three, and suggest likely values for Local Repulsion. We run extensive simulations of each algorithm and compare the results to the lower bounds, showing how close each algorithm gets to optimal performance.
Date of Award24 Mar 2020
Original languageEnglish
Awarding Institution
  • The University of Bristol
SupervisorA J Ganesh (Supervisor) & Sabine Hauert (Supervisor)

Cite this

Decentralised Algorithms for Area Coverage
Young, S. J. (Author). 24 Mar 2020

Student thesis: Master's ThesisMaster of Science (MSc)