This is the implementation of the paper "Resilient Vector Consensus in Multi-Agent Networks Using Centerpoints".
We also implemented the method proposed in "An efficient algorithm for fault-tolerant rendezvous of multi-robot systems with controllable sensing range") for a comparison with our method.
Tested on python 3.7.3
Four executable files:
- python main.py (general cases)
- python faultTolerantRendezvous.py
- python attackToOnePoint.py
- python resilienceSuperiority.py
Parameters:
n: number of robots
n_faulty: number of faulty robots (red)
n_fault_free: number of fault-free robots (blue)
method: "tver" for Tverberg point based concensus or "center" for centerpoint based consensus
pip install shapely
- 100 robots (fully connected graph)
- 30 of which are faulty and not moving
- fault-free robots should achieve consensus for both Tverberg point based and centerpoint based algorithms.
- 100 robots (fully connected graph)
- 52 faulty robots (n/2 + 2) at one point are guaranteed to make Tverberg point based fault-free robots converge to one point
- 67 faulty robots (2/3n) at one point are guaranteed to make centerpoint based fault-free robots converge to one point
- Showing centerpoint is more resilient to Tverberg point.
- 26 robots, 6 faulty robots in the left, 6 faulty robots in the right, 14 fault-free robots in the middle, divided into half equal clusters of 7 fault-free robots.
- Sensing range is 1.5 and each fault-free agent is connected to all the other fault-free robots and 6 faulty robots in either left cluster or right cluster, but not both. So each fault-free robot have 20 neighbors in the beginning.
- For Tverberg point based rendezvous, fault-free robots fail to converge to one point. Because when n = 20, Tverberg point is resilient to math.ceil(20/4) - 1 = 4 faulty robots.
- However, for centerpoint based rendezvoous, fault-free robots converge to one point. Because when n = 20, centerpoint is resilient to math.ceil(20/3) - 1 = 6 faulty robots.
@inproceedings{centerpointconcensus_ACC,
author = {Mudassir Shabbir and
Jiani Li and
Waseem Abbas and
Xenofon D. Koutsoukos},
title = {Resilient Vector Consensus in Multi-Agent Networks Using Centerpoints},
booktitle = {American Control Conference},
year = {2020}
}