Wie finde ich meine Frau in einem Supermarkt?

27

Wenn sich zwei Personen in einem Labyrinth verirren, gibt es dann einen Algorithmus, mit dem beide sich finden können, ohne vorher vereinbart zu haben, welchen Algorithmus sie verwenden werden?

Ich denke, dass es einige Eigenschaften gibt, die dieser Algorithmus haben wird:

  • Jede Person muss in der Lage sein , um es Logik ableiten verwenden , die keine macht Annahmen über das, was die andere Person zu entscheiden, aber wie jede Person die andere in der gleichen Position kennt kann sie machen Abzüge über das, was der andere muss entscheiden werden.
  • Ein identischer Algorithmus muss von beiden Personen abgeleitet werden, da in ihren Situationen eine vollständige Symmetrie besteht (keine hat Kenntnisse über die Startposition der anderen und das Labyrinth hat eine feste Größe und wird von beiden vollständig abgebildet). Beachten Sie, dass der Algorithmus nicht deterministisch sein muss: Er darf randomisiert werden.
jl6
quelle
(Ein Supermarkt kann ein irreführendes Beispiel sein, da es eine halb beobachtbaren Austrittsfläche ist.) Nun, wenn beide ein Mittel haben ihren Weg in eine Art und Weise zu kennzeichnen , dass jeder kann sagen , selbst von anderen , sie zu verdreifachen Abständen umkehren könnten, Startprobleme bei der Begegnung mit eigenen .
Greybeard
7
Die logische Antwort ist, ihr Handy anzurufen;)
DavidPostill
2
Die Nicht-CS-Antwort lautet, zu einem Schelling-Punkt zu gehen . In einem Supermarkt ist dies beispielsweise der Kundendienst oder der Ausgang. Beachten Sie jedoch, dass Schelling-Punkte im menschlichen Leben oftmals weniger von der algorithmischen Analyse von Konnektivitätsmustern abhängen, als vielmehr von menschlichem Verhalten und Wissen. Die CS-Perspektive liefert also nicht wirklich viel Einsicht, wenn es um menschliche Agenten geht. Wollen Sie wirklich nach Menschen im wirklichen Leben fragen , oder möchten Sie eine mathematische Frage zu Roboteragenten in einer idealisierten Umgebung stellen?
DW

Antworten:

19

Dies wird als Rendezvous-Problem bezeichnet .

Wie im Artikel: Mobile Agent Rendezvous: Eine Umfrage erwähnt, ist dieses Problem ursprünglich von Alpern vorgeschlagen worden : Das Rendezvous-Suchproblem :

Zwei Astronauten landen auf einem kugelförmigen Körper, der viel größer ist als der Erfassungsradius (innerhalb dessen sie sich sehen können). Der Körper hat weder eine feste Orientierung im Raum noch eine Rotationsachse, so dass den Astronauten kein gemeinsamer Begriff von Position oder Richtung für die Koordination zur Verfügung steht. Wie sollten sich die beiden Astronauten bei einer vorgegebenen Laufgeschwindigkeit bewegen, um die erwartete Treffzeit T zu minimieren (bevor sie in den Erfassungsradius gelangen)?

In der Umfrage oben,

Kurzfassung: Die jüngsten Ergebnisse zum Problem des Rendezvous von mobilen Agenten in verteilten Netzwerken werden untersucht, wobei der Schwerpunkt auf den verschiedenen Ansätzen von Forschern der theoretischen Informatikgemeinschaft liegt.

Es behandelt sowohl "Asymmetrisches Rendezvous" (in Abschnitt 4) als auch "Symmetrisches Rendezvous" (in Abschnitt 5).


Für ein symmetrisches Rendezvous zeigt das Papier von Alpern:

Es wird gezeigt, wie Symmetrien in der Suchregion den Prozess behindern können, indem sie eine Koordination verhindern, die auf Konzepten wie Norden oder im Uhrzeigersinn basiert.

Hengxin
quelle
Als so gut bezeichnet, weist mich das auf das jeweilige Fachgebiet hin. Wenn ich diese Umfrage richtig lese, ist noch nicht bekannt, ob es eine optimale Lösung für ein symmetrisches Rendezvous gibt.
jl6
-1

Tatsächlich reicht jedes im Voraus festgelegte Schema aus.

Beispielsweise:

  1. Biegen Sie immer links ab
  2. Wenn Sie sich in einer Sackgasse befinden, biegen Sie rechts ab
  3. Man muss die doppelte (vorab festgelegte) Geschwindigkeit des anderen laufen (oder in zahlen-theoretischen Begriffen sollten die Geschwindigkeiten der beiden Agenten relativ prim oder im Allgemeinen linear unabhängig sein).

Oder noch einfacher

  1. Ein Agent bleibt am selben Ort
  2. Während der andere ein konsistentes Schema verwendet, um das Labyrinth zu erkunden (z. B. mit einem Ariadne-Thread-Ansatz ).
  3. Irgendwann, in endlicher Zeit, werden sie sich treffen.

Dieses Schema garantiert, dass die Leute sich irgendwann treffen (aber es kann einige Zeit dauern)

Warum? Denn das Schema ist für beide gleich und führt auch nicht zu einer Sackgasse. Da das Labyrinth endlich ist und verbunden ist, werden sie sich nach einer endlichen Zeit treffen.

Wenn das Schema nicht konsistent ist, gibt es keine Garantie dafür, dass es erfüllt wird, da dies zu geschlossenen Kreisläufen führen kann.

Wenn sie die gleiche Geschwindigkeit haben, ist es abhängig von der Architektur des Labyrinths, z. B. eines zyklischen Labyrinths, möglich, dass sie sich immer an antidiametrischen Punkten des Labyrinths befinden und sich daher niemals treffen, obwohl das Schema konsistent ist.

Aus dem oben Gesagten geht klar hervor, dass das Schema vorab festgelegt werden muss, aber jedes konsistente vorab festgelegte Schema reicht aus.

Ansonsten kann man sich auf probabilistische Analysen verlassen und daraus schließen, dass sie mit großer Wahrscheinlichkeit aufeinandertreffen werden, aber diese Wahrscheinlichkeit ist nicht eine (dh unter allen Umständen).

Man kann auch die Umkehrung des Rendezvous-Problems betrachten , das Vermeidungsproblem, bei dem es das Ziel ist, dass sich die Agenten immer gegenseitig meiden .

Die Lösung für das Vermeidungsproblem besteht darin, dass sich die Agenten genau widerspiegeln. Das heißt, dass das, was ein Agent dem anderen antut, die Reflexion dessen tun sollte. Da das Vermeidungsproblem auch eine Lösung hat , ist klar, dass Strategien für das Rendezvous-Problem, die zum Reflexionsverhalten der Agenten führen können, keine Lösung garantieren können.

Man kann sagen, dass die Strategie für das Vermeidungsproblem Parallelisierung (dh maximaler Divergenzpunkt) ist, während die Strategie für das Rendezvous-Problem Orthogonalität (dh am wenigsten konvergenter Punkt) ist.

Die obige Analyse kann in einen zufälligen Algorithmus umgewandelt werden, der keine vorher festgelegten Rollen für die Agenten übernimmt, wie z.

  1. Jeder Agent wirft eine Münze auf die zu wählende Rolle (z. B. an Ort und Stelle bleiben oder das Labyrinth erkunden)
  2. Dann gehen sie wie oben beschrieben vor.

Dies führt im Durchschnitt zu Treffen, ist jedoch nicht in allen Fällen garantiert.

Wenn wir davon ausgehen, dass die Agenten Spuren hinterlassen können , zB Beschriftungen ihrer (aktuellen) Richtung und Geschwindigkeit. Der andere Agent kann diese Traces dann als Information verwenden, um sowohl seine eigene Richtung als auch seine eigene Geschwindigkeit anzupassen (siehe unten).

Diese Art von Problem ist ein Beispiel für eine globale Optimierung, bei der nur lokale Informationen verwendet werden . Oder mit anderen Worten, eine Möglichkeit, globale Einschränkungen auf lokale Einschränkungen abzubilden . Dieses allgemeinere Problem (das das Rendezvous-Problem zusammenfasst) wird in diesem math.se-Beitrag (und den darin enthaltenen Verweisen) "Methoden zum Übersetzen globaler Einschränkungen in lokale Einschränkungen" behandelt.

Nikos M.
quelle
"Ein Agent bleibt am selben Ort" verletzt die von OP gewünschte Symmetrieeigenschaft. wobei beide Agenten dieselbe Strategie verfolgen.
AndyG
@AndyG, ja, dieser Teil wird unten mit einer Reihe von Ansätzen beantwortet. Außerdem wird darauf hingewiesen, dass die Lösung in diesem Fall nicht garantiert ist
Nikos M.
1
@NikosM. Ich glaube nicht, dass irgendeine Art von Synchronisation notwendig ist. Man kann dieses Problem als Verfolgungshinterziehungsszenario modellieren, bei dem beide Agenten die anderen als Ausweicher betrachten. Es gibt probabilistische Ansätze, um dieses Problem zu lösen, und in einer 3D-Umgebung kann man die minimale Anzahl von Verfolgern anzeigen, die erforderlich sind, um eine Erfassung zu gewährleisten.
AndyG
1
"Immer links abbiegen" funktioniert nicht. Angenommen, Sie befinden sich in Gang 2 und Ihre Frau befindet sich in Gang 5. Sie werden die Gänge 2 und 3 (oder 1 und 2, je nachdem, in welche Richtung Sie sich ursprünglich befanden) für immer auf- und abgehen, und Ihre Frau wird auf- und abgehen nach unten 5 und 6 (oder 4 und 5). Wenn Sie sich in einem kleinen Supermarkt befinden, dessen Konnektivitätsdiagramm ein Fahrrad ist, können Sie auch für immer in die gleiche Richtung und mit der gleichen Geschwindigkeit um das Fahrrad laufen.
David Richerby
1
"Ein Agent bleibt am selben Ort, der andere erledigt etwas anderes" funktioniert nicht, da sich beide Agenten möglicherweise dafür entscheiden, still zu bleiben und für immer auf den anderen zu warten. Wenn die Agenten kommunizieren können, um zu vereinbaren, wer stehen bleibt, können sie stattdessen auch mitteilen, dass einer von ihnen bei den Bananen steht.
David Richerby