Particle Computation: Permute an array of particles with 4 global moves

バージョン (14.2 KB) 作成者: Aaron T. Becker's Robot Swarm Lab
Given 2 rectangular permutations of n^2 particles, arranges obstacles to permute in 4 moves

ダウンロード 399 件

更新 2014/2/18


Program that permutes arranges obstacles on the plane to permute any given (ar*ac) matrix A into the (br*bc) matrix B. [ensure (ar*ac == br*bc)], where each element of A is assigned a destination in B.
Note that this is both a permutation (changing the order of pixels) and a reshaping of the matrix dimensions. There are (n!) permutations and (n) reshapes possible. You can reapply the permutation and (permutation power to get the identity.
This code also shows the history of each block by drawing a trace behind them.

Author: Aaron Becker, Summer 2013

ICRA video:

Video output:

hardware version:

Companion to ICRA 2014 paper:
"Particle Computation: Designing Worlds to Control Robot Swarms with only Global Signals" by Aaron Becker, Erik D. Demaine, Sándor P. Fekete, James McLurkin

Paper Abstract—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.


Aaron T. Becker's Robot Swarm Lab (2022). Particle Computation: Permute an array of particles with 4 global moves (, MATLAB Central File Exchange. 取得済み .

MATLAB リリースの互換性
作成: R2013a
Windows macOS Linux

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!