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.
VENUE: 31st International Symposium on Computational Geometry (SOCG 2015), multimedia exposition.
http://www.win.tue.nl/SoCG2015/
AUTHORS:
Aaron T. Becker [1], Erik D. Demaine [2], Sa?ndor P. Fekete [3], Hamed Mohtasham Shad [1], and Rose Morris-Wright [1]
[1] Department of Electrical and Computer Engineering, University of Houston Houston, TX 77004, USA
[2] CSAIL, MIT Cambridge, MA 02139, USA
[email protected]
[3] Department of Computer Science, TU Braunschweig 38106 Braunschweig, Germany
Posting Permissions
Reply With Quote
Социальные закладки