Robust distributed decision-making in swarm robotics

2017/09/14

Background

During my PhD at the University of Bristol (2013-2018) I spent 3 months as a Research Assistant exploring how my ongoing research on consensus formation in multi-agent systems could be applied to collective decision-making in robot swarms. This work was focused on the "best-of-$n$" problem - a fundamental challenge in swarm robotics where a group of robots needs to collectively select the best option from multiple alternatives using only local interactions and decentralised algorithms. This problem is inspired by biological systems, such as ants and honeybees, which need to collectively decide on a new nesting location by comparing $n$ possible options.

Traditional approaches to this problem often struggle when some robots malfunction, potentially disrupting the entire swarm's decision-making process. Our research investigated how introducing a third truth state could improve robustness whilst still allowing the swarm to reach consensus.

The core idea

In classical decision-making models like the weighted voter model, robots hold binary beliefs - either "Option A is best" or "Option B is best". We proposed a three-valued model where robots could also adopt an intermediate belief state representing either "uncertain" or "indifferent".

This seemingly small change produced significant improvements in fault tolerance. Think of it as adding a buffer state that helps prevent erroneous beliefs from spreading too quickly through the swarm.

Implementation

For this project, I implemented both models in C/C++, creating algorithms that would work both in simulation and on physical robots. We used Kilobots - small, simple robots specifically designed for swarm experiments - and conducted tests with swarms of $400$ robots.

The programming involved:

• Creating efficient state-transition algorithms for both models
• Implementing communication protocols within the robots' limited capabilities
• Designing fault-tolerance mechanisms to handle malfunctioning robots
• Extending the model from binary choices to multiple options ($n>2$)

Key findings

Weighted Voter Model
(w/ malfunction)

Three-Valued Model
(w/ malfunction)

Our experiments revealed a fascinating trade-off between robustness and speed:

1. Robustness: The three-valued model was significantly more robust to malfunctioning robots. Even with $10\%$ of robots malfunctioning, it maintained $99.7\%$ convergence to the correct option, while the weighted voter model dropped to $86.5\%$.

2. Convergence Speed: However, the weighted voter model converged approximately $3$ times faster than our three-valued approach.

This demonstrated a clear engineering trade-off: when designing swarm systems, one must choose between faster convergence or greater fault tolerance based on application requirements.

Why this matters

This research has implications for any distributed system that requires collective decision-making under uncertainty:

• Search and rescue operations: Swarms exploring disaster sites need to make robust decisions even when some robots fail
• Distributed sensing networks: Environmental monitoring systems must remain reliable even with failing sensors
• Smart infrastructure: Connected systems making collective decisions need fault tolerance

The three-valued approach shows that sometimes adding complexity to individual agents (the third truth state) can actually produce more reliable collective behaviour.

Technical details

For those interested in the technical aspects, we modelled the belief updating using a truth table that determined how robots should update their beliefs when encountering others. Robots would signal their beliefs to neighbours for a time proportional to the quality of their current choice.

The implementation required careful consideration of the Kilobots' limitations:

• $10$cm communication range
• Limited memory and processing power
• Physical motion constraints
• Communication bandwidth of only up to $9$ bytes in messages

Overcoming these constraints whilst implementing sophisticated decision algorithms was part of the challenge that made this project particularly rewarding.

The code and more detailed technical information can be found in our paper published at IROS 2017.

#project