Resilience of a synchronized multi-agent system

摘要

Fault tolerance is increasingly important for unmanned autonomous vehicles. For example, in a multi robot system the agents need the ability to effectively detect and tolerate internal failures in order to continue performing their tasks without the need for immediate human intervention. The system must react to unplanned events in order to optimize the task allocation between the robots. In a broad sense, the resilience of a system can be defined as the ability to maintain or recover a stable state when subject to disturbance and it is related to the concept of robustness in industrial systems. In this paper, we study the resilience in a synchronized multi-robot system stated as follows:Consider a team of $n$ (ground or aerial) robots each moving along predetermined periodic closed trajectories. Each of the agents needs to communicate informationabout its operation to other agents, but the communication links have a limited range. Hence, when two agents are within communication range, a communication link is established, and information is exchanged. Thus, two neighbors are synchronized if they visit the communication link at the same time and a multi-robot system is called synchronized if each pair of neighbors is synchronized. If a set of robots left the system, then some trajectories has no robots. In these cases, when an alive robot detects no neighboring robot then it pass to this neighboring trajectory to assume the unattended task. In this framework, a fault-tolerance measure is introduced: the resilience of the system is the largest number of robots that can fail while executing the global task. Interesting combinatorial properties of the resilience are showed that allow to know its value for some usual scenarios.