Exploration optimale d'un anneau par des agents mobiles

Lemieux, Alexandre (2017). Exploration optimale d'un anneau par des agents mobiles. Mémoire. Gatineau, Université du Québec en Outaouais, Département d'informatique et d'ingénierie, 91 p.

Prévisualisation

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

Résumé

Des agents mobiles, aussi appelés robots, débutant à des positions distinctes sur un anneau, doivent parcourir tous les points de ce dernier. Dans la littérature, ce type de problèmes est appelé exploration. Dans les différents cas explorés ici, les agents se déplacent tous à la même vitesse. Nous cherchons un mouvement des agents qui complète l’exploration de l’anneau dans un temps minimal. Nous démontrons d’abord la solution pour deux agents mobiles.
Pour n agents, nous faisons l’observation cruciale qu’un programme d’exploration optimal peut être converti en un programme où un des agents se déplace dans une seule direction. Nous nommons ce déplacement direct. Cette observation nous permet d’utiliser l’algorithme d’exploration sur un segment proposé par Stec [211, résultant en un algorithme d’exploration s’exécutant en 0(n3).
Nous avons par contre été en mesure de développer un algorithme original permettant à un ensemble d’agents d’explorer l’anneau en temps 0(n2). Nous prouvons l’exactitude et l’optimalité de cet algorithme.
L’algorithme a été implanté et une animation contrôlée par l’utilisateur permettant de visualiser la solution a été rendue disponible en ligne.

Type de document:	Thèse (Mémoire)
Directeur de mémoire/thèse:	Czyzowicz, Jurek
Mots-clés libres:	Agent mobile; Robot; Anneau; Exploration
Départements et école, unités de recherche et services:	Informatique et ingénierie
Date de dépôt:	21 mars 2018 13:40
Dernière modification:	21 mars 2018 13:40
URI:	https://di.uqo.ca/id/eprint/970

Gestion Actions (Identification requise)

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