Resiliency In Robot Formations With Non-Cooperative Robots

Consensus algorithms are fundamental for distributed decision-making in robotics. However, these algorithms usually assume the ability to communicate without considering the possibility of a malicious or malfunctioning robot that may communicate false or incorrect in- formation. The literature proposes methods that mitigate the effect of these non-cooperative robots and ensure convergence of the consensus, but require the graph of the communication network to satisfy a property known as r-robustness. Verifying the r-robustness of a given graph has been shown to be an coNP-complete problem, and the methods to construct graphs satisfying a desired r-robustness are limited. Furthermore, achieving formations of robots satisfying this graph-theoretic property has not been addressed thoroughly in the literature. The only existing solution is based on increasing the algebraic connectivity to a minimum value, which in turn tends to cluster the robots, reducing the applicability of such method to general formations. In this thesis, we address the problem of developing methods to systematically build graphs that, by design, satisfy the desired r-robustness. Then, we propose methods to arrange robots in formations whose associated communication graph satisfy the desired r-robustness. By using an underlying lattice structure for the formation, we can calculate a sufficient communication range to ensure resilience. Finally, we propose control laws that drive robots to self-organize into formations with the desired r-robust communication graphs. The results presented in this thesis allow us to obtain formations of robots that are resilient in the use of consensus algorithms to effects of non-cooperative robots, and can be adapted to the number of robots available, the communication capabilities of the robots, and obstacles or other environmental challenges.