Persistent monitoring can be solved by multiple robots sharing the task of monitoring. In our scenario, it means dividing the whole area into multiple parts, and each robot monitoring the area assigned to it. Here, we use Multi-Agent Coverage Algorithms by Patel et al. [1] with a few adaptations for persistent monitoring. Patel et al. study Multi-Agent Lawnmower Algorithm and Multi-Agent Voronoi Cover Algorithm for multi-agent coverage and among six solutions for coverage problem. We combine the two algorithms for persistent monitoring, which can be thought of as a dynamic coverage problem.
We assume that all the robots (UGVs) have infinite resources for functioning i.e. they can keep running without needing any recharge. This relaxes the problem to convert it into a trajectory finding problem. This assumption is valid when the area to be monitored is small or the robots have efficient power sources to keep them running for a long time. Additionally, we have only static obstacles in our environments.
With these assumptions, our problem effectively is to find out a good way to divide the area to be monitored among the robots and to plan the paths for monitoring for each robot.
Multi-Agent Persistent Monitoring Algorithm
We solve the multi-agent persistent monitoring problem by dividing it into two sub-problems as follows:
Voronoi Partitioning Problem: In this problem, we split the whole environment into Voronoi Partitions of approximately equal area. Each such non-overlapping region is assigned to each UGV for monitoring. We implement a modified version of Algorithm 7 presented in [1] to solve the Voronoi partitioning problem.
Lawnmower Coverage Problem: Also known as Boustrophedon cellular decomposition (Choset et al. [4]), the objective of this problem is to determine a path for each UGV inside its assigned region which enables the UGV to persistently monitor the region. We implement a modified version of Algorithm 1 presented in [1] to solve the Lawnmower coverage problem.
The following video shows a demonstration of the Voronoi partitioning and the lawnmower coverage. Here, the six magenta polygons show the Voronoi regions assigned to the six UGVs. Each UGV follows a lawnmower like zigzag path to monitor its assigned region. In the next two sections, we discuss these two algorithms in detail.