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

DOI10.1145/3447928.3456705arXiv2006.09132MaRDI QIDQ6201599FDOQ6201599

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)

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}.

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)

Cites Work

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

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)