Comment trouver ma femme dans un supermarché?

Si deux personnes sont perdues dans un labyrinthe, existe-t-il un algorithme qu'elles peuvent toutes deux utiliser pour se retrouver sans avoir préalablement convenu de l'algorithme qu'elles utiliseront?

Je pense que cet algorithme aura certaines caractéristiques:

• Chaque personne doit pouvoir le dériver en utilisant une logique qui ne fait aucune hypothèse sur ce que l'autre personne décide, mais comme chaque personne sait que l'autre est dans la même position, elle peut faire des déductions sur ce que l'autre doit décider.
• Un algorithme identique doit être dérivé par les deux personnes car il y a une symétrie totale dans leurs situations (aucun n'a aucune connaissance de la position de départ de l'autre, et le labyrinthe est de taille fixe et entièrement mappé par les deux). Notez que l'algorithme n'a pas besoin d'être déterministe: il peut être randomisé.

C'est ce qu'on appelle un problème de rendez-vous .

Comme le papier: Mobile Agent Rendezvous: A Survey mentionné, ce problème est proposé par Alpern: The Rendezvous Search Problem :

Deux astronautes atterrissent sur un corps sphérique beaucoup plus grand que le rayon de détection (dans lequel ils peuvent se voir). Le corps n'a pas d'orientation fixe dans l'espace, ni d'axe de rotation, de sorte qu'aucune notion commune de position ou de direction n'est disponible pour la coordination des astronautes. Compte tenu des vitesses de marche des unités pour les deux astronautes, comment devraient-ils se déplacer afin de minimiser le temps de rencontre T attendu (avant de se trouver dans le rayon de détection)?

Dans le document d'enquête ci-dessus,

Résumé: Les résultats récents sur le problème du rendez-vous des agents mobiles sur les réseaux distribués sont étudiés en mettant l'accent sur les différentes approches adoptées par les chercheurs de la communauté théorique de l'informatique.

Il couvre à la fois "Rendez-vous asymétrique" (dans la section 4) et "Rendez-vous symétrique" (dans la section 5).

Pour un rendez-vous symétrique, l'article d'Alpern montre:

Il montre comment les symétries dans la région de recherche peuvent entraver le processus en empêchant la coordination basée sur des concepts tels que le nord ou dans le sens horaire.

En fait, tout schéma pré-arrangé cohérent fera l'affaire.

Par exemple:

1. Tournez toujours à gauche
2. Si vous êtes dans une impasse, revenez au virage précédent et tournez à droite
3. L'un devra marcher deux fois la vitesse (pré-arrangée) de l'autre (ou en termes plus théoriques des nombres, les vitesses des deux agents devraient être relativement premières, ou plus généralement être linéairement indépendantes).

Ou encore plus simple

1. Un agent reste au même endroit
2. Alors que l'autre utilise un schéma cohérent pour explorer le labyrinthe (par exemple en utilisant une approche de fil d'Ariane ).
3. Finalement, en temps limité, ils se rencontreront.

Ce programme garantira que les gens se rencontreront éventuellement (mais cela pourrait prendre un certain temps)

Pourquoi? Parce que le schéma est cohérent pour les deux et ne conduit pas non plus à une impasse. Donc, puisque le labyrinthe est fini et est connecté, après un temps fini, ils se rencontreront.

Si le schéma n'est pas cohérent, il n'y a aucune garantie qu'ils se rencontreront car ils peuvent entraîner des boucles fermées.

S'ils ont la même vitesse, puis en fonction de l'architecture du labyrinthe, par exemple un labyrinthe cyclique, il est possible qu'ils puissent toujours être aux points anti-diamétraux du labyrinthe, donc ne jamais se rencontrer, même si le schéma est cohérent.

Il ressort clairement de ce qui précède que le schéma doit être pré-arrangé, mais tout schéma cohérent pré-arrangé fera l'affaire.

Sinon, on peut s'appuyer sur une analyse probabiliste et en déduire qu'avec une grande probabilité, ils se rencontreront, mais cette probabilité n'est pas une (c'est-à-dire dans tous les cas).

On peut aussi considérer l'inverse du problème des rendez - vous , le problème de l' évitement où l'objectif est que les agents s'évitent toujours .

La solution au problème d'évitement est que les agents se reflètent exactement. Ce qui signifie que ce qu'un agent fait à l'autre devrait refléter cela. Puisque le problème d'évitement a également une solution , il est clair que les stratégies pour le problème de rendez-vous qui peuvent conduire au comportement de réflexion des agents ne peuvent pas garantir la solution.

On peut dire que la stratégie pour le problème d'évitement est la parallélisation (ie point divergent maximum) alors que la stratégie pour le problème de rendez-vous est l' orthogonalité (ie point le moins convergent)

L'analyse ci-dessus peut être transformée en un algorithme aléatoire qui n'assume pas de rôles pré-arrangés pour les agents, comme le suivant:

1. Chaque agent jette une pièce sur le rôle à choisir (par exemple, rester en place ou explorer le labyrinthe)
2. Ensuite, ils procèdent comme décrit ci-dessus.

Cela conduira en moyenne à des rencontres, mais n'est pas garanti dans tous les cas.

Si nous supposons que les agents peuvent laisser des traces , par exemple des étiquettes de leur direction (actuelle) et de leur vitesse. Ensuite, l'autre agent peut utiliser ces traces comme informations pour ajuster à la fois sa propre direction et sa vitesse (voir ci-dessous).

Ce type de problème est un exemple d' optimisation globale utilisant uniquement des informations locales . Ou, en d'autres termes, un moyen de faire correspondre les contraintes globales aux contraintes locales . Ce problème, plus général (qui subsume le problème des rendez-vous) est abordé dans cet article de math.se (et les références qu'il contient) "Méthodes pour traduire les contraintes globales en contraintes locales"