In disaster situations like hurricanes, collapsed buildings, and nuclear incidents, the difference between a one-hour response time and a one-day response time can mean life or death. To mitigate these situations, multi-robot systems (MRS) are being increasingly used in search-and-rescue (SAR) operations. Unmanned robots have assisted in SAR efforts following Hurricane Katrina, the Fukushima Daiichi nuclear accident, and the Tohoku Tsunami. In these situations, it is critical for an MRS to be able to function without being disrupted. A team of researchers from Boston University and Northeastern University is working to develop security algorithms for MRS.
The team recently published a paper, titled “Byzantine Resilience At Swarm-Scale: A Decentralized Blocklist Protocol From Inter-Robot Accusations”, which has been accepted into the 22nd International Conference on Autonomous Agents and Multiagent Systems. Kacper Wardega, a Ph.D. candidate in the Dependable Computing Lab, led by CISE Faculty Affiliate Wenchao Li (ECE, SE), is the project’s student lead.
“This problem is difficult to solve and doesn’t fit neatly into a single field,” says Professor Li, whose research lies in safe, reliable, and secure systems. “By bringing together experts from different fields we’re able to find a solution for this complex problem. Professor Roberto Tron (ME, SE) contributes his expertise in robotics, and Northeastern Professor Cristina Nita-Rotaru (CS) and her student Max von Hippel (CS) have a background in security for distributed systems. The multidisciplinary nature of this team has been invaluable to the project’s success.”
The researchers are targeting robots in swarm settings, which is the cooperative behavior of a system of decentralized, self-organized robots. MRS in swarm settings can be affected by Byzantine faults, which are security threats that cause some robots in the swarm to misbehave in potentially arbitrary ways. In SAR situations, Byzantine faults can cause an MRS to malfunction, hindering operations. This team of researchers has developed a novel approach to Byzantine resilience in swarm settings called Decentralized Blocklist Protocol (DBP).
“Byzantine resilience is about tolerating arbitrary failures in an MRS so that the system as a whole can continue to do effective work,” Wardega explains. “The DBP algorithm is designed to ensure uninterrupted safety and reliability in an MRS. By developing a blocklist through peer-to-peer (P2P) communication, DBP adapts the system to enable continuous operation, even in the presence of Byzantine robots.”
The DBP algorithm is based on inter-robot accusations that detect misbehaving robots through observations made by the cooperative robots. The accusations are then propagated throughout the MRS and independently verified with a matching algorithm by each robot to develop a blocklist. DBP ensures that all byzantine robots are eventually blocked by the cooperative robots and that the system can continue to operate as a whole.
“The insight with our approach is that a single robot may have all the information it needs to determine that it received an incorrect message from a Byzantine robot,” says Wardega. “When that robot makes the accusation, its cooperative peers can reason about which robots in the swarm are untrustworthy.”
Multi-robot systems can be used in several settings ranging from SAR, to surveillance and reconnaissance, to cooperative target tracking. During SAR, robots might be tasked with searching spaces too small or dangerous for humans to access. In this situation, a robot sends messages reporting where it is and when it locates a target. Using the accusation rules, the cooperative robots can reason about whether the report is physically possible. The nature of this type of operation requires the MRS to be decentralized.
“The challenge with the DBP algorithm is to determine, in a decentralized manner, which robots are Byzantine, especially because these robots can also accuse cooperative robots,” Li says. “The accusation rules are significant because they allow the cooperative robots to check the messages being propagated through the system to determine which robots are lying, and, as a result, are Byzantine.”
The current standard for designing Byzantine resilient multi-robot systems is the Weighted-Mean Subsequence Reduced (W-MSR) algorithm. However, W-MSR does not dynamically adapt to the number of compromised robots and is empirically not practical as a method to tolerate large quantities of compromised robots.
In their paper, the researchers describe how DBP blocks and removes the influence of compromised robots, enabling the remaining cooperative robots to operate as a nominal, Byzantine-free system. Unlike W-MSR, the DBP algorithm adapts to compromised robots as they arise, requires a lesser degree of network connectivity, and allows cooperative robots to propagate useful information to each other more easily and quickly.
The results published in “Byzantine Resilience at Swarm-Scale: A Decentralized Blocklist Protocol From Inter-Robot Accusations” mark a breakthrough in Byzantine resilience for distributed multi-robot systems. In May 2023, The team will present their research at the International Conference on Autonomous Agents and Multiagent Systems, the flagship conference for research in multiagent systems.