Particle computation: Designing worlds to control robot swarms with only global signals
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 sim...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2015
|
| Online Access: | http://hdl.handle.net/1721.1/100006 https://orcid.org/0000-0003-3803-5703 |
| _version_ | 1811096765217112064 |
|---|---|
| author | Becker, Aaron Demaine, Erik D. Fekete, Sandor P. McLurkin, James |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Becker, Aaron Demaine, Erik D. Fekete, Sandor P. McLurkin, James |
| author_sort | Becker, Aaron |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T16:48:41Z |
| format | Article |
| id | mit-1721.1/100006 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T16:48:41Z |
| publishDate | 2015 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/1000062022-09-29T21:41:07Z Particle computation: Designing worlds to control robot swarms with only global signals Becker, Aaron Demaine, Erik D. Fekete, Sandor P. McLurkin, James Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Demaine, Erik D. 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. National Science Foundation (U.S.) (CPS-1035716) 2015-11-23T17:27:58Z 2015-11-23T17:27:58Z 2014-05 Article http://purl.org/eprint/type/ConferencePaper 978-1-4799-3685-4 http://hdl.handle.net/1721.1/100006 Becker, Aaron, Erik D. Demaine, Sandor P. Fekete, and James McLurkin. “Particle Computation: Designing Worlds to Control Robot Swarms with Only Global Signals.” 2014 IEEE International Conference on Robotics and Automation (ICRA) (May 2014). https://orcid.org/0000-0003-3803-5703 en_US http://dx.doi.org/10.1109/ICRA.2014.6907856 Proceedings of the 2014 IEEE International Conference on Robotics and Automation (ICRA) Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) arXiv |
| spellingShingle | Becker, Aaron Demaine, Erik D. Fekete, Sandor P. McLurkin, James Particle computation: Designing worlds to control robot swarms with only global signals |
| title | Particle computation: Designing worlds to control robot swarms with only global signals |
| title_full | Particle computation: Designing worlds to control robot swarms with only global signals |
| title_fullStr | Particle computation: Designing worlds to control robot swarms with only global signals |
| title_full_unstemmed | Particle computation: Designing worlds to control robot swarms with only global signals |
| title_short | Particle computation: Designing worlds to control robot swarms with only global signals |
| title_sort | particle computation designing worlds to control robot swarms with only global signals |
| url | http://hdl.handle.net/1721.1/100006 https://orcid.org/0000-0003-3803-5703 |
| work_keys_str_mv | AT beckeraaron particlecomputationdesigningworldstocontrolrobotswarmswithonlyglobalsignals AT demaineerikd particlecomputationdesigningworldstocontrolrobotswarmswithonlyglobalsignals AT feketesandorp particlecomputationdesigningworldstocontrolrobotswarmswithonlyglobalsignals AT mclurkinjames particlecomputationdesigningworldstocontrolrobotswarmswithonlyglobalsignals |