Conformal Koopman Certificates for Nonlinear Multi-Agent Consensus on Time-Evolving Graphs

Overview & Synopsis

Robot fleets must often agree on a shared value before they act, over wireless networks that change as the robots move. Their supervisor needs a deadline: the number of communication rounds after which the fleet has agreed with a stated probability. Today it comes from simulation plus a safety margin, with an open probability of being met. We certify it. Our method, conformal Koopman certification, rests on one observation: averaged over the random network changes, the expected behaviour of the fleet evolves linearly, for any nonlinearity of the agents. The decay rate of this linear evolution gives the shape of the deadline. One remaining constant is calibrated from 200 short test runs by conformal prediction, a statistical method that turns any predictor into a guarantee that holds with a user-chosen probability. The certified deadline holds for every agreement tolerance at once and for any error in the estimated rate. The same linear model predicts the value the fleet will agree on and certifies how much corruption of the exchanged messages the collective decision absorbs. For 60 simulated robots the certified deadline was met in all 500 test runs against a 90\% target and exceeded the slowest run by 16\%. The classical worst-case bound exceeds that run by more than 160 orders of magnitude, a linearised deadline is missed in up to 26\% of runs, and direct conformal calibration costs 80 times more simulation per tolerance.