Robust distributed decision-making in swarm robotics

14 Sep, 2017

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, 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. The buffer state slows the propagation of erroneous beliefs 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 showed a 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.

In practice, this means choosing between faster convergence or greater fault tolerance depending on the application.

Why this matters

These results are relevant to distributed systems that require 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

Adding a small amount of complexity to individual agents (the third truth state) produced more reliable collective behaviour in our experiments.

Technical details

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

Working within these constraints while implementing the decision algorithms was a significant engineering challenge.

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

#project