Fault-resilient cooperation of autonomous mobile robots with unreliable compass sensors

Abstract

Continuous advances in technology have made possible the use of several robots in order to carry out a large variety of cooperative tasks that are dangerous or undesirable for humans to complete.These tasks include, surveillance, inspection of sites that are inaccessible to humans, e.g., tight spaces, hazardous environments or remote sites, and search and rescue tasks, such as rescuing human beings trapped under piles of debris in an earthquake disaster or searching for victims of a flood.Following this idea, we are interested in systems with no prior infrastructure (e.g., unlike Global Positioning System), where robots are deployed in adverse environments, and where they are required to cooperate and self-organize to build such an initial infrastructure.For instance, robots may need to exchange information on their states (positions, trajectories, orientation, etc.) to construct a complete configuration of the team in order to cooperate.However, robots may not initially agree on a common coordinate system.Therefore, providing a way for robots to agree on a common coordinate system is useful in exchanging geographical information, for instance.Subsequently, reaching agreement among these robots is one of the most essential issues in distributed robotic systems.Besides, as the number of robots increases in the system, the issue of resilience to failure becomes prominent.In this dissertation, we consider a system that consists of a group of mobile robots roaming in the two-dimensional plane.Each robot occupies a point in the plane, and is equipped with sensors to observe the positions of the other robots.Each robot proceeds by repeatedly (1) observing the environment, (2) computing a destination based on the observed positions of robots, and (3) moving toward the computed destination.Also, robots are unable to communicate directly, and can only interact by observing each others' positions.Finally, all robots execute the same deterministic algorithm, and they are oblivious (i.e., stateless), meaning that they can not remember their previous states, their previous actions or the previous positions of the other robots.In this model, we address the problem of coordination between these robots from a computational viewpoint, aiming to identify the fundamental limits of what autonomous mobile robots can do in the presence of unreliable sensors.In particular, we focus on a basic coordination problem, namely the gathering problem, where robots must selforganize, and meet at some location not determined in advance, and without the help