Search

This paper presents an abstraction-refinement based framework for optimal controller synthesis of discrete-time systems with respect to $\omega$-regular objectives. It first abstracts the discrete-time “concrete” system into a finite weighted transition system using a finite partition of the state-space. Then, a two-player mean payoff parity game is solved on the product of the abstract system and the Buchi automaton corresponding to the $\omega$-regular objective, to obtain an optimal “abstract” controller that satisfies the $\omega$-regular objective. The abstract controller is guaranteed to be implementable in the concrete discrete-time system, with a sub-optimal cost. The abstraction is refined with finer partitions to reduce the suboptimality. In contrast to existing formal controller synthesis algorithms based on abstractions, this technique provides an upper bound on the trajectory cost when implementing the suboptimal controller. A robot surveillance scenario is presented to illustrate the feasibility of the approach.

In the game theoretic approach to the synthesis of reactive systems, specifications are often given as a conjunction of linear time properties. An implementation can be obtained from a winning strategy derived from a suitable generalized parity game in which each property produces a parity acceptance condition. Safety and persistence properties usually make up the majority of the specification. We show how this can be exploited to play the game in two stages and substantially speed up synthesis without sacrificing generality and conciseness of specification.

This paper presents a new lower bound for the discrete strategy improvement algorithm for solving parity games due to Voege and Jurdzinski. First, we informally show which structures are difficult to solve for the algorithm. Second, we outline a family of games on which the algorithm requires exponentially many strategy iterations, answering in the negative the long-standing question whether this algorithm runs in polynomial time. Additionally we note that the same family of games can be used to prove a similar result w.r.t. the strategy improvement variant by Schewe as well as the strategy iteration for solving discounted payoff games due to Puri.