LIPIcs.SOCG.2015.16.pdf
- Filesize: 0.5 MB
- 3 pages
Document
Tilt: The Video - Designing Worlds to Control Robot Swarms with Only Global Signals
Authors
-
Part of:
Volume:
31st International Symposium on Computational Geometry (SoCG 2015)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Computational Geometry (SoCG) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2015-06-12
Cite As Get BibTex
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)
https://doi.org/10.4230/LIPIcs.SOCG.2015.16
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.
Subject Classification
Keywords
- Particle swarms
- global control
- complexity
- geometric computation
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Aaron T. Becker, Erik D. Demaine, Sándor P. Fekete, Golnaz Habibi, and James McLurkin. Reconfiguring massive particle swarms with limited, global control. In 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (ALGOSENSORS), volume 8343 of Springer LNCS, pages 51-66, 2013.
-
Aaron T. Becker, Erik D. Demaine, Sándor P. Fekete, and James McLurkin. Particle computation: Designing worlds to control robot swarms with only global signals. In 2014 IEEE International Conference on Robotics and Automation, ICRA 2014, Hong Kong, China, May 31 - June 7, 2014, pages 6751-6756, 2014.
-
Erik D. Demaine, Martin L. Demaine, and Joseph O'Rourke. PushPush and Push-1 are NP-hard in 2D. In Proceedings of the 12th Annual Canadian Conference on Computational Geometry (CCCG), pages 211-219, August 2000.
-
Birgit Engels and Tom Kamphans. Randolphs robot game is NP-hard! Electronic Notes in Discrete Mathematics, 25:49-53, 2006.
-
Robert A. Hearn and Erik D. Demaine. PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation. arXiv:cs/0205005, cs.CC/0205005, 2002.
-
Michael Hoffmann. Motion planning amidst movable square blocks: Push-* is NP-hard. In Canadian Conference on Computational Geometry, pages 205-210, June 2000.
-
Markus Holzer and Stefan Schwoon. Assembling molecules in ATOMIX is hard. Theoretical Computer Science, 313(3):447-462, 2004.
-
Hahmed Mohtasham Shad, Rose Morris-Wright, Erik D. Demaine, Sándor P. Fekete, and Aaron T. Becker. Particle computation: Device fan-out and binary memory. In 2015 IEEE International Conference on Robotics and Automation, ICRA Seattle, USA, May 26 - 30, 2015, page to appear, 2015.
- ThinkFun. Tilt: Gravity fed logic maze. URL: http://www.thinkfun.com/tilt.