UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

On multi-robot area and boundary coverage Fazli, Pooyan


Distributed coverage aims to deploy a team of robots to move around a target area to perform sensing, monitoring, data collection, search, or distributed servicing tasks. This thesis investigates three variations of the coverage problem. First, we address the multi-robot single coverage of a target area. The aim is to guarantee that every accessible point in the area is visited in a finite time. The proposed algorithm supports heterogeneous robots having various maximal speeds, and is robust to robot failure. It also balances the workload distribution among the robots based on their maximal speeds. The obtained results on the coverage time are scalable to workspaces of different sizes, and robots of varied visual ranges. Second, we tackle the multi-robot repeated coverage of a target area. The objective is to visit all the accessible points of the area repeatedly over time, while optimizing some performance criteria. We introduce four repeated coverage algorithms, and evaluate them under a comprehensive set of metrics including the sum of the paths/tours generated for the robots, the frequency of visiting the points in the target area, and the degree of balance in workload distribution among the robots. We also investigate the effects of environment representation, and the robots' visual range on the performance of the proposed algorithms. The results can be used as a framework for choosing an appropriate combination of repeated coverage algorithm, environment representation, and the robots’ visual range based on the particular workspace and the metric to be optimized. Third, we focus on the multi-robot repeated coverage of the boundaries of a target area and the structures inside it. Events may occur at any position on the boundaries, and the robots are not a priori aware of the event distribution. The goal is to maximize the total detection reward of the events. The reward a robot receives for detecting an event depends on how early the event is detected. To this end, we introduce an online, distributed algorithm and investigate the effects of robots' visual range, communication among the robots, and the event frequency on the performance of the algorithm.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International