{"id":790,"date":"2020-07-29T14:22:52","date_gmt":"2020-07-29T14:22:52","guid":{"rendered":"https:\/\/asarg.hackresearch.com\/main\/?p=790"},"modified":"2020-08-04T19:20:48","modified_gmt":"2020-08-04T19:20:48","slug":"cccg2020-building-patterned-shapes-in-robot-swarms-with-uniform-control-signals","status":"publish","type":"post","link":"https:\/\/asarg.hackresearch.com\/main\/2020\/07\/29\/cccg2020-building-patterned-shapes-in-robot-swarms-with-uniform-control-signals\/","title":{"rendered":"Building Patterned Shapes in Robot Swarms with Uniform Control Signals"},"content":{"rendered":"\n

Title<\/strong>: Building Patterned Shapes in Robot Swarms with Uniform Control Signals<\/p>\n\n\n\n

Authors:<\/strong> <\/strong>David Caballero, Angel A. Cantu, Timothy Gomez, Austin Luchsinger, Robert Schweller, Tim Wylie<\/p>\n\n\n\n

Conference: <\/strong> The 32nd Canadian Conference on Computational Geometry (CCCG 2020)<\/p>\n\n\n\n

<\/p>\n\n\n\n

Abstract:<\/strong>
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 \u2126(n log k) steps in general, and \u2126(n log k +\u221ak) 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 \u00d7 n lines in O(n log k + k) steps with unique output locations. For general colored shapes within a w\u00d7h bounding box, we achieve O(wh log k+hk) steps.<\/p>\n\n\n\n

\n
\n

Virtual Talk:<\/strong> <\/p>\n\n\n\n

\n