On Minimum Time Multi-Robot Planning with Guarantees on the Total Collected Reward

In this paper, we study a multi-robot planning problem where a team of robots visit locations in an environment to collect a specified amount of reward in the minimum possible time. Each location has a weight associated with it that represents the value or amount of reward that can be collected by visiting that location. The problem is to design tours for the robots to collect at least D units of reward while minimizing the length of the longest robot tour. The single robot unweighted version of this problem is called the k-STROLL problem. We provide a 3-approximation algorithm for the multiple robot version of the k-STROLL problem. This leads to an algorithm for the weighted problem that collects at least (1 - ∊)D reward with tour lengths of at most 3 times the optimal tour length. The analysis of the approximation algorithm is then extended to provide bi-criterion approximations to two variations of the problem. We provide an application of the approximation algorithm for planning UAV tours with gimballed cameras for monitoring an urban environment.