arXiv cs.MA· Subhajit Pramanick, Saswata Jana, Partha Sarathi Mandal, Gokarna Sharma·· 2 天前AI 评分12
不透明机器人在异步下的宽容聚集问题研究
Asynchronous Indulgent Gathering of Opaque Robots
AI 导读
该研究在 LUMI 模型下探讨了移动故障模型中不透明机器人的宽容聚集问题，证明 (2,1)-移动系统中使用 2 色灯无法实现宽容聚集，并给出使用 3 色灯的最优解。针对 (N,f)-移动系统提出两种确定性算法：一种使用 7 色灯、时间复杂度 O(N)，另一种使用 26 色灯、时间复杂度 O(max{ℓ,f})，首次实现时间复杂度分析，可应对不透明可见性与异步调度。
正文 · 原文
Abstract:We consider the benchmarking problem of gathering in an $(N,f)$-fault system consisting of $N$ robots, of which at most $f$ may fail at any execution. The {\em traditional} version asks $N-f$ non-faulty robots to gather at a point not known a priori. The recently studied {\em indulgent} version asks $N-f$ non-faulty robots to gather at the location of a faulty one. Indulgent gathering is impossible in a $(2,1)$-crash system in the $LUMI$ model under semi-synchrony, even when infinitely many colors and coordinate axis agreement are available. In this paper, we establish four results for indulgent gathering under asynchrony in $LUMI$, considering a {\em mobility fault} model in which a robot crash only impacts its mobility but not the operation of the light. We first show that indulgent gathering is impossible in a $(2,1)$-mobility system using 2-colored lights, and then give an optimal solution w.r.t. the number of colors using 3-colored lights. We then give two deterministic algorithms for an $(N,f)$-mobility system, $f<N$, $N,f$ unknown, that exhibit a nice time-color trade-off: One with time $O(N)$ using 7-colored lights and another with time $O(\max\{\ell,f\})$ using 26-colored lights, where $\ell< N$ is the number of distinct convex layers of robot positions in the initial configuration. Our algorithms for an $(N,f)$-mobility system are the first to be analysed time complexity, can withstand obstructed visibility (opaque robot model) and asynchronous scheduling. Interestingly, our algorithms also solve traditional gathering.
| Comments: | 37 pages, 26 figures, and 2 tables |
| Subjects: | Distributed, Parallel, and Cluster Computing (cs.DC); Multiagent Systems (cs.MA); Robotics (cs.RO) |
| Cite as: | arXiv:2509.10711 [cs.DC] |
| (or arXiv:2509.10711v2 [cs.DC] for this version) | |
| https://doi.org/10.48550/arXiv.2509.10711 arXiv-issued DOI via DataCite |
Submission history
From: Gokarna Sharma [view email]
[v1]
Fri, 12 Sep 2025 22:05:10 UTC (932 KB)
[v2]
Thu, 15 Oct 2026 11:24:14 UTC (756 KB)
来源：arXiv cs.MA · arxiv.org