Voronoi-based space partitioning for coordinated multi-robot exploration
Please use this identifier to cite or link to this item:
http://hdl.handle.net/10045/12600
Title: | Voronoi-based space partitioning for coordinated multi-robot exploration |
---|---|
Authors: | Wu, Ling | García García, Miguel Ángel | Puig Valls, Domenec | Solé Ribalta, Albert |
Keywords: | Multi-robot | Exploration | Polygonal model | K-means |
Knowledge Area: | Ciencia de la Computación e Inteligencia Artificial |
Issue Date: | Sep-2007 |
Publisher: | Red de Agentes Físicos |
Citation: | WU, Ling, et al. “Voronoi-based space partitioning for coordinated multi-robot exploration”. Journal of Physical Agents. Vol. 1, No. 1 (Sept. 2007). ISSN 1888-0258, pp. 37-44 |
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 beneficial 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. |
Sponsor: | 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. |
URI: | http://hdl.handle.net/10045/12600 | http://dx.doi.org/10.14198/JoPha.2007.1.1.05 |
ISSN: | 1888-0258 |
DOI: | 10.14198/JoPha.2007.1.1.05 |
Language: | eng |
Type: | info:eu-repo/semantics/article |
Peer Review: | si |
Appears in Collections: | Journal of Physical Agents - 2007, Vol. 1, No. 1 |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
JoPha_1_1_05.pdf | 651,99 kB | Adobe PDF | Open Preview | |
This item is licensed under a Creative Commons License