A Fast and Robust Solution for Common Knowledge Formation in Decentralized Swarm Robots

Common knowledge, that is, a common understanding of environmental conditions, task objectives, coordination rules, etc., can greatly improve the collaborative efficiency of swarm robots. In many complex task scenarios, it is impossible to assume there is a central facility (e.g., a powerful robot or a back-end server that can communicate effectively with everyone) responsible for maintaining the collective's common knowledge. Instead, we must maintain it in a decentralized way. Blockchain has been proved to be an effective means of meeting this demand. It can even tolerate malicious or malfunctioning individuals to a certain extent, which is an important capability for swarm robots to operate in an open or hostile environment. However, current widely-accepted Blockchain techniques, such as Ethereum, use the proof-of-work mechanism as the basis of reaching consensus, which has to consume huge computing resources and is not suitable for swarm robots. In this paper, we present a fast and robust solution for maintaining common knowledge in swarm robots based on Hashgraph, a lightweight consensus technology being originally proposed for fully-connected, well-conditioned networks. We successfully improve its kernel mechanisms to adapt it to swarm robots with limited communication capabilities. And we novelly introduce the concept of Ranger Robot, a special kind of robot that can significantly accelerate the formation of consensus in sparsely-distributed or physically-partitioned robot swarms. Furthermore, we design a knowledge validation algorithm to enable the robot swarm to recognize attacks from a special kind of malicious robot called Byzantine robots. The results of a set of experiments based on both simulated and real robots show that our solution can greatly reduce computing overhead and accelerate the formation of consensus in comparison with solutions based on the original Hashgraph.