Data-Driven Abstraction-Based Control Synthesis

This paper studies formal synthesis of controllers for continuous-spacesystems with unknown dynamics to satisfy requirements expressed as lineartemporal logic formulas. Formal abstraction-based synthesis schemes rely on aprecise mathematical model of the system to build a finite abstract model,which is then used to design a controller. The abstraction-based schemes arenot applicable when the dynamics of the system are unknown. We propose adata-driven approach that computes the growth bound of the system using afinite number of trajectories. The growth bound together with the sampledtrajectories are then used to construct the abstraction and synthesise acontroller. Our approach casts the computation of the growth bound as a robust convexoptimisation program (RCP). Since the unknown dynamics appear in theoptimisation, we formulate a scenario convex program (SCP) corresponding to theRCP using a finite number of sampled trajectories. We establish a samplecomplexity result that gives a lower bound for the number of sampledtrajectories to guarantee the correctness of the growth bound computed from theSCP with a given confidence. We also provide a sample complexity result for thesatisfaction of the specification on the system in closed loop with thedesigned controller for a given confidence. Our results are founded onestimating a bound on the Lipschitz constant of the system and provideguarantees on satisfaction of both finite and infinite-horizon specifications.We show that our data-driven approach can be readily used as a model-freeabstraction refinement scheme by modifying the formulation of the growth boundand providing similar sample complexity results. The performance of ourapproach is shown on three case studies.