Optimal Coverage of a Tree with Multiple Robots

EasyChair Preprint 3044

Abstract

We study the algorithmic problem of optimally covering a tree with $k$ mobile robots. The tree is known to all robots, a robot moves between neighboring vertices with unit cost and the goal is to design a covering strategy to minimize a certain objective function. Two objective functions are considered: the cover time and the cover length. The cover time is the maximum time a robot needs to finish its assigned walk; the cover length is the sum of the lengths of all the walks. We also consider a variant in which the robots must rendezvous periodically at the same vertex in at most a certain number of moves. We show that the problems are essentially different for both cost functions. For the cover time minimization problem, when $k$ is part of the input, we prove that the problem is NP-hard regardless if periodic rendezvous is required. For the cover length minimization problem, we show that it can be solved in polynomial time in the case when periodic rendezvous is not required and it is NP-hard, otherwise.

Keyphrases: Graph exploration., Multi robot exploration., Multi-robot exploration, Optimal tree coverage, Optimal tree coverage., graph exploration

@booklet{EasyChair:3044,
  author    = {Israel Aldana-Galvan and Juan Carlos Catana-Salazar and José-Miguel Díaz-Báñez and Frank Duque and Ruy Fabila-Monroy and Marco A. Heredia and Adriana Ramírez-Vigueras and Jorge Urrutia},
  title     = {Optimal Coverage of a Tree with Multiple Robots},
  howpublished = {EasyChair Preprint 3044},
  year      = {EasyChair, 2020}}