A Projected Lloyd’s Algorithm for Coverage Control Problems

This work presents a new approach for solving the coverage problem for large areas given a limited number of sensors. We consider the problem where there is a given area needed to be covered, however there are not enough sensors to provide complete coverage of the designated area at once. Furthermore, we require that at each stage of coverage, a sub-region in the area is constantly monitored. Lastly, we desire a coordinated formation, where the distance between the agents is controlled.
The solution approach is a combination of two algorithms. First, the area is being partitioned into sub-regions using a modified version of the well known Lloyd’s Algorithm that we term the Projected Lloyd’s Algorithm. Then, for each sub region, we utilize Lloyd’s Algorithm. For the coordinate formation, we combined Lloyd’s Algorithm with formation controller.
The new algorithm, projected Lloyd’s algorithm, is used for constraining the area partitioning to include the required sub-region in each partition, and it’s being achieved by projecting the algorithm results onto the constrained polygon. Another concept that was tested is combining the Lloyd’s algorithm strategy with distance-based formation control, which resulted with stable controller. The strategies were tested using numerical simulations.