Formations for Resilient Robot Teams

Abstract

All cooperative control algorithms for robot teams assume the ability to communicate without considering the possibility of a malicious or malfunctioning robot that may either communicate false information or take wrong actions. This paper addresses the development of formations that enable resilience, the ability to achieve consensus and to cooperate in the presence of malicious or malfunctioning robots. Specifically, we use the notion of robust graphs to build resilient teams, and focus on the problem of designing robot formations with communication graphs (each edge models a bi-directional communication link) that are robust. We present algorithms to build robust graphs. Given a set of robots and the maximum number of malicious or malfunctioning robots, we are able to (a) state if it is possible to build a resilient team; (b) say what the proximity relationships that enable communication ought to be; (c) construct elemental resilient graphs; and (d) develop a framework for composing resilient teams to build larger resilient teams. We illustrate these algorithms by constructing resilient robot formations in the plane.