Maximal persistent surveillance under safety constraints

This paper presents a method for the design of time-invariant memoryless control policies for robots tasked with persistent surveillance of an area in which there are forbidden regions. We model each robot as a controlled Markov chain whose state comprises its position on a finite two-dimensional lattice and the direction of motion. The goal is to find the minimum number of robots and an associated time-invariant memoryless control policy that guarantees that the largest number of states are persistently surveilled without ever visiting a forbidden state. We propose a design method that relies on a finitely parametrized convex program inspired by entropy maximization principles. For clarity of exposition, we focus on simple dynamics and state/control spaces, however the proposed methodology can be extended to more general cases. Numerical examples are provided.