Data-driven Reachability using Christoffel Functions and Conformal
  Prediction
Abdelmouaiz Tebjou Goran Frehse Faïcel Chamroukhi
An important mathematical tool in the analysis of dynamical systems is the
approximation of the reach set, i.e., the set of states reachable after a given
time from a given initial state. This set is difficult to compute for complex
systems even if the system dynamics are known and given by a system of ordinary
differential equations with known coefficients. In practice, parameters are
often unknown and mathematical models difficult to obtain. Data-based
approaches are promised to avoid these difficulties by estimating the reach set
based on a sample of states. If a model is available, this training set can be
obtained through numerical simulation. In the absence of a model, real-life
observations can be used instead. A recently proposed approach for data-based
reach set approximation uses Christoffel functions to approximate the reach
set. Under certain assumptions, the approximation is guaranteed to converge to
the true solution. In this paper, we improve upon these results by notably
improving the sample efficiency and relaxing some of the assumptions by
exploiting statistical guarantees from conformal prediction with training and
calibration sets. In addition, we exploit an incremental way to compute the
Christoffel function to avoid the calibration set while maintaining the
statistical convergence guarantees. Furthermore, our approach is robust to
outliers in the training and calibration set.