Dynamic Partitioning Strategies for Multi-Robot Patrolling Systems

In this paper, the mission for mobile patrolling robots is to detect as many incoming visitors as possible by monitoring the environment. For multi-robot mobile patrolling systems, task assignment in the common environment is one of the problems. For this problem, we use a territorial approach and partition the environment into territories. Thus, each robot is allowed to patrol a separate territory regardless of the others. In this regard, however, the workload balancing of the patrolling tasks in the territories is a challenge. For this challenge, we propose dynamic partitioning strategies focusing on visitor trends. The system transfers a part of the territory with the maximum workload to others so as to equalize the workloads. As a result, while the sizes of the territories without visitor trends increase, others with the trends decrease. Therefore, the territorial approach enables robots to intensively monitor areas in accordance with the number of the visitors. This is the main contribution of this paper. Simulation experiments show that the patrolling robots successfully detect visitors through workload balancing.