Separation of Three or More Autonomous Mobile Models under Hierarchical Schedulers
By: Shota Naito, Tsukasa Ninomiya, Koichi Wada
Potential Business Impact:
Robots learn to work together better.
Understanding the computational power of mobile robot systems is a fundamental challenge in distributed computing. While prior work has focused on pairwise separations between models, we explore how robot capabilities, light observability, and scheduler synchrony interact in more complex ways. We first show that the Exponential Times Expansion (ETE) problem is solvable only in the strongest model -- fully-synchronous robots with full mutual lights ($\mathcal{LUMT}^F$). We then introduce the Hexagonal Edge Traversal (HET) and TAR(d)* problems to demonstrate how internal memory and lights interact with synchrony: under weak synchrony, internal memory alone is insufficient, while full synchrony can substitute for both lights and memory. In the asynchronous setting, we classify problems such as LP-MLCv, VEC, and ZCC to show fine-grained separations between $\mathcal{FSTA}$ and $\mathcal{FCOM}$ robots. We also analyze Vertex Traversal Rendezvous (VTR) and Leave Place Convergence (LP-Cv), illustrating the limitations of internal memory in symmetric settings. These results extend the known separation map of 14 canonical robot models, revealing structural phenomena only visible through higher-order comparisons. Our work provides new impossibility criteria and deepens the understanding of how observability, memory, and synchrony collectively shape the computational power of mobile robots.
Similar Papers
Beyond Pairwise Comparisons: Unveiling Structural Landscape of Mobile Robot Models
Distributed, Parallel, and Cluster Computing
Robots learn to work together better.
Beyond Pairwise Comparisons: Unveiling Structural Landscape of Mobile Robot Models
Distributed, Parallel, and Cluster Computing
Robots learn to work together better.
Adaptive Ergodic Search with Energy-Aware Scheduling for Persistent Multi-Robot Missions
Robotics
Robots find important things and stay powered up.