We develop a resilient binary hypothesis testing framework for decision making in adversarial multi-robot crowdsensing tasks. This framework exploits stochastic trust observations between robots to arrive at tractable, resilient decision making at a centralized Fusion Center (FC) even when i) there exist malicious robots in the network and their number may be larger than the number of legitimate robots, and ii) the FC uses one-shot noisy measurements from all robots. We derive two algorithms to achieve this. The first is the Two Stage Approach (2SA) that estimates the legitimacy of robots based on received trust observations, and provably minimizes the probability of detection error in the worst-case malicious attack. Here, the proportion of malicious robots is known but arbitrary. For the case of an unknown proportion of malicious robots, we develop the Adversarial Generalized Likelihood Ratio Test (A-GLRT) that uses both the reported robot measurements and trust observations to estimate the trustworthiness of robots, their reporting strategy, and the correct hypothesis simultaneously. We exploit special problem structure to show that this approach remains computationally tractable despite several unknown problem parameters. We deploy both algorithms in a hardware experiment where a group of robots conducts crowdsensing of traffic conditions on a mock-up road network similar in spirit to Google Maps, subject to a Sybil attack. We extract the trust observations for each robot from actual communication signals which provide statistical information on the uniqueness of the sender. We show that even when the malicious robots are in the majority, the FC can reduce the probability of detection error to 30.5% and 29% for the 2SA and the A-GLRT respectively.
more »
« less
This content will become publicly available on May 29, 2024
Exploiting Trust for Resilient Hypothesis Testing with Malicious Robots
We develop a resilient binary hypothesis testing framework
for decision making in adversarial multi-robot crowdsensing
tasks. This framework exploits stochastic trust observations between
robots to arrive at tractable, resilient decisionmaking at a centralized
Fusion Center (FC) even when i) there exist malicious robots in
the network and their number may be larger than the number of
legitimate robots, and ii) the FC uses one-shot noisy measurements
from all robots.We derive two algorithms to achieve this. The first
is the Two Stage Approach (2SA) that estimates the legitimacy of
robots based on received trust observations, and provably minimizes
the probability of detection error in the worst-case malicious attack.
Here, the proportion of malicious robots is known but arbitrary. For
the case of an unknown proportion of malicious robots, we develop
the Adversarial Generalized Likelihood Ratio Test (A-GLRT) that
uses both the reported robot measurements and trust observations to
estimate the trustworthiness of robots, their reporting strategy, and
the correct hypothesis simultaneously. We exploit special problem
structure to show that this approach remains computationally
tractable despite several unknown problem parameters.We deploy
both algorithms in a hardware experiment where a group of robots
conducts crowdsensing of traffic conditions on a mock-up road
network similar in spirit toGoogleMaps, subject to a Sybil attack.We
extract the trust observations for each robot from actual communication
signals which provide statistical information on the uniqueness
of the sender.We show that even when the malicious robots are in
the majority, the FC can reduce the probability of detection error to
30.5% and 29% for the 2SA and the A-GLRT respectively.
more »
« less
- Award ID(s):
- 2147631
- NSF-PAR ID:
- 10454218
- Date Published:
- Journal Name:
- 2023 IEEE International Conference on Robotics and Automation (ICRA)
- Page Range / eLocation ID:
- 7663 to 7669
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We address the problem of learning the legitimacy of other agents in a multiagent network when an unknown subset is comprised of malicious actors. We specifically derive results for the case of directed graphs and where stochastic side information, or observations of trust, is available. We refer to this as “learning trust” since agents must identify which neighbors in the network are reliable, and we derive a protocol to achieve this. We also provide analytical results showing that under this protocol i) agents can learn the legitimacy of all other agents almost surely, and that ii) the opinions of the agents converge in mean to the true legitimacy of all other agents in the network. Lastly, we provide numerical studies showing that our convergence results hold in practice for various network topologies and variations in the number of malicious agents in the network. Keywords: Multiagent systems, adversarial learning, directed graphs, networked systemsmore » « less
-
Applications in environmental monitoring, surveillance and patrolling typically require a network of mobile agents to collectively gain information regarding the state of a static or dynamical process evolving over a region. However, these networks of mobile agents also introduce various challenges, including intermittent observations of the dynamical process, loss of communication links due to mobility and packet drops, and the potential for malicious or faulty behavior by some of the agents. The main contribution of this paper is the development of resilient, fully-distributed, and provably correct state estimation algorithms that simultaneously account for each of the above considerations, and in turn, offer a general framework for reasoning about state estimation problems in dynamic, failure-prone and adversarial environments. Specifically, we develop a simple switched linear observer for dealing with the issue of time-varying measurement models, and resilient filtering techniques for dealing with worst-case adversarial behavior subject to time-varying communication patterns among the agents. Our approach considers both communication patterns that recur in a deterministic manner, and patterns that are induced by random packet drops. For each scenario, we identify conditions on the dynamical system, the patrols, the nominal communication network topology, and the failure models that guarantee applicability of our proposed techniques. Finally, we complement our theoretical results with detailed simulations that illustrate the efficacy of our algorithms in the presence of the technical challenges described above.more » « less
-
This paper compares different distributed control approaches that enable a team of robots search for and track an unknown number of targets. The robots are equipped with sensors which have limited field of view (FoV) and are required to explore the environment. The team uses a distributed formulation of the Probability Hypothesis Density (PHD) filter to estimate the number and the position of the targets. The resulting target estimate is used to select the future search locations for each robot. This paper compares Lloyd’s algorithm, a traditional method for distributed search, with two typical stochastic optimization methods, Particle Swarm Optimization (PSO) and Simulated Annealing (SA). PSO and SA are traditionally used to find a single global maximum, therefore this paper describes novel formulations of PSO and SA to solve the problem of multi-target tracking. These new methods more effectively trade off between exploration and exploitation. Simulations demonstrate that the use of these stochastic optimization techniques improves coverage of the search space and reduces the error in the target estimates compared to the baseline approach.more » « less
-
null (Ed.)We consider the problem of fault-tolerant parallel search on an infinite line by n robots. Starting from the origin, the robots are required to find a target at an unknown location. The robots can move with maximum speed 1 and can communicate wirelessly among themselves. However, among the n robots, there are f robots that exhibit byzantine faults. A faulty robot can fail to report the target even after reaching it, or it can make malicious claims about having found the target when in fact it has not. Given the presence of such faulty robots, the search for the target can only be concluded when the non-faulty robots have sufficient evidence that the target has been found. We aim to design algorithms that minimize the value of S_d(n, f), the time to find a target at a (unknown) distance d from the origin by n robots among which f are faulty. We give several different algorithms whose running time depends on the ratio f/n, the density of faulty robots, and also prove lower bounds. Our algorithms are optimal for some densities of faulty robots.more » « less
