Beyond Pairwise Comparisons: Unveiling Structural Landscape of Mobile Robot Models
摘要
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 show that the Exponential Times Expansion (ETE) problem is solvable only in the strongest model–fully-synchronous robots with mutual lights ( \({\mathcal {LUMI}}^{F}\) ). The Hexagonal Edge Traversal (HET) and TAR(d)* problems illustrate how internal memory and lights interact with synchrony: under weak synchrony, memory alone is insufficient, while full synchrony can substitute for both. In the asynchronous setting, we classify problems such as LP–MLCv, VEC, and ZCC, revealing fine-grained separations between \({\mathcal {FST\!A}}\) and \({\mathcal {FCOM}}\) robots. We also analyze Vertex Traversal Rendezvous (VTR) and Leave Place Convergence (LP–Cv), showing the limitations of internal memory in symmetric scenarios. Our results extend the known separation map of 14 canonical robot models, uncovering structural phenomena only visible through higher-order comparisons and providing new criteria for impossibility.