On Fast Pattern Formation by Autonomous Robots

Abstract We consider the fundamental problem of arranging a set of n autonomous robots (points) on a real plane according to an arbitrary given pattern. Each robot operates in a, largely oblivious, look-compute-move step. We measure the time complexity of our algorithms in “epochs,” which denotes the minimum time interval in which every robot performs at least one look-compute-move step. We present a framework for the pattern formation problem in which leader election is key. Where n robots can elect a leader in T LE ( n ) epochs, we show that pattern formation can be solved in O ( T LE ( n ) ) epochs on the semi-synchronous model using robots that either are transparent (that is, the classical oblivious robots model where complete visibility is guaranteed at all times) or have lights with a constant number of colors (that is, the robots with lights model where robots are not transparent but the colors of the lights are persistent between steps). We also prove that, for some cases, the O ( T LE ( n ) ) epochs are optimal on the semi-synchronous model. Our results on the semi-synchronous model indicate that transparency and lights compensate for each other in the pattern formation problem. The proposed method runs in O ( T L E ( n ) + log ⁡ n ) epochs on the asynchronous model of robots with lights. This translates to an algorithm on the asynchronous model that runs in O ( log ⁡ n ) randomized epochs with high probability. Our algorithms do not assume agreement on direction or orientation of the robots such as global coordinate system, chirality, or one-axis agreement. Robot motions are rigid in the sense that when a robot moves it reaches its destination point at the completion of that move. The proposed algorithms are randomized and guarantee the claimed time bounds with high probability. The randomization is used only for leader election. Finally, we provide lower bounds regarding optimality of our results as well as impossibility of designing an asynchronous algorithm in the classical model.