Building Patterned Shapes in Robot Swarms with Uniform Control Signals

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.