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 dierentiable. Second, we derive an auxiliary convex and dierentiable minimization problem whose minimizer provides a solution to the original problem. Third and nally, we develop three distributed algorithms, for the cameras to partition the roadmap, and, consequently, synchronize along a trajectory with minimum worst-case detection time. Dierent communication protocols are used for the three algorithms.