Proseminar: Suchen, Verfolgen und Entkommen (Search and Pursuit-Evasion Games)
Prof. Dr. Folkmar Bornemann,
Sommersemester 2011
Material
Literatur und Arbeitsanweisung für alle Themen (passwortgeschützt)
Termine
Di, 14:15-15:45, Raum MI 02.08.011
Datum |
Name |
Thema |
03.5. |
S.O. |
Chasing Pirates |
12.5. (Do!) |
D.A. |
Hathaway's Circular Pursuit Problem |
17.5. |
N.C. |
Rado's Lion and Man |
31.5. |
C.K. |
Capture Pursuit on Unbounded Domains |
07.6. |
C.B. |
Three Bugs on a Triangle |
21.6. |
L.Z. |
Mathematical Treasure Hunting |
28.6. |
F.A. |
Bellman's Linear Search Problem |
19.7. |
D.L. |
Princess and Monster |
26.7. |
I.S. |
Swimming in a Fog & Lady in the Lake |
Inhalt
Anhand elementarer Beispiele wollen wir Such- und Verfolgungsspiele studieren,
eine besonders anschauliche Problemklasse aus der faszinierenden Welt der
dynamischen Spiele. Diese "Spiele" modellieren Konflikte, in denen zwei Gegner
("Spieler") Strategien für Bewegungsabläufe suchen, um ihre gegensätzlichen Ziele
zu erreichen; Anwendungen findet man in Ingenieurwissenschaften, Ökonomie oder
Biologie zuhauf (wobei ich jedoch nicht verschweigen möchte, dass die
Theorie ursprünglich ein Kind des Kalten Krieges war und militärische
Anwendungen lange Zeit dominierten). Wie in der Spieltheorie weit verbreitet,
tragen die Modellprobleme einprägsame Namen, welche auf prägnante und meist
makabre "Parabeln" eines Konflikts verweisen:
So geht es bei "Löwe und Mann" um die Frage, ob ein (punktförmiger) Löwe eine
Strategie besitzt, um einen ihm in einer Arena zum Fraß vorgeworfenen (ebenfalls
punktförmigen) Mann gleicher Maximalgeschwindigkeit in endlicher Zeit zu erlegen.
Dieses "Spiel" wurde zwar bereits um 1925 von Richard Rado erfunden, aber die lange
von vielen Mathematikern als "offensichtlich" angesehene "Lösung" stellte sich
erst 1953 durch ein überraschendes Argument von Abram Besicovitch als völlig falsch
heraus. (Bitte nicht sofort googeln, sondern erst einmal selbst darüber nachdenken!)
Die "Lady im See" muss sich
vor einem Verfolger ans Ufer retten, der als Nichtschwimmer
nur dort entlanglaufen kann; "Prinzessin und Monster" sind zwar körperlich ausgedehnt,
aber die Jagd findet in einem völlig abgedunkelten Raum statt; der (ausgedehnte)
"mordlustige Chauffeur" jagt hingegen ein langsameres Opfer, das dafür aber anders
als sein durch den minimalen Wendekreisradius des Autos beschränkter Verfolger
jederzeit abrupt die Richtung ändern kann.
Methodisch benötigen wir neben elementarer Analysis (ganz einfache
Differentialgleichungen) und geometrischen Überlegungen zur Beschreibung der Kinematik
(nein, dazu braucht man wirklich keine Physikkenntnisse, es geht nur darum, wo die
Spieler sich wann aufhalten und in welche Richtung sie sich bewegen) etwas elementare
Wahrscheinlichkeitstheorie zur Analyse randomisierter Strategien (die bei
unvollständiger Information wie etwa im Fall des Suchens und Versteckens wichtig werden).
Ziele
In der Rolle des Vortragenden sollen Sie lernen, sich anhand von englischen
Fachtexten in einen mathematischen Sachverhalt einzuarbeiten, die wesentlichen Begriffe
und Argumentationslinien herauszuarbeiten, dabei die interessanten Ideen von der
uninteressanten Routine zu trennen, und schließlich Ihren Kommilitonen den Sachverhalt
auch noch nachvollziehbar
an der Tafel zu erläutern. (Zum Thema
Wie halte ich einen Seminarvortrag? 
gibt es ein paar sehr empfehlenswerte Handlungsanweisungen von Manfred
Lehn aus Mainz.) Es geht in diesem Proseminar ausdrücklich
nicht um eine aufwändig
gestaltete Powerpoint- und/oder Latex-Präsentationen mit dem Beamer; das Handout darf
auch handschriftlich erstellt werden.
In der Rolle des Zuhörers sollen Sie üben,
mathematische Vorträge nicht nur zu ertragen und abzusitzen, sondern aktiv mitzudenken
und gemeinsam über die neuen Sachverhalte, Begriffe, Ideen und Argumentationslinien
wissenschaftlich zu diskutieren.
Ablauf
Jeder Teilnehmer erhält Material für einen 75-minütigen Vortrag; ich erwarte von den
Zuhörern pro Vortragstermin eine rege Diskussion von wenigstens 15 Minuten Dauer.
Spätestens 14 Tage vor dem Vortragstermin
muss eine Besprechung der Inhalte, Auswahl
und des Vortragsablaufs mit mir stattfinden.
Literatur
ausgewählte Originalarbeiten sowie
begleitend:
- Paul Nahin: Chases and Escapes - The Mathematics of Pursuit and Evasion, Princeton University Press 2007
und vertiefend:
- Steve Alpern, Shmuel Gal: The Theory of Search Games and Rendeszvous, Kluwer Academic Publishers 2003
- Tamer Basar, Geert Jan Olsder: Dynamic Noncooperative Game Theory, Society of Industrial and Applied Mathematics 1999