Symbolic Abstractions From Data: A PAC Learning Approach
This addresses the challenge of applying symbolic control to systems without accurate models, offering a method with statistical guarantees, though it is incremental as it builds on existing PAC frameworks.
The paper tackles the problem of constructing symbolic abstractions for systems with unknown dynamics by introducing a data-driven approach that relies on state-input successor evaluations instead of closed-form models, and provides PAC guarantees on accuracy and confidence with bounds on required data.
Symbolic control techniques aim to satisfy complex logic specifications. A critical step in these techniques is the construction of a symbolic (discrete) abstraction, a finite-state system whose behaviour mimics that of a given continuous-state system. The methods used to compute symbolic abstractions, however, require knowledge of an accurate closed-form model. To generalize them to systems with unknown dynamics, we present a new data-driven approach that does not require closed-form dynamics, instead relying only the ability to evaluate successors of each state under given inputs. To provide guarantees for the learned abstraction, we use the Probably Approximately Correct (PAC) statistical framework. We first introduce a PAC-style behavioural relationship and an appropriate refinement procedure. We then show how the symbolic abstraction can be constructed to satisfy this new behavioural relationship. Moreover, we provide PAC bounds that dictate the number of data required to guarantee a prescribed level of accuracy and confidence. Finally, we present an illustrative example.