2023/12/25 by Anas Makdesi, Antoine Girard, Laurent Fribourg · 2 citations
Computer Science · Engineering · Mathematics · #A priori and a posteriori #Advanced Control Systems Optimization #Algorithm #Bounded function #Computation #Computer science #Control Systems and Identification #Data structure #Formal Methods in Verification #Mathematics #Monotone polygon #Partition (number theory) #Theoretical computer science
paper · doi:10.1109/tac.2023.3346793
openalex publication_date 2023/12/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/27
In this paper, we consider the problem of computing from data guaranteed set-valued over-approximations of unknown monotone functions with additive disturbances. We provide a characterization of a simulating map that provably contains all monotone functions that are consistent with the data. This map is also minimal in the sense that any set-valued map containing all consistent monotone functions would also include the map we are proposing. We show that this minimal simulating map is interval-valued and admits a simple construction on a finite partition induced by the data. As the complexity of the partition increases with the amount of data, we also consider the problem of computing minimal interval-valued simulating maps defined on partitions that are fixed a priori. We present an efficient algorithm for their computation. We then use those data-driven over-approximations to build models for partially unknown systems where the unknown part is monotone. The resulting models are used to construct finite-state symbolic abstractions, paving the way for discrete controller synthesis methods to be applied. We extend our approach to handle systems with bounded derivatives and introduce an algorithm to calculate the bounds on those derivatives and on the disturbances from the data. We present several numerical experiments to test the performance of the introduced method and show that the data-driven abstractions are suitable for controller synthesis purposes.