Persistent surveillance with multiple robots

Persistent Surveillance Problem
In persistent surveillance, multiple sensing robots must continuously visit all sensing locations of the environment. Release and relay robots assist in transferring the captured data to the base station.

Persistent surveillance is the task of continuously monitoring an environment over a long period of time. Many multi-robot applications, including disaster response, security tasks as well as exploration and mapping, can be represented as a persistent surveillance problem. Understanding the problem’s properties and developing efficient algorithms for solving the problem are therefore highly relevant for multi-robot systems research.

Jürgen Scherer, who is currently finalizing his PhD entitled “Multi-Robot Persistent Surveillance with Connectivity Constraints”, exemplifies the basic persistent surveillance problem, “Robots have to visit all given sensing locations periodically while maintaining a multi-hop connection to a base station with the objective to minimize the duration between two consecutive visits of a sensing location.” Due to the connectivity constraint, the robots mutually restrict their possible movements and traditional patrolling strategies cannot be applied directly to the problem because they do not coordinate the robots’ movement in space and time to maintain connectivity. In his studies, Jürgen Scherer was able to prove that the basic problem and several related problem instances are NP-hard and, hence, that there are no simple (polynomial) algorithm possible for finding the optimal solution.

“In a further investigation, we relaxed the connectivity constraint and allowed delay-tolerant data transfers to the base station”, explains his supervisor Bernhard Rinner. “Thus, continuous connection from all robots to the base station is not required, and the robots can collaboratively transfer the data in a store-and-foward fashion.” For this relaxed problem, two objectives must be considered concurrently: the duration between consecutive visits and the delay between data capturing (at the sensing location) and data delivery (at the base station). Similar to the basic problem, we could show that persistent surveillance with relaxed communication constraints is also a NP hard problem.

Individual surveillance tours of 5 robots (left) and their scheduling (right). The data is transferred via meeting points (circles) to the base station (square) with minimal latency.

Jürgen Scherer developed various heuristics for the solving the basic and relaxed persistent surveillance problems and compared their performance in simulation studies. Furthermore, he proposed an algorithm for the online execution of the individual schedules on the robots which will converge to the optimal schedule. “Overall, this work provides important theoretical results which are highly relevant for various multi-robot applications”, Bernhard Rinner concludes.

Selected publications

Jürgen Scherer and Bernhard Rinner. Multi-robot persistent surveillance with connectivity constraints. IEEE Access, 2020.
(preprint available at arXiv:1909.07703).

Jürgen Scherer and Bernhard Rinner. Multi-Robot Patrolling with Sensing Idleness and Data Delay Objectives. Journal of Intelligent & Robotic Systems, Springer, 2020.
(preprint available at arXiv:1906.11539).

Jürgen Scherer and Bernhard Rinner. Short and Full Horizon Motion Planning for Persistent multi-UAV Surveillance with Energy and Communication Constraints. In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2017), Vancouver, Canada. September 2017