Byzantine Resilience at Swarm Scale: A Decentralized Blocklist Protocol from Inter-robot Accusations
Authors: 
Kacper Wardega, Max von Hippel, Roberto Tron, Cristina Nita-Rotaru, 
Wenchao LiAuthors Info & Claims
Pages 1430 - 1438
Abstract
The Weighted-Mean Subsequence Reduced (W-MSR) algorithm, the state-of-the-art method for Byzantine-resilient design of decentralized multi-robot systems, is based on discarding outliers received over Linear Consensus Protocol (LCP). Although W-MSR provides theoretical guarantees relating network connectivity to the convergence of the underlying consensus, W-MSR comes with several limitations: the number of Byzantine robots, F, to tolerate should be known a priori, each robot needs to maintain 2F+1 neighbors, F+1 robots must independently make local measurements of the consensus property in order for the swarm's decision to change, and W-MSR is specific to LCP and does not generalize to applications not implemented over LCP. In this work, we propose a Decentralized Blocklist Protocol (DBP) based on inter-robot accusations. Accusations are made on the basis of locally-made observations of misbehavior, and once shared by cooperative robots across the network are used as input to a graph matching algorithm that computes a blocklist. DBP generalizes to applications not implemented via LCP, is adaptive to the number of Byzantine robots, and allows for fast information propagation through the multi-robot system while simultaneously reducing the required network connectivity relative to W-MSR. On LCP-type applications, DBP reduces the worst-case connectivity requirement of W-MSR from (2F+1)-connected to (F+1)-connected and the minimum number of cooperative observers required to propagate new information from F+1 to just 1 observer. We demonstrate that our approach to Byzantine resilience scales to hundreds of robots on target tracking, time synchronization, and localization case studies.
References
[1]
USP Srinivas Aditya, Roshan Singh, Pranav Kumar Singh, and Anshuman Kalla. 2021. A Survey on Blockchain in Robotics: Issues, Opportunities, Challenges and Future Directions. Journal of Network and Computer Applications, Vol. 196 (2021), 103245.
[2]
Neda Amirian and Saeed Shamaghdari. 2021. Distributed resilient flocking control of multi-agent systems through event/self-triggered communication. IET Control Theory & Applications, Vol. 15, 4 (2021), 559--569. https://doi.org/10.1049/cth2.12061 _eprint: https://onlinelibrary.wiley.com/doi/pdf/10.1049/cth2.12061.
[3]
Filippo Arrichiello, Alessandro Marino, and Francesco Pierri. 2015. Observer-based decentralized fault detection and isolation strategy for networked multirobot systems. IEEE Transactions on Control Systems Technology, Vol. 23, 4 (2015), 1465--1476. Publisher: IEEE.
[4]
Yotam Ashkenazi, Shlomi Dolev, Sayaka Kamei, Fukuhito Ooshita, and Koichi Wada. 2019. Forgive & Forget: Self-Stabilizing Swarms in Spite of Byzantine Robots. In 2019 Seventh International Symposium on Computing and Networking Workshops (CANDARW). 188--194. https://doi.org/10.1109/CANDARW.2019.00041
[5]
Shahriar Bijani and David Robertson. 2014. A review of attacks and security approaches in open multi-agent systems. Artificial Intelligence Review, Vol. 42, 4 (2014), 607--636. Publisher: Springer.
[6]
Mingxi Cheng, Chenzhong Yin, Junyao Zhang, Shahin Nazarian, Jyotirmoy Deshmukh, and Paul Bogdan. 2021. A general trust framework for multi-agent systems. In Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems. 332--340.
[7]
Seddik M Djouadi, Alexander M Melin, Erik M Ferragut, Jason A Laska, Jin Dong, and Anis Drira. 2015. Finite energy and bounded actuator attacks on cyber-physical systems. In 2015 European Control Conference (ECC). IEEE, 3659--3664.
[8]
Jack Edmonds. 1965. Paths, trees, and flowers. Canadian Journal of mathematics, Vol. 17 (1965), 449--467.
[9]
Adriano Fagiolini, Marco Pellinacci, Gianni Valenti, Gianluca Dini, and Antonio Bicchi. 2008. Consensus-based Distributed Intrusion Detection for Multi-Robot Systems. In 2008 IEEE International Conference on Robotics and Automation. 120--127. https://doi.org/10.1109/ROBOT.2008.4543196 ISSN: 1050--4729.
[10]
Adriano Fagiolini, Gianni Valenti, Lucia Pallottino, Gianluca Dini, and Antonio Bicchi. 2007. Decentralized intrusion detection for secure cooperative multi-agent systems. In 2007 46th IEEE Conference on Decision and Control. IEEE, 1553--1558.
[11]
Jennifer Gielis, Ajay Shankar, and Amanda Prorok. 2022. A Critical Review of Communications in Multi-robot Systems. Current Robotics Reports (Aug. 2022). https://doi.org/10.1007/s43154-022-00090--9
[12]
Stephanie Gil, Swarun Kumar, Mark Mazumder, Dina Katabi, and Daniela Rus. 2017. Guaranteeing spoof-resilient multi-robot networks. Autonomous Robots, Vol. 41, 6 (2017), 1383--1400. Publisher: Springer.
[13]
Luis Guerrero-Bonilla, Amanda Prorok, and Vijay Kumar. 2017. Formations for Resilient Robot Teams. IEEE Robotics and Automation Letters, Vol. 2, 2 (April 2017), 841--848. https://doi.org/10.1109/LRA.2017.2654550 Conference Name: IEEE Robotics and Automation Letters.
[14]
Pinyao Guo, Hunmin Kim, Nurali Virani, Jun Xu, Minghui Zhu, and Peng Liu. 2018. RoboADS: Anomaly detection against sensor and actuator misbehaviors in mobile robots. In 2018 48th Annual IEEE/IFIP international conference on dependable systems and networks (DSN). IEEE, 574--585.
[15]
Heath J. LeBlanc, Haotian Zhang, Xenofon Koutsoukos, and Shreyas Sundaram. 2013. Resilient Asymptotic Consensus in Robust Networks. IEEE Journal on Selected Areas in Communications, Vol. 31, 4 (April 2013), 766--781. https://doi.org/10.1109/JSAC.2013.130413 Conference Name: IEEE Journal on Selected Areas in Communications.
[16]
Jun Liu, Lifeng Zhou, Pratap Tokekar, and Ryan K. Williams. 2021. Distributed Resilient Submodular Action Selection in Adversarial Environments. IEEE Robotics and Automation Letters, Vol. 6, 3 (July 2021), 5832--5839. https://doi.org/10.1109/LRA.2021.3080629 arXiv: 2105.07305.
[17]
Frederik Mallmann-Trenn, Matthew Cavorsi, and Stephanie Gil. 2021. Crowd Vetting: Rejecting Adversaries via Collaboration With Application to Multirobot Flocking. IEEE Transactions on Robotics (2021), 1--20. https://doi.org/10.1109/TRO.2021.3089033 Conference Name: IEEE Transactions on Robotics.
[18]
Aritra Mitra, John A. Richards, Saurabh Bagchi, and Shreyas Sundaram. 2019. Resilient distributed state estimation with mobile agents: overcoming Byzantine adversaries, communication losses, and intermittent measurements. Autonomous Robots, Vol. 43, 3 (March 2019), 743--768. https://doi.org/10.1007/s10514-018--9813--7
[19]
Alexandre Pacheco, Volker Strobel, and Marco Dorigo. 2020. A blockchain-controlled physical robot swarm communicating via an ad-hoc network. In International Conference on Swarm Intelligence. Springer, 3--15.
[20]
Alyssa Pierson and Mac Schwager. 2016. Adaptive Inter-Robot Trust for Robust Multi-Robot Sensor Coverage. In Robotics Research, Masayuki Inaba and Peter Corke (Eds.). Vol. 114. Springer International Publishing, Cham, 167--183. https://doi.org/10.1007/978--3--319--28872--7_10 Series Title: Springer Tracts in Advanced Robotics.
[21]
Carlo Pinciroli, Vito Trianni, Rehan O'Grady, Giovanni Pini, Arne Brutschy, Manuele Brambilla, Nithin Mathews, Eliseo Ferrante, Gianni Di Caro, Frederick Ducatelle, Mauro Birattari, Luca Maria Gambardella, and Marco Dorigo. 2012. ARGoS: a Modular, Parallel, Multi-Engine Simulator for Multi-Robot Systems. Swarm Intelligence, Vol. 6, 4 (2012), 271--295.
[22]
Venkatraman Renganathan and Tyler Summers. 2017. Spoof resilient coordination for distributed multi-robot systems. In 2017 International Symposium on Multi-Robot and Multi-Agent Systems (MRS). IEEE, 135--141.
[23]
David Saldaña, Amanda Prorok, Shreyas Sundaram, Mario F. M. Campos, and Vijay Kumar. 2017. Resilient consensus for time-varying networks of dynamic agents. In 2017 American Control Conference (ACC). 252--258. https://doi.org/10.23919/ACC.2017.7962962 ISSN: 2378--5861.
[24]
Kelsey Saulnier, David Saldaña, Amanda Prorok, George J. Pappas, and Vijay Kumar. 2017. Resilient Flocking for Mobile Robot Teams. IEEE Robotics and Automation Letters, Vol. 2, 2 (April 2017), 1039--1046. https://doi.org/10.1109/LRA.2017.2655142 Conference Name: IEEE Robotics and Automation Letters.
[25]
Yasser Shoukry, Shaunak Mishra, Zutian Luo, and Suhas Diggavi. 2018. Sybil attack resilient traffic networks: A physics-based trust propagation approach. In 2018 ACM/IEEE 9th International Conference on Cyber-Physical Systems (ICCPS). IEEE, 43--54.
[26]
Volker Strobel, Eduardo Castelló Ferrer, and Marco Dorigo. 2018. Managing Byzantine Robots via Blockchain Technology in a Swarm Robotics Collective Decision Making Scenario. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems (Stockholm, Sweden) (AAMAS '18). International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 541--549.
[27]
Janardan Kumar Verma and Virender Ranga. 2021. Multi-Robot Coordination Analysis, Taxonomy, Challenges and Future Scope. Journal of Intelligent & Robotic Systems, Vol. 102, 1 (May 2021), 10. https://doi.org/10.1007/s10846-021-01378--2
[28]
Matthew Weber, Baihong Jin, Gil Lederman, Yasser Shoukry, Edward A. Lee, Sanjit Seshia, and Alberto Sangiovanni-Vincentelli. 2020. Gordian: Formal Reasoning-based Outlier Detection for Secure Localization. ACM Transactions on Cyber-Physical Systems, Vol. 4, 4 (Aug. 2020), 1--27. https://doi.org/10.1145/3386568
[29]
Jean-Paul A. Yaacoub, Hassan N. Noura, Ola Salman, and Ali Chehab. 2022. Robotics cyber security: vulnerabilities, attacks, countermeasures, and recommendations. International Journal of Information Security, Vol. 21, 1 (Feb. 2022), 115--158. https://doi.org/10.1007/s10207-021-00545--8
[30]
Lifeng Zhou and Pratap Tokekar. 2021. Multi-Robot Coordination and Planning in Uncertain and Adversarial Environments. Current Robotics Reports, Vol. 2, 2 (June 2021), 147--157. https://doi.org/10.1007/s43154-021-00046--5 arXiv: 2105.00389.
[31]
Lifeng Zhou, Vasileios Tzoumas, George J. Pappas, and Pratap Tokekar. 2020. Distributed Attack-Robust Submodular Maximization for Multi-Robot Planning. In 2020 IEEE International Conference on Robotics and Automation (ICRA). 2479--2485. https://doi.org/10.1109/ICRA40945.2020.9197243 ISSN: 2577-087X.
Index Terms
- Byzantine Resilience at Swarm Scale: A Decentralized Blocklist Protocol from Inter-robot Accusations
Recommendations
An adaptive reservation time division multiple access control protocol for robot inter-communication
In autonomous distributed robot systems, many robots cooperate together to carry out many difficult tasks that single robots cannot realise. But, in order to cooperate together the robots should communicate with each other. Therefore, the inter-...
Decentralized probabilistic multi-robot collision avoidance using buffered uncertainty-aware Voronoi cells
AbstractIn this paper, we present a decentralized and communication-free collision avoidance approach for multi-robot systems that accounts for both robot localization and sensing uncertainties. The approach relies on the computation of an uncertainty-...
Multi Robot Collision Avoidance with Continuous Curvature Manoeuvres
AIR '13: Proceedings of Conference on Advances In RoboticsIn this paper, we address the problem of reactive collision avoidance among multiple robots. However we impose the constraint of continuous curvature on the collision avoidance manoeuvre which adds to the complexity of the problem but is necessary for ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
May 2023
3131 pages
ISBN:9781450394321
- General Chairs:
- Noa Agmon,
- Bo An,
- Program Chairs:
- Alessandro Ricci,
- William Yeoh
Sponsors
Publisher
International Foundation for Autonomous Agents and Multiagent Systems
Richland, SC
Publication History
Published: 30 May 2023
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- National Science Foundation
Conference
AAMAS '23
Sponsor:
AAMAS '23: International Conference on Autonomous Agents and Multiagent Systems
May 29 - June 2, 2023
London, United Kingdom
Acceptance Rates
Overall Acceptance Rate 1,155 of 5,036 submissions, 23%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 36Total Downloads
- Downloads (Last 12 months)15
- Downloads (Last 6 weeks)6
Reflects downloads up to 22 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in