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