Voronoi-based space partitioning for coordinated multi-robot exploration
Entity
UAM. Departamento de Ingeniería InformáticaPublisher
Red de Agentes Fisicos (RedAF)Date
2007Citation
Journal of Physical Agents 1.1 (2007): 37-44ISSN
1888-0258Funded by
This work is partially supported by the Government of Spain under MCYT DPI2004-07993-C03-03. Ling Wu is supported by a FPI scholarship from the Spanish Ministry of Education and Science.Subjects
Informática; TelecomunicacionesEsta obra está bajo una licencia de Creative Commons Reconocimiento-CompartirIgual 4.0 Internacional.
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.
Files in this item
Google Scholar:Wu, Ling
-
García García, Miguel Ángel
-
Puig, Domenec
-
Sole, Albert
This item appears in the following Collection(s)
Related items
Showing items related by title, author, creator and subject.