1
AG-Monien
Projektgruppe SEROSE
Selfish Routing in Sokoban Environments
(Eigennütziges Routen in Netzwerken)
PG-SEROSE AG Monien 4
Sokoban mit autonomen Arbeitern
• Transportbedarf gegeben durch Jobs
• Kosten für Arbeiter gegeben durch zurückgelegte Wege
• Netzwerk gegeben als Sokoban-Instanz
• Entgelte für Transport gegeben für jeden Job
PG-SEROSE AG Monien 5
Sokoban mit autonomen Arbeitern
• Arbeiter sind eigenständige Agenten, die ihre Laufrouten so planen, dass sie ihren Gewinn maximieren.
• Gewinne der Arbeiter sind auch vom Verhalten der anderen Arbeiter abhängig.
• Stabile Zustände eines Systems sind erreicht, wenn alle Arbeiter ihre Routen geplant haben und kein Arbeiter mehr seine Route ändern will.
PG-SEROSE AG Monien 8
Thema der Projektgruppe
Berechnung von stabilen bzw. approximativ stabilen Zuständen (approximativen Nash Equilibrien) und global optimalen Zuständen in Sokoban-Systemen mit autonomen Arbeitern
Nash Equilibria vs. Global optimale Transportwege
Anschauliche Vorstellung: Ein Spiel zwischen nicht kooperierenden Spielern (Arbeiter), die ihren
persönlichen Gewinn maximieren wollen.
PG-SEROSE AG Monien 9
SOKOBAN
Definitionen:
Push: Verschieben einer Box auf ein Nachbarfeld
Carry: Verschieben einer Box auf ein beliebiges Feld ohne zwischendurch eine andere Box zu bewegen
PG-SEROSE AG Monien 10
SOKOBAN: Geschichte
Erfunden in den 1980ern von Thinking Rabbit, Takarazuka, Japan.
Quasi-Standard Benchmark von 50 Instanzen (1984), geordnet nach der Schwierigkeit für Menschen, sie zu lösen.
Bsp: Kürzeste bekannte Lösung (1999):
674 pushes
PG-SEROSE AG Monien 11
Literatur/Löser
Joseph Culberson. SOKOBAN is PSPACE-complete. Proceedings in Informatics 4. Fun with Algorithms (E.Lodi,
L.Pagli, N.Santoro eds). Carleton Scientific 1999. Andreas Junghanns. Pushing the limits: New developements in Single-Agent Search. Phd Thesis, Edmonton, CAN, 1999.
Push-basierter IDA*-LöserDatenbanken für DeadlockwiedererkennungSchrankenberechnung über Maximum Bipartite Matching
Ken‘ichiro Takahashi: Löser von Thinking Rabbit
http://www.ic-net.or.jp/home/takaken/e/
xsokoban.lcs.mit.edu/cgi-bin/xsokoban/best-scores (?)
PG-SEROSE AG Monien 12
Ein eigener Löser
Carry-basiert Iterative Deepening DFS für non-goal carries Hashtabelle für Carryumstellungen Deadlockerkennung (Hashtabelle für
Wiedererkennung) Zielbereichsanalyse (in Kinderschuhen) Heuristische Bewertungsfunktion (Mobility) Erkennung statisch toter Felder
PG-SEROSE AG Monien 13
Deadlocks
Lösung:
101-139,
80-42,
60-59,
121-120
143-124
145+166
usw.
PG-SEROSE AG Monien 14
Deadlocks
Lösung:
101-139,
80-42,
60-59,
121-120
143-124
145+166
usw.
PG-SEROSE AG Monien 15
Deadlocks
Lösung:
101-139,
80-42,
60-59,
121-120
143-124
145+166
usw.
Warum nicht:
101-139,
121-120
143-124
145+166
usw.
PG-SEROSE AG Monien 17
Zielbereichsanalyse
Welche Zielfelder sollen zuerst besetzt werden ?
PG-SEROSE AG Monien 18
Zielbereichsanalyse
Diese Konfiguration ist nicht mehr lösbar !
Gründe für die Unlösbarkeit können außerhalb des Zielbereiches liegen !
PG-SEROSE AG Monien 19
Zielgerichtete Suche
Bekannte Lösung erfordert 7 stille Carries am Anfang.
Welche Carries ?
PG-SEROSE AG Monien 20
Zielgerichtete Suche
Lösung:
179-181163-18249-12567-6884-65122-103121-123138+248 usw.
PG-SEROSE AG Monien 21
Zielgerichtete Suche
Ziele:
138-Goal ?121-(nicht 121)!122-(nicht 122) !84-(nicht 84) !67-(nicht 67) !49-(nicht 49) !163-(nicht 163) !179-(nicht 179) !
PG-SEROSE AG Monien 22
Ein eigener Löser
… läuft unter Linux… löst durchaus schon schwierige Instanzen,
(1..10,12) z.B.
PG-SEROSE AG Monien 23
Fazit
In der PG: Konzentration auf spieltheoretische
MethodenVermeidung der Deadlocks, z.B. durch
Verwendung von speziellen Eingabeinstanzen oder durch Erlauben von Ziehe-Operationen ?
Vermeidung von Zielbereichsanalysen, z.B. durch Vornummerierung von Boxen und Zielfeldern.
Vermeidung der Notwendigkeit von zielgerichteten Suchen z.B. durch Expansion der Labyrinthe (Straßen breiter machen)
PG-SEROSE AG Monien 24
Aufgaben dieser PG
Berechnung einer global optimalen LösungBerechnung eines bestmöglichen Nash
EquilibriumsBerechnung einer Lösung über AuktionenBerechnung einer heuristisch
eigenständigen LösungInstanzengenerator, Optimierer, Auktionator, Simulator, …
Jeder Teilnehmer schreibt einen eigenen Agenten. Anbindung zum Simulator über MPI.