Contact

EMail:

DIRECTOR

Prof. Dr. Ernst-Rüdiger Olderog,

Department of Computing Science, FK II, University of Oldenburg,

D-26111 Oldenburg, Germany

COODINATOR

Ira Wempe,

Department of Computing Science, FK II, University of Oldenburg,

D-26111 Oldenburg, Germany

[Seminar 05.06.2019] Wuerdemann

Solving High-Level Petri Games

Nick Würdemann

Abstract

The manual implementation of local controllers for autonomous agents in a distributed and concurrent setting is an ambitious and error-prune task. Synthesis algorithms, however, allow for the automatic generation of such controllers given a formal specification of the system’s goal. Recently, high-level Petri games were introduced to allow for a concise modeling technique of distributed systems with a safety objective. One way of solving these games is by a translation to low-level Petri games and applying an existing solving algorithm.

In this paper we present a new solving technique for a subclass of high-level Petri games with a single uncontrollable player, a bounded number of controllable players, and a local safety objective. The technique exploits symmetries in the high-level Petri game. We report on encouraging experimental results of a prototype implementation generating the reduced state space. The results for four existing and one new benchmark family show a state space reduction by a factor of up to 2,366

(Changed: 2021-04-30)