Tilt: The Video - Designing Worlds to Control Robot Swarms with Only Global Signals
Tilt: The Video - Designing Worlds to Control Robot Swarms with Only Global Signals
复制标题
Tilt：视频 - 设计仅用全球信号控制机器人群的世界
DOI：
10.4230/lipics.socg.2015.16
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Rose Morris
中科院分区：
文献类型：
--
作者：
Aaron T. Becker;E. Demaine;S. Fekete;Hamed Mohtasham Shad;Rose Morris
我们在复杂环境中的微型或纳米级机器人群的计算通用性方面取得了根本性进展，这些机器人不是由个体导航控制，而是由统一的全局外力控制。更具体地说，我们考虑一个 2D 网格世界，其中所有障碍物和机器人都是单位正方形，并且对于每次驱动，机器人都会最大程度地移动，直到与障碍物或另一个机器人碰撞。目标是控制障碍物内的机器人运动，设计障碍物以实现所需的机器人排列，并建立足够复杂以允许任意计算的受控交互。在本视频中，我们展示了所有这些挑战的进展：我们演示了并行导航的 NP 难度，我们描述了如何构造允许任意排列的障碍，并且我们建立了执行任意系统内计算所需的逻辑门。
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.