|
Struktur
Vorlesungsfolien (2004)
Vorlesungsskript (2004)
International Planning Competitions
General Game Playing (Stanford)
General Game Playing (Dresden)
Vorlesungsteil Allgemeines Spiel
Literatur
|
Spezialvorlesung
WS 10/11: Handlungsplanung und Allgemeines Spiel
PD Dr. Stefan Edelkamp
Dipl.-Inform. Peter Kissmann
Termine: Mi 10-12, Do 10-12, Raum 1.50 (TZI, TAB, Fallturm 1)
Modul 602 (Algorithmen- und Komplexitätstheorie), 2+2 SWS, 6 ECTS
Thema
Die Vorlesung gibt einen Einblick in den aktuellen Forschungsstand
und neue Forschungsrichtungen in der Handlungsplanung und im Allgemeinen
Spiel.
Handlungsplanung
In der Vorlesung werden verschiedene Planungsformalismen
vorgestellt, ihre Komplexität untersucht und
Algorithmen zur Lösung des Planungsproblems besprochen.
Im klassischen, deterministischen Planen betrachten wir den
propositionalen STRIPS-Kalkül, ADL-Erweiterungen und
ihre Verarbeitung, numerisches, temporales Planen mit
Optimierungsfunktionen in PDDL2.1, sowie
Zeitfenster und abgeleitete Prädikate in PDDL2.2. Als Planungsverfahren
werden u.a. Planen in Graphen, Planen durch lokale Suche,
Planen durch heuristische Suche mit Musterdatenbanken, Planen als
aussagenlogisches Erfüllbarkeitsproblem und Planen mit BDDs beschrieben.
Für numerisches Planen wird die heuristische Suche erweitert und
für temporales Planen ein Scheduling-Ansatz besprochen, der
sequentiell in der Suche
erzeugte Pläne optimal parallelisiert.
Neben dem klassischen Planen werden Planungsansätze zum
nicht-deterministischen, konformanten und
wahrscheinlichkeitstheoretischen Planen besprochen, in denen
Pläne in Form von Zustands-Aktionspaaren dargestellt werden.
Wahrscheinlichkeitstheoretisches Planen erweist sich dabei als
besonders schwierig. Ein Zweig des nicht-deterministischen Planens
birgt eine enge Verbindung zum Zeipersonenspiel. Als
Planungsverfahren werden vorgestellt: schwaches, starkes und
konformantes Planen mit BDDs. Planen mit unvollständiger Information
durch heuristische Suche. Politik- oder Wertiteration zur Lösung
von MDP und POMDP Problemen mit und ohne ADDs.
Als Techniken zur
Vereinfachung von Planungsproblemen werden u.a. die Berechnung von
Invarianten für Planungsprobleme, die Symmetrieerkennung von
Objekttranspositionen und das Planen mit reduzierten Operatorlisten
besprochen.
Allgemeines Spiel (engl. general game playing, GGP)
Forschungszweig, in dem Spiele in einer problemunabhägigen
Beschreibungssprache formuliert werden und dazu aufgerufen wird,
Spieler zu konzipieren, die über eine geeignete Schnittstelle
gegen einen Menschen oder gegeneinander antreten.
Die Spiele sind endlich und terminale Zustände werden über
Auszahlungsvektoren mit Werten im Bereich {0,. . . ,100} beschriftet.
Algorithmen propagieren diese
Werte innerhalb des Suchbaumes möglicher Abspiele zu dem aktuellen
Spielzustand, um daraus eine gewinnversprechende Nachfolgerwahl zu ermöglichen.
Der heute wohl am weitesten verbreitete Beschreibungsformalismus GDL (Game
Description Language) ist eine logikbasierte Beschreibungssprache, die -
im Gegensatz zu PDDL, das häufig in der Handlungsplanung zum Einsatz kommt - auf dem Situationskalkül beruht und statische Definitionsblöcke, welche in
Datalog beschrieben werden, besitzt. Es gibt nationale und internationale Wettbewerbe, von
denen jener auf der amerikanischen KI-Konferenz AAAI am höchsten dotiert ist letzterer
ist sicherlich auch ein Grund für den Erfolg dieses Formalismus.
Das allgemeine Spiel wurde ursprünglich von der Logik-
Gruppe der Universität Stanford initiiert und gefördert; in Deutschland war in den letzten Jahren die Gruppe um Michael Thielscher an der gebend - dort findet sich auch ein Server, auf dem Spieler gegeneinander antreten können.
Neben einfachen Klassikern wie Nimm oder Tic-Tac-Toe liegen bereits Spiele
wie Schach, Dame oder Halma teils in vereinfachter, teils in vollständiger Spezifikation
vor, wobei es sich alich um deterministische, endliche Spiele mit vollständiger
Information handelt. Die Endlichkeit wird häufig über einen Zugzähler sichergestellt und
ein Spiel endet, wenn eine bestimmte Anzahl an Zügen durchgeführt wurde.
Erste erfolgreiche Implementierungen von Spielern wie etwa CLUNEPLAYER und
FLUXPLAYER verwenden Heuristiken basierend auf αβ-Pruning. Dabei können
Mehrpersonenspiele beispielsweise als Varianten des Zweipersonenspiels aufgefasst
werden, indem die Spieler in zwei Mannschaften unterteilt werden: Diejenigen, die
mit dem eigenen Spieler kooperieren (was sich etwa darin zeigt, dass sie die gleiche
Bewertung in sämtlichen Zielzuständen bekommen), und diejenigen, die gegen ihn spielen.
Ein weiterer aktueller Trend im allgemeinen Spiel ist der UCT Algorithmus (Upper Confidence Bounds Applied to Trees), bei dem nur ein Teil des Spielgraphen im Speicher gehalten wird und eine Einschätzung üer die Qualität einer Position durch zufällige Abspiele ermittelt wird. Die Sieger der letzten drei internationalen Meisterschaften haben
diesen Ansatz verfolgt und ihn für Mehrpersonenspiele erweitert.
Software
In der Vorlesung wird das Planungssystem GAMER zur
Fallstudie genutzt. Desweiteren werden
aktuelle Systeme vorgestellt. Als Beispiele
dienen Probleme aus den Planungs- und GGP-Wettbewerben.
Übung
Anstatt einer traditionellen Übung mit zu bearbeitbaren
Zetteln wird von den Studierenden begleitend durch die Vorlesung
schrittweise ein Handlungsplaner oder Allgemeiner Spieler
in Gruppenarbeit programmiert. Am Ende der Vorlesung findet
eine Präsentation / Wettbewerb statt.
Literatur
Zu der Vorlesung wird ein Skript
(evtl. in zwei Teilen) erstellt.
M. Ghallab, D. Nau, and P. Traverso. Automated Planning: Theory and Practice.
Morgan Kaufmann, 2004.
Weitere Resultate entspringen richtungsweisenden Veröffentlichungen
der letzten Jahre.
mehr...
|
|