Quel est le nombre optimal de robots pour explorer un anneau hautement dynamique ?
Abstract
Dans cet article, nous nous intéressons à la coordination algorithmique d'une cohorte de robots mobiles. Ces robots sont autonomes, uniformes, anonymes, capables de percevoir leur environnement, mais pas de communiquer. Ils évoluent de manière synchrone dans un environnement fini et discret représenté par un graphe. Nous supposons que cet environnement est un anneau hautement dynamique, c'est-à-dire un anneau dont les arêtes peuvent apparaître et disparaître de manière imprévisible sans aucune hypothèse de récurrence, de stabilité ou de périodicité à travers le temps mais avec une hypothèse de connexité temporelle minimale à la résolution du problème. Nous nous intéressons en particulier au problème de l'exploration perpétuelle de ce type de graphe, problème dans lequel chaque nœud de l'anneau doit être infiniment souvent visité par un robot. Notre contribution est la caractérisation exhaustive du nombre de robots nécessaires et suffisants pour résoudre ce problème en fonction de la taille de l'anneau.
Origin : Files produced by the author(s)
Loading...