Exploration of finite 2D square grid by a metamorphic robotic system

Keisuke Doi; Yukiko Yamauchi; Shuji Kijima; Masafumi Yamashita

doi:10.1007/978-3-030-03232-6_7

Exploration of finite 2D square grid by a metamorphic robotic system

Keisuke Doi, Yukiko Yamauchi, Shuji Kijima, Masafumi Yamashita

Mathematical Informatics

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

7 Citations (Scopus)

Abstract

We consider exploration of a finite 2D square grid by a metamorphic robotic system consisting of anonymous oblivious modules. The number of possible shapes of the metamorphic robotic system grows as the number of modules increases. The shapes of the system serve as its memory and show its functionality. We consider the effect of global compass on the minimum number of modules for exploration of a finite 2D square grid. We show that if the modules agree on the directions (north, south, east, and west), three modules are necessary and sufficient for exploration from an arbitrary initial configuration, otherwise five modules are necessary and sufficient for limited initial configurations.

Original language	English
Title of host publication	Stabilization, Safety, and Security of Distributed Systems - 20th International Symposium, SSS 2018, Proceedings
Editors	Taisuke Izumi, Petr Kuznetsov
Publisher	Springer Verlag
Pages	96-110
Number of pages	15
ISBN (Print)	9783030032319
DOIs	https://doi.org/10.1007/978-3-030-03232-6_7
Publication status	Published - 2018
Event	20th International Symposium on Stabilization, Safety, and Security of Distributed Systems, SSS 2018 - Tokyo, Japan Duration: Nov 4 2018 → Nov 7 2018

Publication series

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

Other

Other	20th International Symposium on Stabilization, Safety, and Security of Distributed Systems, SSS 2018
Country/Territory	Japan
City	Tokyo
Period	11/4/18 → 11/7/18

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-030-03232-6_7

Cite this

Doi, K., Yamauchi, Y., Kijima, S., & Yamashita, M. (2018). Exploration of finite 2D square grid by a metamorphic robotic system. In T. Izumi, & P. Kuznetsov (Eds.), Stabilization, Safety, and Security of Distributed Systems - 20th International Symposium, SSS 2018, Proceedings (pp. 96-110). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11201 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-030-03232-6_7

Exploration of finite 2D square grid by a metamorphic robotic system. / Doi, Keisuke; Yamauchi, Yukiko; Kijima, Shuji et al.
Stabilization, Safety, and Security of Distributed Systems - 20th International Symposium, SSS 2018, Proceedings. ed. / Taisuke Izumi; Petr Kuznetsov. Springer Verlag, 2018. p. 96-110 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11201 LNCS).

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

Doi, K, Yamauchi, Y, Kijima, S & Yamashita, M 2018, Exploration of finite 2D square grid by a metamorphic robotic system. in T Izumi & P Kuznetsov (eds), Stabilization, Safety, and Security of Distributed Systems - 20th International Symposium, SSS 2018, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11201 LNCS, Springer Verlag, pp. 96-110, 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems, SSS 2018, Tokyo, Japan, 11/4/18. https://doi.org/10.1007/978-3-030-03232-6_7

Doi K, Yamauchi Y, Kijima S, Yamashita M. Exploration of finite 2D square grid by a metamorphic robotic system. In Izumi T, Kuznetsov P, editors, Stabilization, Safety, and Security of Distributed Systems - 20th International Symposium, SSS 2018, Proceedings. Springer Verlag. 2018. p. 96-110. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-03232-6_7

Doi, Keisuke ; Yamauchi, Yukiko ; Kijima, Shuji et al. / Exploration of finite 2D square grid by a metamorphic robotic system. Stabilization, Safety, and Security of Distributed Systems - 20th International Symposium, SSS 2018, Proceedings. editor / Taisuke Izumi ; Petr Kuznetsov. Springer Verlag, 2018. pp. 96-110 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{3da4d8286bd74414a3af6ee8422e9379,

title = "Exploration of finite 2D square grid by a metamorphic robotic system",

abstract = "We consider exploration of a finite 2D square grid by a metamorphic robotic system consisting of anonymous oblivious modules. The number of possible shapes of the metamorphic robotic system grows as the number of modules increases. The shapes of the system serve as its memory and show its functionality. We consider the effect of global compass on the minimum number of modules for exploration of a finite 2D square grid. We show that if the modules agree on the directions (north, south, east, and west), three modules are necessary and sufficient for exploration from an arbitrary initial configuration, otherwise five modules are necessary and sufficient for limited initial configurations.",

author = "Keisuke Doi and Yukiko Yamauchi and Shuji Kijima and Masafumi Yamashita",

note = "Funding Information: This work is partially supported by JST SICORP and JSPS KAKENHI Grant Number JP17K19982.; 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems, SSS 2018 ; Conference date: 04-11-2018 Through 07-11-2018",

year = "2018",

doi = "10.1007/978-3-030-03232-6_7",

language = "English",

isbn = "9783030032319",

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

publisher = "Springer Verlag",

pages = "96--110",

editor = "Taisuke Izumi and Petr Kuznetsov",

booktitle = "Stabilization, Safety, and Security of Distributed Systems - 20th International Symposium, SSS 2018, Proceedings",

address = "Germany",

}

TY - GEN

T1 - Exploration of finite 2D square grid by a metamorphic robotic system

AU - Doi, Keisuke

AU - Yamauchi, Yukiko

AU - Kijima, Shuji

AU - Yamashita, Masafumi

N1 - Funding Information: This work is partially supported by JST SICORP and JSPS KAKENHI Grant Number JP17K19982.

PY - 2018

Y1 - 2018

N2 - We consider exploration of a finite 2D square grid by a metamorphic robotic system consisting of anonymous oblivious modules. The number of possible shapes of the metamorphic robotic system grows as the number of modules increases. The shapes of the system serve as its memory and show its functionality. We consider the effect of global compass on the minimum number of modules for exploration of a finite 2D square grid. We show that if the modules agree on the directions (north, south, east, and west), three modules are necessary and sufficient for exploration from an arbitrary initial configuration, otherwise five modules are necessary and sufficient for limited initial configurations.

AB - We consider exploration of a finite 2D square grid by a metamorphic robotic system consisting of anonymous oblivious modules. The number of possible shapes of the metamorphic robotic system grows as the number of modules increases. The shapes of the system serve as its memory and show its functionality. We consider the effect of global compass on the minimum number of modules for exploration of a finite 2D square grid. We show that if the modules agree on the directions (north, south, east, and west), three modules are necessary and sufficient for exploration from an arbitrary initial configuration, otherwise five modules are necessary and sufficient for limited initial configurations.

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

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

U2 - 10.1007/978-3-030-03232-6_7

DO - 10.1007/978-3-030-03232-6_7

M3 - Conference contribution

AN - SCOPUS:85056453310

SN - 9783030032319

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

SP - 96

EP - 110

BT - Stabilization, Safety, and Security of Distributed Systems - 20th International Symposium, SSS 2018, Proceedings

A2 - Izumi, Taisuke

A2 - Kuznetsov, Petr

PB - Springer Verlag

T2 - 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems, SSS 2018

Y2 - 4 November 2018 through 7 November 2018

ER -

Exploration of finite 2D square grid by a metamorphic robotic system

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this