Document Open Access Logo

Search by a Metamorphic Robotic System in a Finite 3D Cubic Grid

Authors Ryonosuke Yamada, Yukiko Yamauchi

PDF
Thumbnail PDF

File

LIPIcs.SAND.2022.20.pdf
  • Filesize: 10.15 MB
  • 16 pages

Document Identifiers

Author Details

Ryonosuke Yamada
  • Graduate School of Information Science and Electrical Engineering, Kyushu University, Fukuoka, Japan
Yukiko Yamauchi
  • Faculty of Information Science and Electrical Engineering, Kyushu University, Fukuoka, Japan

Funding

This work was supported by JSPS KAKENHI Grant Numbers JP18H03202 and JST SICORP Grant Number JPMJSC1806, Japan.

Cite AsGet BibTex

Ryonosuke Yamada and Yukiko Yamauchi. Search by a Metamorphic Robotic System in a Finite 3D Cubic Grid. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, pp. 20:1-20:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.SAND.2022.20

Abstract

We consider search in a finite 3D cubic grid by a metamorphic robotic system (MRS), that consists of anonymous modules. A module can perform a sliding and rotation while the whole modules keep connectivity. As the number of modules increases, the variety of actions that the MRS can perform increases. The search problem requires the MRS to find a target in a given finite field. Doi et al. (SSS 2018) demonstrate a necessary and sufficient number of modules for search in a finite 2D square grid. We consider search in a finite 3D cubic grid and investigate the effect of common knowledge. We consider three different settings. First, we show that three modules are necessary and sufficient when all modules are equipped with a common compass, i.e., they agree on the direction and orientation of the x, y, and z axes. Second, we show that four modules are necessary and sufficient when all modules agree on the direction and orientation of the vertical axis. Finally, we show that five modules are necessary and sufficient when all modules are not equipped with a common compass. Our results show that the shapes of the MRS in the 3D cubic grid have richer structure than those in the 2D square grid.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
  • Computer systems organization → Robotic autonomy
Keywords
  • Distributed system
  • metamorphic robotic system
  • search
  • and 3D cubic grid

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Abdullah Almethen, Othon Michail, and Igor Potapov. On efficient connectivity-preserving transformations in a grid. In Proc. of ALGOSENSORS 2020, pages 76-91, 2020. Google Scholar
  2. Abdullah Almethen, Othon Michail, and Igor Potapov. Pushing lines helps: Efficient universal centralised transformations for programmable matter. Theoretical Computer Science, 830-831:43-59, 2020. Google Scholar
  3. Dana Angluin, Zoë Diamadi James Aspnes, Michael J. Fischer, and René Peralta. Computation in networks of passively mobile finite-state sensors. In Proc. of PODC 2004, pages 290-299, 2004. Google Scholar
  4. Shantanu Das, Paola Flocchini, Giuseppe Prencipe, Nicola Santoro, and Masafumi Yamashita. Autonomous mobile robots with lights. Theoretical Computer Science, 609:171-184, 2016. Google Scholar
  5. Zahra Derakhshandeh, Shlomi Dolev, Robert Gmyr, Andréa W. Richa, Christian Scheideler, and Thim Strothmann. Brief announcement: amoebot - a new model for programmable matter. In Proc. of SPAA 2014, pages 220-222, 2014. Google Scholar
  6. Zahra Derakhshandeh, Robert Gmyr, Andréa W. Richa, Christian Scheideler, and Thim Strothmann. An algorithmic framework for shape formation problems in self-organizing particle systems. In Proc. of NANOCOM 2015, pages 21:1-21:2, 2015. Google Scholar
  7. Keisuke Doi, Yukiko Yamauchi, Shuji Kijima, and Masafumi Yamashita. Exploration of finite 2d square grid by a metamorphic robotic system. In Proc. of SSS 2018, pages 96-110, 2018. Google Scholar
  8. Adrian Dumitrescu and János Pach. Pushing squares around. Graphs and Combinatorics, 22:37-50, 2006. Google Scholar
  9. Adrian Dumitrescu, Ichiro Suzuki, and Masafumi Yamashita. Formations for fast locomotion of metamorphic robotic systems. The International Journal of Robotics Research, 23(6):583-593, 2004. Google Scholar
  10. Adrian Dumitrescu, Ichiro Suzuki, and Masafumi Yamashita. Motion planning for metamorphic systems: feasibility, decidability, and distributed reconfiguration. IEEE Transactions on Robotics, 20(3):409-418, 2004. Google Scholar
  11. Nao Fujinaga, Yukiko Yamauchi, Hirotaka Ono, Shuji Kijima, and Masafumi Yamashita. Pattern formation by oblivious asynchronous mobile robots. SIAM Journal on Computing, 44(3):740-785, 2015. Google Scholar
  12. Giuseppe Antonio Di Luna, Paola Flocchini, Nicola Santoro, Giovanni Viglietta, and Yukiko Yamauchi. Shape formation by programmable particles. Distributed Computing, 33(1):69-101, 2020. Google Scholar
  13. Othon Michail, George Skretas, and Paul G. Spirakis. On the transformation capability of feasible mechanisms for programmable matter. Journal of Computer and System Sciences, 102:18-39, 2019. Google Scholar
  14. Junya Nakamura, Sayaka Kamei, and Yukiko Yamauchi. Evacuation from a finite 2d square grid field by a metamorphic robotic system. In Proc. of CANDAR 2020, pages 69-78, 2020. Google Scholar
  15. Michael Rubenstein, Alejandro Cornejo, and Radhika Nagpal. Programmable self-assembly in a thousand-robot swarm. Science, 345(6198):795-799, 2014. Google Scholar
  16. Ichiro Suzuki and Masafumi Yamashita. Distributed anonymous mobile robots: Formation of geometric patterns. SIAM Journal on Computing, 28(4):1347-1363, 1999. Google Scholar
  17. Pierre Thalamy, Benoît Piranda, and Julien Bourgeois. Distributed self-reconfiguration using a deterministic autonomous scaffolding structure. In Proc. of AAMAS 2019, pages 140-148, 2019. Google Scholar
  18. Ryonosuke Yamada. MRS demonstration videos. URL: http://tcs.inf.kyushu-u.ac.jp/~yamauchi/MRSdemonstrations.html.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact