EM-Patroller: Entropy Maximized Multi-Robot Patrolling With Steady State Distribution Approximation

Abstract

This letter investigates the multi-robot patrolling (MuRP) problem in a discrete environment with the objective of achieving uniform node coverage probability distribution by the robot team. Existing MuRP solutions for uniform node coverage either involve high computational complexity for the global optimal solution or rely on heuristics for approximate solutions without performance guarantees. To bridge the gap, we propose an efficient iterative algorithm, namely Entropy Maximized Patroller (EM-Patroller), with the per-iteration performance improvement guarantee and polynomial computational complexity. We reformulate the MuRP problem as an “unnormalized” joint steady state distribution entropy maximization problem and use multi-layer perceptron (MLP) to model the relationship between each robot's patrolling strategy and the individual steady state distribution. We derive a multi-agent model-based policy gradient method to update the robots' patrolling strategies towards the optimum. Complexity analysis indicates the polynomial computational complexity of EM-Patroller, and we show that EM-Patroller has additional benefits of accommodating user-defined joint steady state distributions and incorporating other objectives such as entropy maximization of individual steady state distribution. We compare EM-Patroller with state-of-the-art MuRP algorithms in various canonical MuRP environments and deploy it to a real multi-robot system for patrolling in a self-constructed indoor environment.