Distributed partitioning algorithm with application to video-surveillance

How many times have we wanted to control an area and the video-surveillance system does not have the appropriate properties? Nowadays, the video-surveillance has become a responsibility by the necessity to patrol a specific area. Even if there are available HD cameras that can detect movements and heat uxes, the real problem is to have a way of controlling the behaviour of the cameras in order to provide a good and autonomous video-surveillance system. Only exploiting communication among cameras, the system should cover all the area, not allowing to an object to cross the area without being detected. Also, a very important aspect to consider is the speed of the algorithm to coordinate the cameras in order to converge to an optimal covering, where each camera has to take care of a specific area.. The coverage and partitioning of an area is one fundamental task that needs to be accomplished in order to execute more complex tasks, for example the application in video-surveillance. The appealing idea is that a group of robots have the ability to communicate among them in order to cover and control the area. Although we will be focusing on camera-surveillance the algorithm may be used in other fields, such as vacuum and security robots. The aim of this project is to develop an algorithm that allows us to partition and cover an area of interest. This algorithm has to be robust and adaptive to possible changes in the controlled area. Another important aspect to take into account is the possibility to add or remove new cameras, or considering the variation of the dimensions of the area. The challenge that we want to address is to provide an algorithm close to reality. In particular, we will focus on the communication between cameras explaining different protocols and their behaviours. In order to proceed step by step, we will firstly create a synchronous algorithm where the robots interact simultaneously and then we will add constraints in order to get to an asynchronous and asymmetric algorithm, which is the most realistic. In the synchronous system, the robots are all together communicating at every time instant so they are updating data. Conversely, in the asynchronous protocol only a pair of robots interact at a specific time, so maybe they have the necessity to communicate and they are not able to do it. There has been considerable effort in the analysis of minimizing the time to converge to an optimal solution and also we want to exploit the concept of centroidal Voronoi partitions to optimally divide the monitored area. Finally, it will be studied the 2-Dimensional case where it will be possible to simulate a real case. We will provide a video where we show how the algorithm works and how the agents are communicating to calculate the area covered by each one of them