On-The-Fly Control of Unknown Systems: From Side Information to Performance Guarantees through Reachability
Authors:
- Franck DjeumouFDFranck Djeumou
- Abraham P. VinodAVAbraham P. Vinod
- Eric GoubaultEGEric Goubault
- Sylvie PutotSPSylvie Putot
- Ufuk TopcuUTUfuk Topcu
Preprint
Abstract
We develop data-driven algorithms for reachability analysis and control of systems with a priori unknown nonlinear dynamics. The resulting algorithms not only are suitable for settings with real-time requirements but also provide provable performance guarantees. To this end, they merge data from only a single finite-horizon trajectory and, if available, various forms of side information. Such side information may include knowledge of the regularity of the dynamics, algebraic constraints on the states, monotonicity, or decoupling in the dynamics between the states. Specifically, we develop two algorithms, $\texttt{DaTaReach}$ and $\texttt{DaTaControl}$, to over-approximate the reachable set and design control signals for the system on the fly. $\texttt{DaTaReach}$ constructs a differential inclusion that contains the unknown dynamics. Then, in a discrete-time setting, it over-approximates the reachable set through interval Taylor-based methods applied to systems with dynamics described as differential inclusions. We provide a bound on the time step size that ensures the correctness and termination of $\texttt{DaTaReach}$. $\texttt{DaTaControl}$ enables convex-optimization-based control using the computed over-approximation and the receding-horizon control framework. Besides, $\texttt{DaTaControl}$ achieves near-optimal control and is suitable for real-time control of such systems. We establish a bound on its suboptimality and the number of primitive operations it requires to compute control values. Then, we theoretically show that $\texttt{DaTaControl}$ achieves tighter suboptimality bounds with an increasing amount of data and richer side information. Finally, experiments on a unicycle, quadrotor, and aircraft systems demonstrate the efficacy of both algorithms over existing approaches.
Keywords
All Related Versions
This publication has 15 references indexed in Scilit:
- Adaptive restart of accelerated gradient methods under local quadratic growth conditionIMA Journal of Numerical Analysis, 2019
- Sparse identification of nonlinear dynamics for model predictive control in the low-data limitProceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 2018
- Linear predictors for nonlinear dynamical systems: Koopman operator meets model predictive controlAutomatica, 2018
- Decomposition of Reachable Sets and Tubes for a Class of Nonlinear SystemsIEEE Transactions on Automatic Control, 2018
- Data-driven and model-based verification via Bayesian identification and reachability analysisAutomatica, 2017
- An Accelerated Dual Gradient-Projection Algorithm for Embedded Linear Model Predictive ControlIEEE Transactions on Automatic Control, 2013
- Ordinary Differential Equations and Dynamical Systems2012
- Constrained model predictive control: Stability and optimalityAutomatica, 2000
- Robust one‐step receding horizon control for constrained systemsInternational Journal of Robust and Nonlinear Control, 1999
- Verified Integration of ODEs and Flows Using Differential Algebraic Methods on High-Order Taylor ModelsReliable Computing, 1998