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})，首次实现时间复杂度分析，可应对不透明可见性与异步调度。
正文 · AI 翻译
摘要：我们考虑在由 $N$ 个机器人组成的 $(N,f)$-故障系统中进行聚集的基准测试问题，其中至多 $f$ 个机器人在任何一次执行中可能发生故障。{\em 传统}版本要求 $N-f$ 个非故障机器人在一个事先未知的点聚集。最近研究的{\em 宽容}版本要求 $N-f$ 个非故障机器人在一个故障机器人的位置聚集。在半同步下的 $LUMI$ 模型中，宽容聚集在 $(2,1)$-崩溃系统中是不可能的，即使有无限多种颜色和坐标轴一致性可用。在本文中，我们在 $LUMI$ 中的异步条件下，考虑一种{\em 移动性故障}模型（其中机器人崩溃只影响其移动性而不影响灯的操作），为宽容聚集建立了四个结果。我们首先证明，使用 2 色灯的宽容聚集在 $(2,1)$-移动性系统中是不可能的，然后给出一个关于颜色数最优的、使用 3 色灯的解决方案。接着，我们为 $(N,f)$-移动性系统（$f<N$，$N,f$ 未知）给出两个确定性算法，它们展现出良好的时间-颜色权衡：一个使用 7 色灯、时间为 $O(N)$，另一个使用 26 色灯、时间为 $O(\max\{\ell,f\})$，其中 $\ell< N$ 是初始配置中机器人位置的不同凸层数。我们针对 $(N,f)$-移动性系统的算法是首批被分析时间复杂度的算法，能够承受遮挡可见性（不透明机器人模型）和异步调度。有趣的是，我们的算法也能解决传统聚集问题。
| 评论： | 37 页，26 幅图，2 张表 |
| 主题： | 分布式、并行与集群计算 (cs.DC)；多智能体系统 (cs.MA)；机器人学 (cs.RO) |
| 引用为： | arXiv:2509.10711 [cs.DC] |
| （或 arXiv:2509.10711v2 [cs.DC] 用于此版本） | |
| https://doi.org/10.48550/arXiv.2509.10711 由 DataCite 颁发的 arXiv DOI |
提交历史
来自：Gokarna Sharma [查看电子邮件]
[v1]
2025 年 9 月 12 日星期五 22:05:10 UTC（932 KB）
[v2]
2026 年 10 月 15 日星期四 11:24:14 UTC（756 KB）
来源：arXiv cs.MA · arxiv.org