论文标题
在具有多个机器人的树的最佳覆盖范围
On Optimal Coverage of a Tree with Multiple Robots
论文作者
论文摘要
我们研究了用$ k $移动机器人最佳覆盖树的算法问题。所有机器人都知道这棵树，我们的目标是向每个机器人分配步行，以使这些步行的结合覆盖整棵树。我们假设边缘的长度相同，并且沿着边缘行驶需要一个时间单位。考虑了两个目标功能：覆盖时间和覆盖长度。封面时间是机器人需要完成其分配步行的最长时间，封面长度是所有步行的长度的总和。我们还考虑了一种变体，其中机器人必须在最多一定数量的移动中定期在同一顶点上定期对集合。我们表明，这两个成本功能的问题是不同的。对于覆盖时间最小化问题，我们证明当$ k $是输入的一部分时，无论是否需要定期会合时，问题是NP-HARD。对于覆盖长度最小化问题，我们表明它可以在不需要周期性会合时在多项式时间内解决，否则它是NP-HARD。
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.
