2026-07-23T20:44:41Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5087 2024-03-06T10:35:49Z ddc:004 open_access

Tilt: The Video - Designing Worlds to Control Robot Swarms with Only Global Signals Becker, Aaron T. Demaine, Erik D. Fekete, Sándor P. Shad, Hamed Mohtasham Morris-Wright, Rose Particle swarms global control complexity geometric computation 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Aaron T. Becker and Erik D. Demaine and Sándor P. Fekete and Hamed Mohtasham Shad and Rose Morris-Wright 2015 Is Part Of LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SOCG.2015.16 urn:nbn:de:0030-drops-50870 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.16 eng https://creativecommons.org/licenses/by/3.0/legalcode