Multi-Robot Routing for Persistent Monitoring with Latency Constraints
This addresses efficient resource allocation for monitoring tasks in robotics, but it is incremental as it builds on known PSPACE-complete problems with new algorithms.
The paper tackles the problem of multi-robot path planning for persistent monitoring with latency constraints, presenting an O(log ρ) approximation algorithm and a heuristic that often outperforms it in simulations, evaluated on patrolling and scene reconstruction applications.
In this paper we study a multi-robot path planning problem for persistent monitoring of an environment. We represent the areas to be monitored as the vertices of a weighted graph. For each vertex, there is a constraint on the maximum time spent by the robots between visits to that vertex, called the latency, and the objective is to find the minimum number of robots that can satisfy these latency constraints. The decision version of this problem is known to be PSPACE-complete. We present a $O(\log ρ)$ approximation algorithm for the problem where $ρ$ is the ratio of the maximum and the minimum latency constraints. We also present an orienteering based heuristic to solve the problem and show through simulations that in most of the cases the heuristic algorithm gives better solutions than the approximation algorithm. We evaluate our algorithms on large problem instances in a patrolling scenario and in a persistent scene reconstruction application. We also compare the algorithms with an existing solver on benchmark instances.