Aggregation is a fundamental behavior for swarm robotics that requires a system to gather together in a compact, connected cluster. In 2014, Gauci et al. proposed a surprising algorithm that reliably achieves swarm aggregation using only a binary line-of-sight sensor and no arithmetic computation or persistent memory. It has been rigorously proven that this algorithm will aggregate one robot to another, but it remained open whether it would always aggregate a system of $n > 2$ robots as was observed in experiments and simulations. We prove that there exist deadlocked configurations from which this algorithm cannot achieve aggregation for $n > 3$ robots when the robots' motion is uniform and deterministic. On the positive side, we show that the algorithm (i) is robust to small amounts of error, enabling deadlock avoidance, and (ii) provably achieves a linear runtime speedup for the $n = 2$ case when using a cone-of-sight sensor. Finally, we introduce a noisy, discrete adaptation of this algorithm that is more amenable to rigorous analysis of noise and whose simulation results align qualitatively with the original, continuous algorithm.
翻译:群集是群装机器人的基本行为, 需要在一个紧凑、 连接的组群中集合一个系统。 2014年, Gauci 等人提出了一个令人惊讶的算法, 仅使用二进制线传感器, 而不进行算术计算或持续记忆来可靠地实现群集。 严格地证明, 这个算法将把一个机器人集中到另一个机器人身上, 但是它是否总是会像在实验和模拟中观察到的那样集中到一个 $ > 2 的系统, 但它仍然是开放的。 我们证明, 存在一个僵化的配置, 当机器人运动是统一和确定性的, 这个算法无法在3美元以上机器人中实现集成。 在积极的一面, 我们显示算法 (一) 强于小量的错误, 能够避免陷入僵局, 并且 (二) 在使用直观传感器时, 可以实现一个 $= 2 的直线速速度。 最后, 我们引入一种对这个算法的热、 离散化的调整方法, 更适合对噪音进行严格分析, 其模拟结果与原始、 连续的算法质量一致 。