Improved Runtime for the Synchronous Multi-door Filling

Authors

  • Attila Hideg
    Affiliation
    Department of Automation and Applied Informatics, Faculty of Electrical Engineering and Informatics, Budapest University of Technology and Economics, H-1117 Budapest, Magyar tudósok krt. 2., Hungary
  • Tamás Lukovszki
    Affiliation
    Faculty of Informatics, H-1117 Budapest, Eötvös Loránd University, Pázmány Péter sétány 1/C., Hungary
  • Bertalan Forstner
    Affiliation
    Department of Automation and Applied Informatics, Faculty of Electrical Engineering and Informatics, Budapest University of Technology and Economics, H-1117 Budapest, Magyar tudósok krt. 2., Hungary
https://doi.org/10.3311/PPee.17853

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.

Keywords:

filling, uniform dispersal, multi-robot system

Citation data from Crossref and Scopus

Published Online

2022-01-17

How to Cite

Hideg, A., Lukovszki, T., Forstner, B. “Improved Runtime for the Synchronous Multi-door Filling”, Periodica Polytechnica Electrical Engineering and Computer Science, 66(1), pp. 12–19, 2022. https://doi.org/10.3311/PPee.17853

Issue

Section

Articles