On the decidability of reachability in continuous time linear time-invariant systems

DOI10.1145/3447928.3456705MaRDI QIDQ6201599zbMATH OpenFDO

Authors Amaury Pouly

Publication date 21 February 2024

Published in Proceedings of the 24th International Conference on Hybrid Systems: Computation and Control (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2006.09132

zbMATH Keywords

control theoryreachabilitydecidabilityexponentiallinear differential equationLTI systemstheory of the reals

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Specification and verification (program logics, model checking, etc.) (68Q60) Control/observation systems governed by functional relations other than differential equations (such as hybrid and switching systems) (93C30)

Abstract: We consider the decidability of state-to-state reachability in linear time-invariant control systems over continuous time. We analyse this problem with respect to the allowable control sets, which are assumed to be the image under a linear map of the unit hypercube. This naturally models bounded (sometimes called saturated) controls. Decidability of the version of the reachability problem in which control sets are affine subspaces of $mathbb{R}^n$ is a fundamental result in control theory. Our first result is decidability in two dimensions ($n=2$) if the matrix $A$ satisfies some spectral conditions, and conditional decidablility in general. If the transformation matrix $A$ is diagonal with rational entries (or rational multiples of the same algebraic number) then the reachability problem is decidable. If the transformation matrix $A$ only has real eigenvalues, the reachability problem is conditionally decidable. The time-bounded reachability problem is conditionally decidable, and unconditionally decidable in two dimensions. Some of our decidability results are conditional in that they rely on the decidability of certain mathematical theories, namely the theory of the reals with exponential ($mathfrak{R}_{exp}$) and with bounded sine ($mathfrak{R}_{exp,sin}$). We also obtain a hardness result for a mild generalization of the problem where the target is simple set (hypercube of dimension $n-1$ or hyperplane) instead of a point, and the control set is a convex bounded polytope. In this case, we show that the problem is at least as hard as the emph{Continuous Positivity problem} or the emph{Nontangential Continuous Positivity problem}.

Cites work

• scientific article; zbMATH DE number 3776332 (Why is no real title available?)
• scientific article; zbMATH DE number 1303067 (Why is no real title available?)
• scientific article; zbMATH DE number 1157649 (Why is no real title available?)
• scientific article; zbMATH DE number 1169378 (Why is no real title available?)
• scientific article; zbMATH DE number 2163583 (Why is no real title available?)
• scientific article; zbMATH DE number 3232021 (Why is no real title available?)
• scientific article; zbMATH DE number 3256013 (Why is no real title available?)
• scientific article; zbMATH DE number 3334376 (Why is no real title available?)
• A Modified Riccati Transformation for Decentralized Computation of the Viability Kernel Under LTI Dynamics
• A controllability minimum principle
• A survey of computational complexity results in systems and control
• Algorithms in real algebraic geometry
• An algebraic approach to bounded controllability of linear systems†
• An explicit description of null controllable regions of linear systems with saturating actuators.
• Boundedness of the domain of definition is undecidable for polynomial ODEs
• Complexity of stability and controllability of elementary hybrid systems
• Computability with low-dimensional dynamical systems
• Computation in One-Dimensional Piecewise Maps
• Constrained controllability of discrete-time systems†
• Continuous-time orbit problems are decidable in polynomial-time
• Control theory in the plane.
• Controllable regions of linear systems with bounded inputs
• Decidability of the reachability for a family of linear vector fields
• Hybrid Systems: Computation and Control
• Low dimensional hybrid systems -- decidable, undecidable, don't know
• Mathematical Description of Linear Dynamical Systems
• Null Controllability of Linear Systems with Constrained Controls
• Null controllable region of LTI discrete-time systems with input saturation
• On Zonotopes
• On the Skolem problem for continuous linear dynamical systems
• On the behaviour of dynamical systems subject to bounded disturbances
• On the computational complexity and geometry of the first-order theory of the reals. I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals
• On the computational power of neural nets
• On the decidability and complexity of problems for restricted hierarchical hybrid systems
• On the decidability of reachability in linear time-invariant systems
• Overview of complexity and decidability results for three classes of elementary nonlinear systems
• REACHABILITY PROBLEMS IN LOW-DIMENSIONAL ITERATIVE MAPS
• Reachability analysis of dynamical systems having piecewise-constant derivatives
• Reachability in Linear Dynamical Systems
• Reachability problems for one-dimensional piecewise affine maps
• Some undecidable problems involving elementary functions of a real variable
• State estimation of linear dynamical systems under bounded control
• Symbolic reachability computation for families of linear vector fields
• The continuous Skolem-Pisot problem
• The removal of \pi from some undecidable problems involving elementary functions
• Unbounded-time analysis of guarded LTI systems with inputs by abstract acceleration
• Zonotope/Hyperplane Intersection for Hybrid Systems Reachability Analysis

This page was built for publication: On the decidability of reachability in continuous time linear time-invariant systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6201599)