Suche Home Einstellungen Anmelden Hilfe

Gemeinsam mit Bernd Finkbeiner, Universität des Saarlandes, führen wir Petri-Spiele als einen neuartigen Spiele-Typ mit unvollständiger Information ein. Die einzelnen Spieler sind in System- und Umgebungsspieler unterteilt und werden durch Token im Petri-Netz dargestellt. Die Spieler kennen die Zustände der anderen Spieler nicht, es sei denn, sie kommunizieren miteinander. Dann wird maximal die gesamte kausale Vergangenheit ausgetauscht. Das Ziel der Systemspieler ist es, unabhängig von der Umgebung gewisse unsichere Zustände zu vermeiden.

Wir untersuchen die Frage, ob es entscheidbar ist, dass es eine gewinnende Strategie für die Systemspieler gibt. Für beschränkte Petri-Spiele mit nur einem Umgebungsspieler, aber beliebig vielen Systemspielern ist der Entscheidbarkeitsbeweis gelungen. Er basiert auf Konzepten der Petri-Netz-Theorie. Insbesondere haben wir eine neuartige Definition von maximalem Schnitt in den Entfaltungen von Petri-Netzen gefunden, mit denen sich im Spielablauf Wiederholungen mit äquivalentem Wissenstand der Systemspieler erkennen lassen. Es konnte sogar gezeigt werden, dass die Komplexität des Entscheidungsproblems EXPTIME-vollständig ist. Aus einer mit dem Entscheidungsalgorithmus konstruierten endlichen Gewinnstrategie lässt sich ein verteilter Controller synthetisieren, bestehend aus der parallelen Komposition lokaler endlicher Automaten für jeden einzelnen Systemspieler.

Für beschränkte Petri-Spiele mit mehr als einem Umgebungsspieler ist die Entscheidbarkeitsfrage jedoch weiterhin ungelöst. Für unbeschränkte Petri-Spiele konnte durch eine Reduktion gezeigt werden, dass die Frage nach der Existenz einer gewinnenden Strategie unentscheidbar ist.

Benutzer: gast • Besitzer: schwill • Zuletzt geändert am: