Download PDFOpen PDF in browserOptimal Coverage of a Tree with Multiple RobotsEasyChair Preprint 30444 pages•Date: March 25, 2020AbstractWe 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
|