Forming Sequences of Patterns with Luminous Robots

The extensive studies on computing by a team of identical mobile robots operating in the plane in Look-Compute-Move cycles have been carried out mainly in the traditional {mathcal{ OBLOT}} model, where the robots are silent (have no communication capabilities) and oblivious (in a cycle, they have no memory previous cycles). To partially overcome the limits of obliviousness and silence while maintaining some of their advantages, the stronger model of luminous robots, {mathcal{ LUMI}} , has been introduced where the robots, otherwise oblivious and silent, carry a visible light that can take a number of different colors; a color can be seen by observing robots, and persists from a cycle to the next. In the study of the computational impact of lights, an immediate concern has been to understand and determine the additional computational strength of {mathcal{ LUMI}} over {mathcal{ OBLOT}}. Within this line of investigation, we examine the problem of forming a sequence of geometric patterns, PatternSequenceFormation. A complete characterization of the sequences of patterns formable from a given starting configuration has been determined in the {mathcal{ OBLOT}} model. In this paper, we study the formation of sequences of patterns in the {mathcal{ LUMI}} model and provide a complete characterization. The characterization is constructive: our universal protocol forms all formable sequences, and it does so asynchronously and without rigidity. This characterization explicitly and clearly identifies the computational strength of {mathcal{ LUMI}} over {mathcal{ OBLOT}} with respect to the Pattern Sequence Formation problem.