Adaptive Malicious Robot Detection in Dynamic Topologies

We consider a class of problems where robots gather observations of each other to assess the legitimacy of their peers. Previous works propose accurate detection of malicious robots when robots are able to extract observations of each other for a long enough time. However, they often consider static networks where the set of neighbors a robot observes remains the same. Mobile robots experience a dynamic set of neighbors as they move, making the acquisition of adequate observations more difficult. We design a stochastic policy that enables the robots to periodically gather observations of every other robot, while simultaneously satisfying a desired robot distribution over an environment modeled by sites. We show that with this policy, any pre-existing or new malicious robot in the network will be detected in a finite amount of time, which we minimize and also characterize. We derive bounds on the time needed to obtain the desired number of observations for a given topological map and validate these bounds in simulation. We also show and verify in a hardware experiment that the team is able to successfully detect malicious robots, and thus estimate the true distribution of cooperative robots per site, in order to converge to the desired robot distribution over sites.