Exploration problems using autonomous robots

Godon, Maxime (2018). Exploration problems using autonomous robots. Thèse. Gatineau, Université du Québec en Outaouais, Département d'informatique et d'ingénierie, 208 p.

Prévisualisation

PDF Télécharger (37MB) | Prévisualisation

Résumé

We introduce and study search problems for collections of mobile robots. Throughout our work, we consider cases where robots may experience various type of faults, which may hinder the progress of the algorithm and require novel ways to solve the problem. We first discuss the search and exploration problem in the Euclidian plane, where a group of k robots with various maximal speeds, among which up to f may be faulty, have to discover a target and gather at its location, using various communication models. We then discuss the problem of search for a non-adversarial, uncooperative robot on the cycle, based on various premisses regarding the information available to the robots. We also consider the evacuation problem on the disc in the presence of faulty robots. In the evacuation problem, the robot finding a target point (exit) on the boundary of the environment must communicate it to other robots, which then all need to move to the exit (evacuate). Finally, we consider the problem of exploring various types of graphs in the presence of time constraints : each node has to be visited before a certain moment in time for the algorithm to succeed. We discuss the complexity of the exploration, based on the number of robots, the presence or absence of faults, and the topology of the graph. For all problems, we introduce algorithms to solve the problem, and discuss their efficiency.

Type de document:	Thèse (Thèse)
Directeur de mémoire/thèse:	Czyzowicz, Jurek
Co-directeurs de mémoire/thèse:	Kranakis, Evangelos
Départements et école, unités de recherche et services:	Informatique et ingénierie
Date de dépôt:	24 juill. 2018 20:04
Dernière modification:	05 févr. 2020 20:36
URI:	https://di.uqo.ca/id/eprint/1005

Gestion Actions (Identification requise)

Dernière vérification avant le dépôt