Open AccessImproved Runtime for the Synchronous Multi-door Filling
Author(s) -
Attila Hideg,
Tamás Lukovszki,
Bertalan Forstner
Publication year - 2022
Publication title -
periodica polytechnica. electrical engineering and computer science
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.158
H-Index - 13
eISSN - 2064-5279
pISSN - 2064-5260
DOI - 10.3311/ppee.17853
Subject(s) - a priori and a posteriori , computer science , graph , robot , upper and lower bounds , doors , degree (music) , algorithm , combinatorics , mathematics , theoretical computer science , artificial intelligence , mathematical analysis , philosophy , physics , epistemology , acoustics , operating system
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.