Coordinated multi-robot exploration through unsupervised clustering of unknown space

Abstract

This paper proposes a new coordination algorithm for efficiently exploring an unknown environment with a team of mobile robots. The proposed technique subsequently applies a well-known unsupervised clustering algorithm (k-means) in order to fairly divide the remaining unknown space into as many disjoint regions as available robots. Each robot is primarily responsible for exploring its assigned region and can help other robots on its way through. Unknown space is dynamically repartitioned as new areas are discovered by the team, balancing thus the overall workload among team members and naturally leading to greater dispersion over the environment and thus faster broad coverage than with previous greedy-like approaches, which guide robots based on maximum profit strategies that simply trade off between distance to the closest frontiers and amount of unknown cells likely to be discovered from them.