Journal of Physical Agents, Vol 1, No 1 (2007)

Voronoi-Based Space Partitioning for Coordinated Multi-Robot Exploration

Ling Wu, Miguel Angel Garcia, Domenec Puig, Albert Sole

Abstract


Recent multi-robot exploration algorithms usually
rely on occupancy grids as their core world representation.
However, those grids are not appropriate for environments that
are very large or whose boundaries are not well delimited
from the beginning of the exploration. In contrast, polygonal
representations do not have such limitations. Previously, the
authors have proposed a new exploration algorithm based on
partitioning unknown space into as many regions as available
robots by applying K-Means clustering to an occupancy grid
representation, and have shown that this approach leads to higher
robot dispersion than other approaches, which is potentially bene-
ficial for quick coverage of wide areas. In this paper, the original
K-Means clustering applied over grid cells, which is the most
expensive stage of the aforementioned exploration algorithm, is
substituted for a Voronoi-based partitioning algorithm applied to
polygons. The computational cost of the exploration algorithm is
thus significantly reduced for large maps. An empirical evaluation
and comparison of both partitioning approaches is presented.

Full Text: PDF