Guo, H., Kang, Q., Yau, W.-Y., Ang, M. H., & Rus, D. (2023). EM-Patroller: Entropy Maximized Multi-Robot Patrolling With Steady State Distribution Approximation. IEEE Robotics and Automation Letters, 8(9), 5712–5719. https://doi.org/10.1109/lra.2023.3300245
Abstract:
This paper 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.
License type:
Publisher Copyright
Funding Info:
This research / project is supported by the A*STAR - HORIZONTAL TECHNOLOGY COORDINATING OFFICE SEED FUND
Grant Reference no. : C221518004