Building Patterned Shapes in Robot Swarms with Uniform Control Signals

Title: Building Patterned Shapes in Robot Swarms with Uniform Control Signals

Authors: David Caballero, Angel A. Cantu, Timothy Gomez, Austin Luchsinger, Robert Schweller, Tim Wylie

Conference: The 32nd Canadian Conference on Computational Geometry (CCCG 2020)

Abstract:
This paper investigates a restricted version of robot motion planning, in which particles on a board uniformly respond to global signals that cause them to move one unit distance in a particular direction. We look at the problem of assembling patterns within this model. We
first derive upper and lower bounds on the worst-case number of steps needed to reconfigure a general purpose board into a target pattern. We then show that the construction of k-colored patterns of size-n requires Ω(n log k) steps in general, and Ω(n log k +√k) steps if the constructed shape must always be placed in a designated output location. We then design algorithms to approach these lower bounds: We show how to construct k-colored 1 × n lines in O(n log k + k) steps with unique output locations. For general colored shapes within a w×h bounding box, we achieve O(wh log k+hk) steps.

Virtual Talk:

Accompanying Videos:

Patterned Line Building:

Section 3.2 introduces a construction for building 1xn k-colored patterns. Here is an example of a pattern being built for the constraints n=5,k=4.

Funneling Gadget:

Section 3.3 makes use of the funneling gadget, here is an example of the gadget in use.

General Pattern Builder:

Section 3.3 introduces a construction for building wxh k-colored patterns. Here is an example of a pattern being built for the constraints w=4,h=4,k=4.