Improved Runtime for the Synchronous Multi-door Filling

Abstract

In this paper, a particular type of dispersion is further investigated, which is called Filling. In this problem, robots are injected one by one into an a priori not known area and have to travel across until the whole area is covered. The coverage is achieved by a robotic team whose hardware capabilities are restricted in order to maintain low production costs. This includes limited viewing and communication ranges. In this work, we present an algorithm solving the synchronous Filling problem in O((k + ∆)·n) time steps by n robots with a viewing range of 1 hop, where k is the number of doors, n is the number of vertices of the graph, and ∆ is the maximum degree of the graph. This improves the best previously known running time bound of O(k · ∆ · n). Furthermore, we remove the constraint from the previous algorithm that the door vertices need to have a degree of 1.