Gathering semi-synchronously scheduled two-state robots

• We study the Gathering problem for n mobile robots endowed with two-color lights in semi-synchronous (Ssynch) environments. • We focus on two models: F ST A (where robots see only their own light) and F COM (where robots see only each others’ lights). • We prove existing upper bounds to be optimal. In particular, we show that, even with rigid movement and consistent chirality, Gathering is impossible with only 2 colors in both F ST A and F COM under Ssynchunless additional assumptions are introduced. • We provide a constructive algorithm demonstrating that, relying on minimal extra assumptions, F ST A robots with 2 colors can solve Gathering in Ssynch. We study the problem Gathering for n autonomous mobile robots in semi-synchronous settings with a persistent memory called light . It is well known that Gathering is impossible in the basic model ( OBLOT ) where robots have no lights, even if the system is semi-synchronous (called Ssynch ). Gathering becomes possible, however, if each robot has a light of some type that can be set to a constant number of colors. In the F COM model, the robots can only see the lights of other robots. In the F ST A model, each robot can only observe its own light. In the LUMI model, all robots can see all lights. This paper focuses on F ST A robots with 2-colored lights in synchronous settings. We show that 2-color F ST A and F COM robots cannot solve Gathering in Ssynch without additional assumptions, even with rigid movement and agreement on chirality. We also show a Gathering algorithm for F ST A robots with 2-color Ssynch with minimal additional assumptions.