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

Given 2 rectangular permutations of n^2 particles, arranges obstacles to permute in 4 moves
Updated 18 Feb 2014

View License

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.

Cite As

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

MATLAB Release Compatibility
Created with R2013a
Compatible with any release
Platform Compatibility
Windows macOS Linux

Community Treasure Hunt

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

Start Hunting!
Version Published Release Notes

Added commenting to m-file, made plot larger