揭示移动机器人模型中同步、记忆与可观测性的复杂相互作用
Beyond Pairwise Comparisons: Unveiling Structural Landscape of Mobile Robot Models
- 通过高阶比较揭示同步性、内存与灯光的协同效应
- 发现完全同步下内存和灯光可互相替代，弱同步时仅靠内存不足
- 适用于分布式计算与机器人系统理论研究者
理解移动机器人系统的计算能力是分布式计算中的基本挑战。以往研究集中于模型间的成对分离，本文探索机器人能力、光信号可观测性与调度同步性在更复杂交互下的影响。首先证明指数时间扩展（ETE）问题仅在最强模型——完全同步且具备完整互视灯光的$\mathcal{LUMT}^F$模型中可解。随后引入六边形边遍历（HET）和TAR(d)*问题，展示内部记忆与灯光如何随同步性变化而相互作用：在弱同步下，仅靠内部记忆不足以解决问题，而完全同步可替代灯光与记忆。在异步设置中，对LP-MLCv、VEC、ZCC等问题分类分析，揭示了$\mathcal{FSTA}$与$\mathcal{FCOM}$模型间的精细区分。还分析了顶点遍历会合（VTR）与离开位置收敛（LP-Cv），说明对称环境下内部记忆的局限性。这些结果拓展了14个典型机器人模型的已知分离图谱，揭示了仅通过高阶比较才能显现的结构性现象。本工作提出新的不可能性判据，深化了对可观测性、记忆与同步性共同塑造移动机器人计算能力的理解。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。