证明了无计算能力的机器人无法在任意初始状态下实现自组织聚集。
Impossibility of Self-Organized Aggregation without Computation
- 通过分析控制器的几何结构，证明无计算能力下无法设计通用聚集算法。
- 推翻了此前两机器人聚集的数学证明，并提出新控制器与严格证明。
- 适合对分布式系统、机器人协同与理论计算机科学感兴趣的读者。
Gauci 等人（2014）研究了聚合这一基础任务：多个机器人需在无预设会合点的情况下聚集，仅使用最小硬件。该工作考虑的是无记忆、无计算能力的差速驱动机器人，无法通信，仅配备能检测前方是否有其他机器人的简单传感器。尽管存在这些严苛限制，他们提出一个控制器并数学证明其可使两机器人系统在任意初始状态下聚集。然而，对于更大规模系统，同一控制器虽在多数情况下有效，但并非总是成立。因此，是否存在一个能在任意数量机器人下均能保证聚集的控制器，仍是未解之谜。本文通过分析控制器的几何结构，证明此类控制器根本不存在。此外，我们推翻了前述两机器人聚集的数学证明，提出一种新控制器，并给出简洁严谨的聚合证明。
原文摘要 · Abstract (English)
In their seminal work, Gauci et al. (2014) studied the fundamental task of aggregation, wherein multiple robots need to gather without an a priori agreed-upon meeting location, using minimal hardware. That paper considered differential-drive robots that are memoryless and unable to compute. Moreover, the robots cannot communicate with one another and are only equipped with a simple sensor that determines whether another robot is directly in front of them. Despite those severe limitations, Gauci et al. introduced a controller and proved mathematically that it aggregates a system of two robots for any initial state. Unfortunately, for larger systems, the same controller aggregates empirically in many cases but not all. Thus, the question of whether a controller exists that aggregates for any number of robots remains open. In this paper, we show that no such controller exists by investigating the geometric structure of controllers. In addition, we disprove the aggregation proof of the paper above for two robots and present an alternative controller alongside a simple and rigorous aggregation proof.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。