4.6 Article

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

Journal

IEEE ROBOTICS AND AUTOMATION LETTERS
Volume 8, Issue 9, Pages 5712-5719

Publisher

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/LRA.2023.3300245

Keywords

Un-normalized joint steady state distribution; multi-robot patrolling; multi-agent model-based policy gradient

Categories

Ask authors/readers for more resources

This letter proposes an efficient iterative algorithm, named Entropy Maximized Patroller (EM-Patroller), to solve the multi-robot patrolling (MuRP) problem in a discrete environment. EM-Patroller achieves uniform node coverage probability distribution by reformulating the MuRP problem as an unnormalized joint steady state distribution entropy maximization problem. It uses the multi-layer perceptron (MLP) to model the relationship between each robot's patrolling strategy and the individual steady state distribution.
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.

Authors

I am an author on this paper
Click your name to claim this paper and add it to your profile.

Reviews

Primary Rating

4.6
Not enough ratings

Secondary Ratings

Novelty
-
Significance
-
Scientific rigor
-
Rate this paper

Recommended

No Data Available
No Data Available