Continuous Graph Partitioning for Camera Network Surveillance*

This work focuses on the problem of designing surveillance trajectories for a network of autonomous cameras. As performance criterion we consider the worst-case detection time of static intruders. First, we represent the environment by means of a robotic roadmap. We show that optimal trajectories can be designed via a continuous graph partitioning problem. This minimization problem is convex and not differentiable. Second, we derive an auxiliary convex and differentiable minimization problem whose minimizer provides a solution to the original problem. Third and finally, we develop three distributed algorithms, for the cameras to partition the roadmap, and, consequently, synchronize along a trajectory with minimum worst-case detection time. Different communication protocols are used for the three algorithms.