CCCG 2020: Building Patterned Shapes in Robot Swarms with Uniform Control Signals

Описание: Authors:
David Caballero
Angel A. Cantu
Timothy Gomez
Austin Luchsinger
Robert Schweller
Tim Wylie

Abstract:
This paper investigates a restricted version of robot mo-
tion 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 pur-
pose 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 des-
ignated 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