Approximation algorithms for the set cover formation by oblivious mobile robots

Tomoko Izumi; Sayaka Kamei; Yukiko Yamauchi

doi:10.1007/978-3-319-14472-6_16

Approximation algorithms for the set cover formation by oblivious mobile robots

Tomoko Izumi, Sayaka Kamei, Yukiko Yamauchi

Mathematical Informatics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

1 Citation (Scopus)

Abstract

Given n robots and n target points on the plane, the minimum set cover formation (SCF) problem requires the robots to form a set cover by the minimum number of robots. In previous formation problems by mobile robots, such as gathering and pattern formation, the problems consist only of the mobile robots, and there are no points fixed in the environment. In addition, the problems do not require a control of the number of robots constructing the formation. In this paper, we first introduce the formation problem in which robots move so that they achieve a desired deployment with the minimum number of robots for a given set of positions of fixed points.

Since the minimum set cover problem with disks in the centralized settings is NP-hard, our goal is to propose approximation algorithms for the minimum SCF problem. First, we show a minimal SCF algorithm from any initial configuration in the asynchronous system. Moreover, we propose an 8-approximation SCF algorithm in the semi-synchronous system for an initial configuration with a low symmetricity. This approximation algorithm achieves 2(1 + 1/l)2 approximation ratio for an initial configuration with the lowest symmetricity (l ≥ 1).

Original language	English
Title of host publication	Principles of Distributed Systems - 18th International Conference, OPODIS 2014, Proceedings
Editors	Marcos K. Aguilera, Leonardo Querzoni, Marc Shapiro
Publisher	Springer Verlag
Pages	233-247
Number of pages	15
ISBN (Electronic)	9783319144719
DOIs	https://doi.org/10.1007/978-3-319-14472-6_16
Publication status	Published - 2014
Event	18th International Conference on Principles of Distributed Systems, OPODIS 2014 - Cortina d’Ampezzo, Italy Duration: Dec 16 2014 → Dec 19 2014

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	8878
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	18th International Conference on Principles of Distributed Systems, OPODIS 2014
Country/Territory	Italy
City	Cortina d’Ampezzo
Period	12/16/14 → 12/19/14

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-319-14472-6_16

Cite this

Izumi, T., Kamei, S., & Yamauchi, Y. (2014). Approximation algorithms for the set cover formation by oblivious mobile robots. In M. K. Aguilera, L. Querzoni, & M. Shapiro (Eds.), Principles of Distributed Systems - 18th International Conference, OPODIS 2014, Proceedings (pp. 233-247). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8878). Springer Verlag. https://doi.org/10.1007/978-3-319-14472-6_16

Approximation algorithms for the set cover formation by oblivious mobile robots. / Izumi, Tomoko; Kamei, Sayaka; Yamauchi, Yukiko.
Principles of Distributed Systems - 18th International Conference, OPODIS 2014, Proceedings. ed. / Marcos K. Aguilera; Leonardo Querzoni; Marc Shapiro. Springer Verlag, 2014. p. 233-247 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8878).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Izumi, T, Kamei, S & Yamauchi, Y 2014, Approximation algorithms for the set cover formation by oblivious mobile robots. in MK Aguilera, L Querzoni & M Shapiro (eds), Principles of Distributed Systems - 18th International Conference, OPODIS 2014, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8878, Springer Verlag, pp. 233-247, 18th International Conference on Principles of Distributed Systems, OPODIS 2014, Cortina d’Ampezzo, Italy, 12/16/14. https://doi.org/10.1007/978-3-319-14472-6_16

Izumi T, Kamei S, Yamauchi Y. Approximation algorithms for the set cover formation by oblivious mobile robots. In Aguilera MK, Querzoni L, Shapiro M, editors, Principles of Distributed Systems - 18th International Conference, OPODIS 2014, Proceedings. Springer Verlag. 2014. p. 233-247. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-14472-6_16

Izumi, Tomoko ; Kamei, Sayaka ; Yamauchi, Yukiko. / Approximation algorithms for the set cover formation by oblivious mobile robots. Principles of Distributed Systems - 18th International Conference, OPODIS 2014, Proceedings. editor / Marcos K. Aguilera ; Leonardo Querzoni ; Marc Shapiro. Springer Verlag, 2014. pp. 233-247 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{586c7882699e43dc95998355c65a15fe,

title = "Approximation algorithms for the set cover formation by oblivious mobile robots",

abstract = "Given n robots and n target points on the plane, the minimum set cover formation (SCF) problem requires the robots to form a set cover by the minimum number of robots. In previous formation problems by mobile robots, such as gathering and pattern formation, the problems consist only of the mobile robots, and there are no points fixed in the environment. In addition, the problems do not require a control of the number of robots constructing the formation. In this paper, we first introduce the formation problem in which robots move so that they achieve a desired deployment with the minimum number of robots for a given set of positions of fixed points.Since the minimum set cover problem with disks in the centralized settings is NP-hard, our goal is to propose approximation algorithms for the minimum SCF problem. First, we show a minimal SCF algorithm from any initial configuration in the asynchronous system. Moreover, we propose an 8-approximation SCF algorithm in the semi-synchronous system for an initial configuration with a low symmetricity. This approximation algorithm achieves 2(1 + 1/l)2 approximation ratio for an initial configuration with the lowest symmetricity (l ≥ 1).",

author = "Tomoko Izumi and Sayaka Kamei and Yukiko Yamauchi",

note = "Funding Information: This work was supported in part by KAKENHI No. 26330015 and a Grant-in-Aid for Scientific Research on Innovative Areas gMolecular Roboticsh (No. 24104519) of The Ministry of Education, Culture, Sports, Science, and Technology, Japan. Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2014.; 18th International Conference on Principles of Distributed Systems, OPODIS 2014 ; Conference date: 16-12-2014 Through 19-12-2014",

year = "2014",

doi = "10.1007/978-3-319-14472-6_16",

language = "English",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "233--247",

editor = "Aguilera, {Marcos K.} and Leonardo Querzoni and Marc Shapiro",

booktitle = "Principles of Distributed Systems - 18th International Conference, OPODIS 2014, Proceedings",

address = "Germany",

}

TY - GEN

T1 - Approximation algorithms for the set cover formation by oblivious mobile robots

AU - Izumi, Tomoko

AU - Kamei, Sayaka

AU - Yamauchi, Yukiko

N1 - Funding Information: This work was supported in part by KAKENHI No. 26330015 and a Grant-in-Aid for Scientific Research on Innovative Areas gMolecular Roboticsh (No. 24104519) of The Ministry of Education, Culture, Sports, Science, and Technology, Japan. Publisher Copyright: © Springer International Publishing Switzerland 2014.

PY - 2014

Y1 - 2014

N2 - Given n robots and n target points on the plane, the minimum set cover formation (SCF) problem requires the robots to form a set cover by the minimum number of robots. In previous formation problems by mobile robots, such as gathering and pattern formation, the problems consist only of the mobile robots, and there are no points fixed in the environment. In addition, the problems do not require a control of the number of robots constructing the formation. In this paper, we first introduce the formation problem in which robots move so that they achieve a desired deployment with the minimum number of robots for a given set of positions of fixed points.Since the minimum set cover problem with disks in the centralized settings is NP-hard, our goal is to propose approximation algorithms for the minimum SCF problem. First, we show a minimal SCF algorithm from any initial configuration in the asynchronous system. Moreover, we propose an 8-approximation SCF algorithm in the semi-synchronous system for an initial configuration with a low symmetricity. This approximation algorithm achieves 2(1 + 1/l)2 approximation ratio for an initial configuration with the lowest symmetricity (l ≥ 1).

AB - Given n robots and n target points on the plane, the minimum set cover formation (SCF) problem requires the robots to form a set cover by the minimum number of robots. In previous formation problems by mobile robots, such as gathering and pattern formation, the problems consist only of the mobile robots, and there are no points fixed in the environment. In addition, the problems do not require a control of the number of robots constructing the formation. In this paper, we first introduce the formation problem in which robots move so that they achieve a desired deployment with the minimum number of robots for a given set of positions of fixed points.Since the minimum set cover problem with disks in the centralized settings is NP-hard, our goal is to propose approximation algorithms for the minimum SCF problem. First, we show a minimal SCF algorithm from any initial configuration in the asynchronous system. Moreover, we propose an 8-approximation SCF algorithm in the semi-synchronous system for an initial configuration with a low symmetricity. This approximation algorithm achieves 2(1 + 1/l)2 approximation ratio for an initial configuration with the lowest symmetricity (l ≥ 1).

UR - http://www.scopus.com/inward/record.url?scp=84917743766&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84917743766&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-14472-6_16

DO - 10.1007/978-3-319-14472-6_16

M3 - Conference contribution

AN - SCOPUS:84917743766

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 233

EP - 247

BT - Principles of Distributed Systems - 18th International Conference, OPODIS 2014, Proceedings

A2 - Aguilera, Marcos K.

A2 - Querzoni, Leonardo

A2 - Shapiro, Marc

PB - Springer Verlag

T2 - 18th International Conference on Principles of Distributed Systems, OPODIS 2014

Y2 - 16 December 2014 through 19 December 2014

ER -

Approximation algorithms for the set cover formation by oblivious mobile robots

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this