Connected Reconfiguration of Lattice-Based Cellular Structures by Finite-Memory Robots

被引：4

作者：

Fekete, Sandor P. ^{[1
]}

Niehs, Eike ^{[2
]}

Scheffer, Christian ^{[3
]}

Schmidt, Arne ^{[1
]}

机构：

[1] TU Braunschweig, Dept Comp Sci, Braunschweig, Germany

[2] TU Braunschweig, Inst High Voltage Technol & Power Syst, Braunschweig, Germany

[3] Bochum Univ Appl Sci, Fac Elect Engn & Comp Sci, Bochum, Germany

来源：

ALGORITHMICA | 2022年 / 84卷 / 10期

关键词：

Finite automata; Reconfiguration; Polyominoes; Robots; Connectivity; TREE EXPLORATION; MOBILE ROBOTS; SHAPES; GRAPHS;

D O I：

10.1007/s00453-022-00995-z

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We provide algorithmic methods for connected reconfiguration of lattice-based cellular structures by finite-state robots, motivated by large-scale constructions in space. We present algorithms that are able to detect and reconfigure arbitrary polyominoes, while also preserving connectivity of a structure during reconfiguration; we also provide mathematical proofs and performance guarantees. Specific results include methods for determining a bounding box, scaling a given arrangement, and adapting more general algorithms for transforming polyominoes.

引用

页码：2954 / 2986

页数：33

共 71 条

[21] Asynchronous deterministic rendezvous in graphs [J].

De Marco, G ;

Gargano, L ;

Kranakis, E ;

Krizanc, D ;

Pelc, A ;

Vaccaro, U .

THEORETICAL COMPUTER SCIENCE, 2006, 355 (03) :315-326

[22] Staged self-assembly: nanomanufacture of arbitrary shapes with O(1) glues [J].

Erik D. Demaine ;

Martin L. Demaine ;

Sándor P. Fekete ;

Mashhood Ishaque ;

Eynat Rafalin ;

Robert T. Schweller ;

Diane L. Souvaine .

Natural Computing, 2008, 7 (3) :347-370

[23]

Derakhshandeh Zahra, 2016, DNA Computing and Molecular Programming. 22nd International Conference, DNA 22. Proceedings: LNCS 9818, P148, DOI 10.1007/978-3-319-43994-5_10

[24]

Derakhshandeh Zahra, 2015, DNA Computing and Molecular Programming. 21st International Conference, DNA 21. Proceedings 9211, P117, DOI 10.1007/978-3-319-21999-8_8

[25] Universal coating for programmable matter [J].

Derakhshandeh, Zahra ;

Gmyr, Robert ;

Richa, Andrea W. ;

Scheideler, Christian ;

Strothmann, Thim .

THEORETICAL COMPUTER SCIENCE, 2017, 671 :56-68

[26] Brief Announcement: Amoebot-A New Model for Programmable Matter [J].

Derakhshandeh, Zahra ;

Dolev, Shlomi ;

Gmyr, Robert ;

Richa, Andrea W. ;

Scheideler, Christian ;

Strothmann, Thim .

PROCEEDINGS OF THE 26TH ACM SYMPOSIUM ON PARALLELISM IN ALGORITHMS AND ARCHITECTURES (SPAA'14), 2014, :220-222

[27]

Derakhshandeh Zahra., 2015, Proceedings of the Second Annual International Conference on Nanoscale Computing and Communication, page, P21

[28] Deterministic rendezvous in graphs [J].

Dessmark, Anders ;

Fraigniaud, Pierre ;

Kowalski, Dariusz R. ;

Pelc, Andrzej .

ALGORITHMICA, 2006, 46 (01) :69-96

[29] Optimal torus exploration by oblivious robots [J].

Devismes, Stephane ;

Lamani, Anissa ;

Petit, Franck ;

Tixeuil, Sebastien .

COMPUTING, 2019, 101 (09) :1241-1264

[30] Shape formation by programmable particles [J].

Di Luna, Giuseppe A. ;

Flocchini, Paola ;

Santoro, Nicola ;

Viglietta, Giovanni ;

Yamauchi, Yukiko .

DISTRIBUTED COMPUTING, 2020, 33 (01) :69-101

← 1 2 3 4 5 6 7 8 →