Responsable(s): Nicolas Hanusse et Cyril Gavoille
Tél.: 05.56.84.26.04 / 05.56.84.69.16
e-mail: hanusse@labri.fr / gavoille@labri.fr
Web: http://www.labri.fr/~gavoille
Equipe de recherche: Combinatoire et algorithmique : Graphes et Applications
Titre du sujet: Algorithmes d'explorations pour agents mobiles

Présentation: Un agent mobile est un programme circulant dans un
réseau et ayant la capacité de s'exécuter quand il arrive dans un
noeud du réseaux. L'utilisation d'agents mobiles a de multiple
applications : mise-à-jour automatique des tables de routage,
recherche de sites et collecte d'informations ("crawler"),
apprentissage d'un environnement inconnu (déplacement de robots), etc.

L'objet de cette thèse est l'étude théorique des problèmes que l'on
peut résoudre à l'aide d'agents mobiles dans les réseaux. En
particulier il s'agira de proposer des algorithmes "efficaces" pour la
recherche d'une information par un ou plusieurs agents dans un réseau
dont certain noeuds, appelés menteurs, routent l'agent dans une
mauvaise direction. Le terme "efficace" signifie que l'algorithme doit
optimiser plusieurs paramètres comme : le temps que met un agent à
trouver l'information, la quantité de mémoire maximal dont dispose un
agent, la possibilité de faire des choix aléatoires, etc.

Mots clés: algorithmique, algorithmes distribués, théorie des graphes,
routage, agent mobile

Références:

[1] "The power of a pebble: Exploring and mapping directed graphs" de
M. A.  Bender, A. Fernandez, D. Ron A. Sahai, and S. Vadhan,
Proc. Annual Symposium on Foundations of Computer Science, 1998.

[2] "The power of team exploration: Two robots can learn unlabeled
directed graphs", de M. Bender and D. Slonim. In Proceedings of the
Thirty Fifth Annual Symposium on Foundations of Computer Science, pp
75--85, 1994.

[3] "Exploring Unknown Environments", Albers et Henzinger, SIAM
Journal of Computing, Vol 29, num 4, pp 1664-1188

Commentaires: