Approche asynchrone dans le plan : un algorithme déterministe polynomial

Overview & Synopsis

Nous étudions la tâche de l'approche entre deux agents mobiles ayant la même portée de vision limitée et se déplaçant de façon asynchrone dans le plan. En partant de positions initiales quelconques, cette tâche consiste à les amener au moyen d'un algorithme déterministe à portée de vision l'un de l'autre en un temps fini. Ils sont autonomes et ne peuvent pas communiquer entre eux. Ils disposent cependant d'identifiants distincts et d'une boussole leur indiquant les points cardinaux. Chaque agent ne connaît que son identifiant. En particulier, il ignore l'identifiant et la position initiale de l'autre agent. Un adversaire choisit les identifiants et les positions initiales des deux agents dans le plan et modifie à volonté la vitesse à laquelle chacun se déplace. Le coût d'une exécution complète d'un algorithme pour cette tâche est la somme des distances parcourues par les deux agents jusqu'à accomplir l'approche. Dans ces conditions, certains algorithmes déterministes résolvent cette tâche avec un coût exponentiel en fonction de la distance initiale ∆ séparant les deux robots et de la longueur des identifiants. D'autres nécessitent que chaque agent connaisse sa position de départ dans un système de coordonnées commun ; d'autres encore fonctionnent avec un adversaire plus faible. Ce papier présente un algorithme déterministe pour la tâche de l'approche dont le coût est polynomial en fonction de ∆ et de la longueur (de la représentation binaire) du plus petit identifiant.