Resilient Multi-Robot Coordination using Network Connectivity and Trust

Abstract

The prospect of multi-robot teams have become increasingly investigated in the field of robotics due to their simplicity and diversity of potential applications. A critical challenge in achieving this vision however, is that robots must trust in the reliability of one another in order to facilitate task completion. In this thesis we seek to provide resilience to multi-robot coordination algorithms so that coordination can be preserved even in the presence of one or more misbehaving robots. We consider problems where robots share information with one another in order to coordinate their actions. In order to provide resilience against misbehaving robots, our goal is to enable the team to exchange accurate information despite the influences from potentially malicious sources. While providing resilience to a system is in general a difficult problem, we leverage unique aspects of robotic systems that allow us to tackle resilience along two directions: 1) We leverage the fact that multi-robot systems are often mobile, in which case the team can be driven to create different formations and network topologies. Along these lines, we develop controllers to reinforce the structure of the communication network by creating network topologies with many inter-robot communication links such that any robot is likely to receive more legitimate information than malicious; 2) We exploit the cyberphysical nature of multi-robot systems, i.e., the fact that they physically exist, sense, and interact with each other and their environment. This allows us to extract additional information from the system in order to estimate which robots may be trustworthy or malicious. Along these lines we develop strategies to maximize each robot's ability to gather information for estimating trustworthiness, as well as strategies for using the trust estimates to best preserve the team's performance. In the first part of the thesis we develop a control strategy that maintains resilient multi-robot networks as characterized by previous works. However, these networks impose specific constraints on the structure of the team formations, making it potentially difficult for robots to consider additional objectives besides resilience. To this end, we investigate the trade-off between the team's ability to navigate through an environment consisting of obstacles and the team's ability to maintain a formation that attains sufficient resilience. Specifically, we generalize complex environments into a set of large circular obstacles and narrow corridors, and derive analytical bounds for the maximum radius of an obstacle that a robot team can maneuver around as well as the resilience the team can provably achieve inside a narrow corridor with a given width and length. We use these results to design a formation keeping and path planning algorithm that helps a team of robots find paths between waypoints in an environment that permit resilience. Additionally, in the case where no resilient path exists through an environment, we develop a controller that takes resilience as a soft constraint, meaning it can be compromised in favor of team navigation. We derive an expression for the gain on this soft constraint controller, which we mathematically prove is required to sacrifice resilience just enough such that navigation can provably continue. While one clear determining factor in characterizing the resilience of a multi-robot team is its network topology, another is the additional information available in the network, due to its cyberphysicality, to ascertain the trustworthiness of neighboring robots. We investigate the class of information called trust observations that can be obtained from the physicality of the network, or the fact that embodied multi-robot networks operate in shared environments. We assume that these trust observations are merely estimates about the trustworthiness of a robot, and thus we develop control strategies that maximize the probability that a robot successfully estimates the true legitimacy of another robot by improving their efficiency in gathering and utilizing the trust observations. We show, both analytically and experimentally, that by following our control methods, every robot can arrive at accurate estimates of all other robots in the network with at most a user-specified failure probability. Moreover, through an algorithm called Dynamic Crowd Vetting, which utilizes trusted neighboring information, we analytically show that robots can achieve the same level of accuracy in O(T_{hit} log(N/|L|)) time, for hitting time T_{hit}, N robots, and |L| legitimate robots, compared to the case where robots independently estimate trustworthiness, which requires O(T_{meet} log(N)) time for meeting time T_{meet}. Finally, we consider several applications where the concepts of resilient topologies and detection of malicious robots can be applied to multi-robot systems. For example, we address the challenge of performing distributed event detection in the presence of malicious information by designing a framework that integrates trust observations into the detection scheme. We experimentally show that while the inclusion of malicious robots makes distributed detection more challenging, the inclusion of trust information allows us to develop algorithms that improve the probability of error compared with approaches that do not leverage auxiliary trust information. Specifically, we develop the Two Stage Approach (2SA) algorithm which uses trust information to decide whether each robot's information should be used or discarded, and then performs event detection with only the information deemed to be trustworthy. We show analytically that the 2SA algorithm provably minimizes the probability of error under a worst-case attack where the number of malicious robots in the network is maximized and they always share incorrect information. Additionally, we prove mathematically that the probability of error decays at least exponentially as the number of total robots in the network increases, and we derive an expression that relates the probability of trusting a legitimate or malicious robot with the 2SA algorithm's ability to perform event detection. In all sections we validate our derived algorithms and the theoretical results both in hardware and in simulation. Our hardware experiments use off-the-shelf hardware platforms that demonstrate the applicability and implementability of our solutions, and the agreement between our derived theoretical results and the multi-robot coordination performance in practice.