Spatial Consensus-Prevention in Robotic Swarms

In this work, we define the consensus-prevention problem, which examines the canonical swarm robotic consensus problem from an adversarial point of view: how (if at all) is it possible to lead a swarm into a disagreement, that is, prevent them from reaching an agreement. We focus on consensus-prevention in physically grounded tasks, concentrating on influencing the direction of movement of a flocking swarm and guaranteeing that the swarm will never converge to the same direction by the use of external, predefined agents, referred to as diverting agents. We formally define the notion of disagreement within a flock, and propose a way of measuring it. We show a correlation between the consensus-prevention problem and the coalition formation problem, whose players aim at maximizing the disagreement measure. While the general problem of optimizing disagreement between flocking agents is NP-hard, we focus on a case which is solvable in polynomial time, using a variant of the graph clustering problem where the clusters constitute the desired coalitions. This allows us to determine both the number of coalitions that optimize disagreement, and the behavior of the diverting agents for a given number of coalitions that will lead to optimal disagreement. Finally, we demonstrate in simulation the impact of the number of diverting agents on the disagreement measure in different scenarios, and discuss the limitations of the diverting agents in dynamic settings.