Search Results

Documents authored by Skretas, George

Document
DOI: 10.4230/LIPIcs.SAND.2024.9
All for One and One for All: An O(1)-Musketeers Universal Transformation for Rotating Robots

Authors: Matthew Connor, Othon Michail, and George Skretas

Published in: LIPIcs, Volume 292, 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)

Abstract
In this paper, we settle the main open question of [Michail, Skretas, Spirakis, ICALP'17], asking what is the family of two-dimensional geometric shapes that can be transformed into each other by a sequence of rotation operations, none of which disconnects the shape. The model represents programmable matter systems consisting of interconnected modules that perform the minimal mechanical operation of 90° rotations around each other. The goal is to transform an initial shape of modules A into a target shape B. Under the necessary assumptions that the given shapes are connected and have identical colourings on a checkered colouring of the grid, and using a seed of only constant size, we prove that any pair of such shapes can be transformed into each other within an optimal O(n²) rotation operations none of which disconnects the shape.
Cite as

Matthew Connor, Othon Michail, and George Skretas. All for One and One for All: An O(1)-Musketeers Universal Transformation for Rotating Robots. In 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 292, pp. 9:1-9:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{connor_et_al:LIPIcs.SAND.2024.9,
  author =	{Connor, Matthew and Michail, Othon and Skretas, George},
  title =	{{All for One and One for All: An O(1)-Musketeers Universal Transformation for Rotating Robots}},
  booktitle =	{3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)},
  pages =	{9:1--9:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-315-7},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{292},
  editor =	{Casteigts, Arnaud and Kuhn, Fabian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2024.9},
  URN =		{urn:nbn:de:0030-drops-198874},
  doi =		{10.4230/LIPIcs.SAND.2024.9},
  annote =	{Keywords: programmable matter, universal transformation, reconfigurable robotics, shape formation, centralised algorithms}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2017.136
On the Transformation Capability of Feasible Mechanisms for Programmable Matter

Authors: Othon Michail, George Skretas, and Paul G. Spirakis

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract
In this work, we study theoretical models of programmable matter systems. The systems under consideration consist of spherical modules, kept together by magnetic forces and able to perform two minimal mechanical operations (or movements): rotate around a neighbor and slide over a line. In terms of modeling, there are n nodes arranged in a 2-dimensional grid and forming some initial shape. The goal is for the initial shape A to transform to some target shape B by a sequence of movements. Most of the paper focuses on transformability questions, meaning whether it is in principle feasible to transform a given shape to another. We first consider the case in which only rotation is available to the nodes. Our main result is that deciding whether two given shapes A and B can be transformed to each other is in P. We then insist on rotation only and impose the restriction that the nodes must maintain global connectivity throughout the transformation. We prove that the corresponding transformability question is in PSPACE and study the problem of determining the minimum seeds that can make feasible otherwise infeasible transformations. Next we allow both rotations and slidings and prove universality: any two connected shapes A,B of the same number of nodes, can be transformed to each other without breaking connectivity. The worst-case number of movements of the generic strategy is Theta(n^2). We improve this to O(n) parallel time, by a pipelining strategy, and prove optimality of both by matching lower bounds. We next turn our attention to distributed transformations. The nodes are now distributed processes able to perform communicate-compute-move rounds. We provide distributed algorithms for a general type of transformation.
Cite as

Othon Michail, George Skretas, and Paul G. Spirakis. On the Transformation Capability of Feasible Mechanisms for Programmable Matter. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 136:1-136:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{michail_et_al:LIPIcs.ICALP.2017.136,
  author =	{Michail, Othon and Skretas, George and Spirakis, Paul G.},
  title =	{{On the Transformation Capability of Feasible Mechanisms for Programmable Matter}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{136:1--136:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.136},
  URN =		{urn:nbn:de:0030-drops-74341},
  doi =		{10.4230/LIPIcs.ICALP.2017.136},
  annote =	{Keywords: programmable matter, transformation, reconfigurable robotics, shape formation, complexity, distributed algorithms}
}
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact