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 FCOM model, the robots can only see the lights of other robots. In the FSTA model, each robot can only observe its own light. In the LUMI model, all robots can see all lights. This paper focuses on FSTA robots with 2-colored lights in synchronous settings. We show that 2-color FSTA and FCOM robots cannot solve Gathering in SSYNCH without additional assumptions, even with rigid movement and agreement on chirality. We also show a Gathering algorithm for FSTA robots with 2-color SSYNCH with minimal additional assumptions. © 2026 The Author(s)

We show that self-consistency can be a crucial property for autonomous mobile robots. Specifically, we consider the task of gathering three robots, placed adversarially in distinct locations in the Euclidean plane, in a single point. We assume the natural scheduler RoundRobin, which activates the robots in turns. An activated robot perceives all robot locations in an adversarially scaled, rotated, and mirrored Cartesian coordinate system with itself at the origin and then moves wherever it wants. We show that this task cannot be solved in the default robot model (without any consistency guarantees and no multiplicity detection) but becomes feasible if we assume self-consistency (i.e., no changes between the different activations of the same robot) of either the unit length (i.e., no scaling) or the compass (i.e., no rotating) by providing explicit algorithms. © 2025 Fabian Frei and Koichi Wada.

In this paper, we address the problem of uniformly deploying mobile robots in complete bipartite graphs. Specifically, when n robots are positioned arbitrarily at distinct nodes in a complete bipartite graph Kn,n, which consists of two n-node sets VL and VR, the uniform deployment problem requires the robots to achieve one of the following configurations: (a) each node in VL is occupied by exactly one robot, with no robots in VR, or (b) each node in VR is occupied by exactly one robot, with no robots in VL. In either configuration, the distance between any two robots is 2, ensuring that the robots are uniformly deployed. In this paper, we explore the relationship between the visibility range of robots and the solvability of the uniform deployment problem. First, we characterize solvable and unsolvable initial configurations under the assumption that robots have an infinite visibility range. Next, we demonstrate that visibility range 1 (meaning robots can only observe nodes at a distance of 1 and the robots positioned on them) is insufficient, proving the impossibility of solving the problem under this constraint. Conversely, we show that visibility range Θ(log n) is sufficient by presenting an algorithm that solves the uniform deployment problem in O(1) rounds, starting from any solvable initial configuration. Finally, we briefly introduce an example showing that robots with a constant visibility range (which is 3 in this example) cannot solve the problem in a native way. © Masahiro Shibata, Naoki Kitamura, Ryota Eguchi, Yuichi Sudo, Junya Nakamura, Yonghwan Kim, Yoshiaki Katayama, Toshimitsu Masuzawa, Quentin Bramas, and Sébastien Tixeuil;

Recently, Böckenhauer, Frei, Unger, and Wehner (SIROCCO 2023) introduced a novel variant of the graph exploration problem in which a single memoryless agent must visit all nodes of an unknown, undirected, and connected graph before returning to its starting node. Unlike the standard model for mobile agents, edges are not labeled with port numbers. Instead, the agent can color its current node and observe the color of each neighboring node. To move, it specifies a target color and then moves to an adversarially chosen neighbor of that color. They analyzed the minimum number of colors required for successful exploration and proposed an elegant algorithm that enables the agent to explore an arbitrary graph using only eight colors. In this paper, we present a novel graph exploration algorithm that requires only six colors. Furthermore, we prove that five colors are sufficient if we consider only a restricted class of graphs, which we call the φ-free graphs, a class that includes every graph with maximum degree at most three and every cactus. © Shota Takahashi, Haruki Kanaya, Shoma Hiraoka, Ryota Eguchi, and Yuichi Sudo;