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 条
  • [1] Abdellah AM., 2020, S COMPUTATIONAL GEOM, P73
  • [2] THE RENDEZVOUS SEARCH PROBLEM
    ALPERN, S
    [J]. SIAM JOURNAL ON CONTROL AND OPTIMIZATION, 1995, 33 (03) : 673 - 683
  • [3] Tree Exploration with Logarithmic Memory
    Ambuehl, Christoph
    Gasieniec, Leszek
    Pelc, Andrzej
    Radzik, Tomasz
    Zhang, Xiaohui
    [J]. ACM TRANSACTIONS ON ALGORITHMS, 2011, 7 (02)
  • [4] THE RENDEZVOUS PROBLEM ON DISCRETE LOCATIONS
    ANDERSON, EJ
    WEBER, RR
    [J]. JOURNAL OF APPLIED PROBABILITY, 1990, 27 (04) : 839 - 851
  • [5] [Anonymous], 2016, P 28 ACM S PAR ALG A, P289, DOI [DOI 10.1145/2935764.2935784, 10.1145/2935764.2935784]
  • [6] Balanza-Martinez Jose, 2019, 30 ANN ACM SIAM S DI, DOI DOI 10.1137/1.9781611975482.167
  • [7] Tilt Assembly: Algorithms for Micro-factories That Build Objects with Uniform External Forces
    Becker, Aaron T.
    Fekete, Sandor P.
    Keldenich, Phillip
    Krupke, Dominik
    Rieck, Christian
    Scheffer, Christian
    Schmidt, Arne
    [J]. ALGORITHMICA, 2020, 82 (02) : 165 - 187
  • [8] BENDER MA, 1994, AN S FDN CO, P75
  • [9] Blum M., 1978, 19th Annual Symposium on Foundations of Computer Science, P132, DOI 10.1109/SFCS.1978.30
  • [10] Multirobot Tree and Graph Exploration
    Brass, Peter
    Cabrera-Mora, Flavio
    Gasparri, Andrea
    Xiao, Jizhong
    [J]. IEEE TRANSACTIONS ON ROBOTICS, 2011, 27 (04) : 707 - 717
12345678