Enhancing Security in Multirobot Systems Through Co-Observation Planning, Reachability Analysis, and Network Flow

We address security challenges in multi-robot systems (MRS) where adversaries may compromise robots to gain unauthorized physical access to forbidden regions. We introduce a security mechanism based on reachability constraints and co-observations between robots. The mechanism guarantees that malicious trajectory deviations toward forbidden regions become physically detectable, as compromised robots must violate scheduled co observations. We first incorporate these mechanisms directly as constraints in a multi-robot optimal planning formulation, where we use ellipsoidal over-approximations of reachability regions for intersection checking and gradient computation. To address feasibility and optimality limitations of this naive formulation, we introduce the notion of sub-teams, cohesive units that replace individual robots along each trajectory. This enables cross-trajectory co-observations, where redundant robots switch between trajectories to secure multiple sub-teams without modifying the original plans. We formulate this cross-trajectory planning problem as a network-flow vertex path coverage problem on the checkpoint graph derived from unsecured MRS trajectories, while preserving the same security guarantees against plan deviation attacks. Simulations demonstrate the effectiveness and robustness of the proposed algorithm in strengthening the security of multi-robot systems under adversarial threats.