Deadlock and Noise in Self-Organized Aggregation Without Computation


In 2014, Gauci et al. introduced a surprising algorithm for swarm aggregation that only required a single line-of-sight sensor per robot, avoiding the usual reliance on persistent memory and arithmetic computation. It was left as an open problem whether this algorithm would provably aggregate systems of $n > 2$ robots even though this was observed often in experiments. In this talk, we identify deadlock states from which the algorithm never achieves aggregation. We then present simulation results demonstrating the algorithm’s robustness to error in the robots' motions and sensors. Finally, we show how cone-of-sight sensors can improve the runtime of the algorithm when the cones are small and the number of robots is not too large.

November 17, 2021 9:40 AM
Virtual Event
Joshua J. Daymude
Joshua J. Daymude
Assistant Professor, Computer Science

I am a Christian and assistant professor in computer science studying collective emergent behavior and programmable matter through the lens of distributed computing, stochastic processes, and bio-inspired algorithms. I also love gaming and playing music.

Noble C. Harasha
Noble C. Harasha
Undergraduate Research Assistant