7 papers
A Minimum Exact Disjunctive Basis for Two-Robot Solvability Profiles
Tsukasa Ninomiya, Shota Naito, Naoki Kitamura +2
We completely characterize the solvability profiles of tasks for two autonomous mobile robots in the plane under variable disorientation, chirality, and rigid movements. The four s…
Rendezvous under Variable Disorientation:The Algorithmic Power of Fixed Unit Distance
Toshimitsu Masuzawa, Yuichi Sudo, Koichi Wada
We study deterministic Rendezvous of two robots with lights under weak geometric and synchronization assumptions. Our focus is on Variable Disorientation (VD), where each robot may…
Tight Bounds on Window Size and Time for Single-Agent Graph Exploration under T-Interval Connectivity
Yuichi Sudo, Naoki Kitamura, Masahiro Shibata +4
We study deterministic exploration by a single agent in -interval-connected graphs, a standard model of dynamic networks in which, for every time window of length , the inter…
Two-Robot Computational Landscape: A Complete Characterization of Model Power in Minimal Mobile Robot Systems
Naoki Kitamura, Yuichi Sudo, Koichi Wada
The computational power of autonomous mobile robots under the Look-Compute-Move (LCM) model has been widely studied through an extensive hierarchy of robot models defined by the pr…
Complementary Time-Space Tradeoff for Self-Stabilizing Leader Election: Polynomial States Meet Sublinear Time
Yuichi Sudo
We study the self-stabilizing leader election (SS-LE) problem in the population protocol model, assuming exact knowledge of the population size . Burman, Chen, Chen, Doty, Nowak…
Sublinear-time Collision Detection with a Polynomial Number of States in Population Protocols
Takumi Araya, Yuichi Sudo
This paper addresses the collision detection problem in population protocols. The network consists of state machines called agents. At each time step, exactly one pair of agents is…
On Asynchrony, Memory, and Communication: Separations and Landscapes
Paola Flocchini, Nicola Santoro, Yuichi Sudo +1
Research on distributed computing by a team of identical mobile computational entities, called robots, operating in a Euclidean space in --$\mathit…