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)
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.
Patterned Line Building:
General Pattern Builder: