Proposition of a Distributed Voronoi Partitioning Approach Enhanced with a Dispersion Phase for a Multirobot System

Abstract

This paper is an extension to our work presented in Ben Slimane and Tagina (in: Nguyen, Pimenidis, Khan and Trawiński (eds) Computational collective intelligence, Springer, Cham, 2018). It deals with the the problem of partitioning the space in an even way between a number of autonomous mobile robots. In our previous work we proposed a distributed one-phased partitioning method where each robot constructs its corresponding Voronoi cell from the information received from its neighbors. We propose in what follows a two-phased partitioning approach, starting with a dispersion task, followed by the distributed Voronoi partitioning as for the one-phased method. For the dispersion phase, we propose a novel parametrized algorithm from which we seek to control the dispersion behavior of the robots. The individual actions of the agents are controlled by the belief–desire–intention model which endows them with the required know-how needed to operate deliberately and readjust the plans dynamically on the go. We show in this paper, through a series of experiments, the results of the dispersion method and the impact of its parameters on the generated maps. We also compare the results of the two partitioning methods to show the impact of the dispersion on the partitioning in terms of the actual performed steps towards convergence and the generated maps for both methods.