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.
翻译:我们研究的是以美元移动机器人优化覆盖树的算法问题。 树是所有机器人都知道的, 我们的目标是为每个机器人分配散步, 以便让这些步行的结合覆盖整个树。 我们假设边缘长度相同, 沿边缘旅行需要一单位时间。 我们考虑的是两个客观的函数: 覆盖时间和覆盖长度。 覆盖时间是机器人完成指定行走的最大时间, 覆盖时间是所有行走长度的总和。 我们还考虑一个变量, 机器人必须在大多数特定行走的同一个顶点定期集合。 我们显示, 两种成本功能的问题不同。 关于覆盖时间的问题, 我们证明当$K是投入的一部分时, 问题很困难, 不论是否需要定期会合。 关于覆盖时间的最小化问题, 我们表明, 在不需要定期会合的时候, 它可以在聚诺米时间中解决, 并且它是硬的 。