On optimal coverage of a tree with multiple robots
Por:
Aldana-Galvan, I, Catana-Salazar, J. C., Diaz-Banez, J. M., Duque, F., Fabila-Monroy, R., Heredia, M. A., Ramirez-Vigueras, A., Urrutia, J.
Publicada:
16 sep 2020
Resumen:
We study the algorithmic problem of optimally covering a tree with k
mobile robots. The tree is known to all robots, and our goal is to
assign a walk to each robot in such a way that the union of these walks
covers the whole tree. We assume that the edges have the same length,
and that traveling along an edge takes a unit of time. 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 and
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
problem is different for the two cost functions. For the cover time
minimization problem, we prove that the problem is NP-hard when k is
part of the input, regardless of whether periodic rendezvous are
required or not. For the cover length minimization problem, we show that
it can be solved in polynomial time when periodic rendezvous are not
required, and it is NP-hard otherwise. (C) 2020 Elsevier B.V. All rights
reserved.
Filiaciones:
Aldana-Galvan, I:
Univ Nacl Autonoma Mexico, Inst Matemat, Mexico City, DF, Mexico
Catana-Salazar, J. C.:
Univ Nacl Autonoma Mexico, Inst Matemat, Mexico City, DF, Mexico
Diaz-Banez, J. M.:
Univ Seville, Dept Matemat Aplicada 2, Seville, Spain
Duque, F.:
Univ Antioquia, Inst Matemat, Medellin, Colombia
Fabila-Monroy, R.:
CINVESTAV, Dept Matemat, Mexico City, DF, Mexico
Heredia, M. A.:
UAM Azcapotzalco, Dept Sistemas, Mexico City, DF, Mexico
Ramirez-Vigueras, A.:
Univ Nacl Autonoma Mexico, Inst Matemat, Mexico City, DF, Mexico
Urrutia, J.:
Univ Nacl Autonoma Mexico, Inst Matemat, Mexico City, DF, Mexico
|