Tilt Motion Planning: Motion Plans for Assembling Particles with Global Control
[IROS 2023 paper: https://arxiv.org/abs/2307.02873 ] We investigate motion planning algorithms for the assembly of shapes in the tilt model in which unit-square tiles move in a grid world under the influence of uniform external forces and self-assemble according to certain rules.
We provide several heuristics and experimental evaluation of their success rate, solution length, and runtime. [code: https://github.com/RoboticSwarmContro...]
Video attachment for “Computing Motion Plans for Assembling Particles with Global Control" by
Patrick Blumenberg, Arne Schmidt, and Aaron T. Becker.
Animation shows colored tiles moved by a global signal so they all move in the same direction unless blocked.
A simple example is shown first, followed by a more challenging example.
[video 1.] This animation shows colored tiles moved by a global signal so they all move in the same direction unless blocked.
This simple example is solved using the Greatest Distance heuristic, which finds the shortest path in 21 steps.
[video 2] Each tile has glue on the four sides that only stick to compatible glues. Glue type is denoted by color.
The objective is to manipulate the tiles to bond in the shape of the connected polyomino target outlined in red.
The Polyomino Assembly Problem is PSPACE-hard, so optimal solutions are difficult to find.
This more complicated workspace was solved using the Minimum Move to Polyomino or Target.
This approach is not optimal, but is a best-first search that attempts to keep tiles not involved in the present construction step separated from each other.
This is done by pruning configurations with undesired subassemblies from the search tree.
The solution requires 473 steps.
https://ieee-iros.org/
The 2023 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2023) on October 1 – 5, 2023 at Huntington Place in Detroit, Michigan, USA.