Description
Date depot: 1 janvier 1900
Titre: Gathering with Byzantine Robots
Directeur de thèse:
Franck PETIT (LIP6)
Encadrant :
Yoann DIEUDONNÉ (MIS)
Encadrant :
Swan DUBOIS (LIP6)
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Systèmes et réseaux
Resumé:
Research in achieving coordination among {teams of mobile robots} is challenging and has great scientific and practical implications. Squads of mobile robots (drones, automatic vehicles, software agents, humanoid machines, swarms of micro or nano robots, etc.) are currently being utilized and are expected to be employed even more in the future, in various critical situations. Numerous potential applications exist for such multi-robot systems: environmental monitoring, large-scale construction, Intelligence activities, rescue operations, risky area surrounding or surveillance, and the exploration of awkward environments, to name only a few.
In any given environment, the ability for a team of robots to succeed in the accomplishment of assigned tasks greatly depends on the capabilities that the robots possess, namely, their moving abilities, their memory and computation capacities, their means of communication, and the quality and accuracy of their sensory organs. It is therefore important to design algorithms that need limited resources and capacities. Furthermore, the loss of one sensing capability by a single robot can easily lead to the failure of a mission for the entire cohort. So, it is also crucial to propose solutions that tolerate possible equipment dysfunctions (e.g. caused by attacks or failures) or leading to the complete lost of robots.
By weakening assumptions made on the robot capabilities in the design of solutions drastically reduces the possibility that equipment failures hamper the actions of robots. Indeed, considering that robots have no means of communication, failures of equipment such as radio transceiver does not make sense, the failure of the mass memory means nothing assuming oblivious robots, as well as dysfunctions of the geolocation system makes no sense assuming disoriented robots. In other words, the advantage of this model is that it includes almost all component failures, except its computing unit and its motion devices. There have been numerous work studying the minimal assumptions about robots for this problem over different graph topologies.
We consider the {gathering problem} which consists to make several robots to eventually meet together at a single point. We plan to study the feasibility of gathering by considering that some robots may be Byzantine, i.e., we consider that some robots have permanent odd behaviors, harmful for the mission of robots, and from the point of the algorithm, seen as a completely erratic behavior, random or even malicious. It can be for instance a permanent error of an element of the robot, or even a hostile intrusion in the robot program. Tolerate this type of failure is very relevant in the context of robots because it helps to deal with various scenarios ranging from hardware failure of a robot to the takeover of one or more robots by an adversaire.
The scientific agenda is mainly threefold:
-* Producing necessary and sufficient conditions to solve the gathering problem assuming Byzantine robots;
-* The design of distributed algorithms that meet these necessary and sufficient conditions in order to obtain optimal solutions (with respect to impossibility results);
-* The study of links between the gathering and other related problems.
Doctorant.e: Bouchard Sebastien