DROPS

Document

DOI: 10.4230/LIPIcs.SOCG.2015.16

Tilt: The Video - Designing Worlds to Control Robot Swarms with Only Global Signals

Authors: Aaron T. Becker, Erik D. Demaine, Sándor P. Fekete, Hamed Mohtasham Shad, and Rose Morris-Wright

Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)

Abstract

We present fundamental progress on the computational universality of swarms of micro- or nano-scale robots in complex environments, controlled not by individual navigation, but by a uniform global, external force. More specifically, we consider a 2D grid world, in which all obstacles and robots are unit squares, and for each actuation, robots move maximally until they collide with an obstacle or another robot. The objective is to control robot motion within obstacles, design obstacles in order to achieve desired permutation of robots, and establish controlled interaction that is complex enough to allow arbitrary computations. In this video, we illustrate progress on all these challenges: we demonstrate NP-hardness of parallel navigation, we describe how to construct obstacles that allow arbitrary permutations, and we establish the necessary logic gates for performing arbitrary in-system computations.

Cite as

Aaron T. Becker, Erik D. Demaine, Sándor P. Fekete, Hamed Mohtasham Shad, and Rose Morris-Wright. Tilt: The Video - Designing Worlds to Control Robot Swarms with Only Global Signals. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 16-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{becker_et_al:LIPIcs.SOCG.2015.16,
  author =	{Becker, Aaron T. and Demaine, Erik D. and Fekete, S\'{a}ndor P. and Shad, Hamed Mohtasham and Morris-Wright, Rose},
  title =	{{Tilt: The Video - Designing Worlds to Control Robot Swarms with Only Global Signals}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{16--18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Arge, Lars and Pach, J\'{a}nos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.16},
  URN =		{urn:nbn:de:0030-drops-50870},
  doi =		{10.4230/LIPIcs.SOCG.2015.16},
  annote =	{Keywords: Particle swarms, global control, complexity, geometric computation}
}

Search Results

Documents authored by Shad, Hamed Mohtasham

Tilt: The Video - Designing Worlds to Control Robot Swarms with Only Global Signals

Abstract

Cite as

Thanks for your feedback!

Could not send message