next up previous contents
Next: Computational Finance Up: Kombinatorische Optimierung Previous: Zusammenarbeit mit der Firma

Rendezvous-Suche

In vielen alltäglichen Situationen ist man mit dem Problem konfrontiert, eine andere Person in einer unübersichtlichen Umgebung zu treffen. Genaue Verabredungen helfen, Schwierigkeiten zu verkleinern, aber oft kann man keinen präzisen Ort und keine präzise Zeit vereinbaren, da man den eigenen späteren Aufenthaltsort zum Zeitpunkt der Verabredung noch nicht kennt. Szenarien dieser Art treten aber auch bei Rettungsaktionen auf, bei denen zumindest einer der Beteiligten nicht genau weiß, wo der andere sich gerade befindet. Probleme mit zwei oder mehr mobilen Personen (,,Spielern``) bezeichnet man als Rendezvous-Suche. Ziel ist es, optimale Protokolle zu entwickeln, die ein möglichst schnelles Zusammentreffen garantieren, bzw. die Wahrscheinlichkeit für ein Zusammentreffen maximieren.


  
Abbildung: Eine optimales Strategiepaar für eine begrenzte Gesamtstrecke
\begin{figure}
\begin{center}
\leavevmode
\epsfxsize=0.9 \columnwidth
\epsffile{mathopt1/limit.eps}\end{center}\end{figure}

In vergangenen Jahren gab es eine zunehmende Anzahl von Untersuchungen zur Rendezvous-Suche in eindimensionalen Szenarien, bei denen sich die beiden Spieler z.B. auf einer Strecke oder einem Kreis befinden. In Zusammenarbeit mit Prof. Edward Anderson (Sydney) gelang es uns, erstmals eine Reihe von Ergebnissen für zweidimensionale Rendezvous Probleme zu erzielen. Unterschiedliche Szenarien ergeben sich durch verschiedene Annahmen über die den Spielern zur Verfügung stehende Information. So kann der anfängliche Abstand bekannt sein, oder es kann eine gemeinsame Orientierung im Raum existieren. Für diese Szenarien gelang es uns, eine optimale Strategie zu finden, die sowohl den Erwartungswert bei zufälligem Ausgangspunkt minimiert, als auch bei begrenzter Gesamtstrecke beider Beteiligten die Wahrscheinlichkeit für ein Treffen maximiert. Für den Fall, daß sich die Spieler auf einem Gitter bewegen, fanden wir ebenfalls eine optimale Strategie, auch wenn die Anfangsorientierung zufällig ist. Schließlich gelang es uns, ein typisches Rettungsszenario zu lösen, bei dem einer der beiden Spieler (der ,,Retter``) die Anfangsposition und den Abstand des anderen Spielers (des ,, Verirrten``) kennt, während dieser nur die Anfangsdistanz des Retters kennt.


  
Abbildung: Eine optimale Trajektorie für das Rettungsszennario
\begin{figure}
\begin{center}
\leavevmode
\epsfxsize=\columnwidth
\epsffile{mathopt1/spiral.ps}\end{center}\end{figure}


next up previous contents
Next: Computational Finance Up: Kombinatorische Optimierung Previous: Zusammenarbeit mit der Firma
Webmaster<www@zpr.uni-koeln.de>
1999-07-28