Optimized State Space Grids for Abstractions

DOI10.1109/TAC.2016.2642794zbMATH Open1390.93419arXiv1711.01637OpenAlexW3099113746MaRDI QIDQ4566928FDOQ4566928

Authors: A. Weber, Matthias Rungger, Gunther Reißig 

Publication date: 27 June 2018

Published in: IEEE Transactions on Automatic Control (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1711.01637

Mathematics Subject Classification ID

Synthesis problems (93B50) Control/observation systems governed by functional relations other than differential equations (such as hybrid and switching systems) (93C30) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Cited In (6)

• Alexander Borisovich Kurzhanskiĭ (on the occasion of his 75th birthday)
• Merge-and-Shrink Abstraction
• On distributed symbolic control of interconnected systems under persistency specifications
• Abstraction-based control synthesis using partial information
• Lazy controller synthesis for monotone transition systems and directed safety specifications
• ABS: A formally correct software tool for space-efficient symbolic synthesis

This page was built for publication: Optimized State Space Grids for Abstractions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4566928)