Title: Optimized State Space Grids for Abstractions,
Abstract: The practical impact of abstraction-based controller synthesis methods is
currently limited by the immense computational effort for obtaining
abstractions. In this note we focus on a recently proposed method to compute
abstractions whose state space is a cover of the state space of the plant by
congruent hyper-intervals. The problem of how to choose the size of the
hyper-intervals so as to obtain computable and useful abstractions is unsolved.
This note provides a twofold contribution towards a solution. Firstly, we
present a functional to predict the computational effort for the abstraction to
be computed. Secondly, we propose a method for choosing the aspect ratio of the
hyper-intervals when their volume is fixed. More precisely, we propose to
choose the aspect ratio so as to minimize a predicted number of transitions of
the abstraction to be computed, in order to reduce the computational effort. To
this end, we derive a functional to predict the number of transitions in
dependence of the aspect ratio. The functional is to be minimized subject to
suitable constraints. We characterize the unique solvability of the respective
optimization problem and prove that it transforms, under appropriate
assumptions, into an equivalent convex problem with strictly convex objective.
The latter problem can then be globally solved using standard numerical
methods. We demonstrate our approach on an example.