2014/02/15 by Aaron T. Becker, Aaron Becker, Erik D. Demaine +6
Biochemistry, Genetics and Molecular Biology · Computer Science · Engineering · Physics and Astronomy · #DNA and Biological Computing #FOS: Computer and information sciences #Micro and Nano Robotics #Modular Robots and Swarm Intelligence #Robotic Path Planning Algorithms #Robotics (cs.RO) #cs.RO
paper · pdf · doi:10.48550/arxiv.1402.3749
8 pages, 7 figures, to appear IEEE International Conference on Robotics and Automation (ICRA 2014)
openalex publication_date 2014/02/15 · arxiv created 2014/02/16 · arxiv updated 2014/02/18 · openalex created_date 2022/08/14 · openalex updated_date 2026/07/28
Micro- and nanorobots are often controlled by global input signals, such as an electromagnetic or gravitational field. These fields move each robot maximally until it hits a stationary obstacle or another stationary robot. This paper investigates 2D motion-planning complexity for large swarms of simple mobile robots (such as bacteria, sensors, or smart building material). In previous work we proved it is NP-hard to decide whether a given initial configuration can be transformed into a desired target configuration; in this paper we prove a stronger result: the problem of finding an optimal control sequence is PSPACE-complete. On the positive side, we show we can build useful systems by designing obstacles. We present a reconfigurable hardware platform and demonstrate how to form arbitrary permutations and build a compact absolute encoder. We then take the same platform and use dual-rail logic to build a universal logic gate that concurrently evaluates AND, NAND, NOR and OR operations. Using many of these gates and appropriate interconnects we can evaluate any logical expression.