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.
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.
Jürgen Scherer and Bernhard Rinner. Multi-Robot Patrolling with Sensing Idleness and Data Delay Objectives. Journal of Intelligent & Robotic Systems, Springer, 2020.
Jürgen Scherer and Bernhard Rinner. Multi-UAV Surveillance With Minimum Information Idleness and Latency Constraints. IEEE Robotics and Automation Letters, 2020.
