On the polytope escape problem for continuous linear dynamical systems

DOI10.1145/3049797.3049798MaRDI QIDQ5275313zbMATH OpenOpenAlexFDO

Authors Joël Ouaknine, J. Sousa Pinto, James Worrell

Publication date 11 July 2017

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

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

zbMATH Keywords

continuous linear dynamical systemsorbit problem

Mathematics Subject Classification ID

Complexity and performance of numerical algorithms (65Y20) Specification and verification (program logics, model checking, etc.) (68Q60) Linear programming (90C05) Transformations (93B17) Linear systems in control theory (93C05) Control/observation systems governed by ordinary differential equations (93C15)

Abstract: The Polyhedral Escape Problem for continuous linear dynamical systems consists of deciding, given an affine function $f:mathbb{R}^{d}ightarrowmathbb{R}^d$ and a convex polyhedron $mathcalPsubseteqmathbb{R}^d$, whether, for some initial point $$ in $mathcalP$, the trajectory of the unique solution to the differential equation $$, $$, is entirely contained in $mathcalP$. We show that this problem is decidable, by reducing it in polynomial time to the decision version of linear programming with real algebraic coefficients, thus placing it in $existsmathbbR$, which lies between NP and PSPACE. Our algorithm makes use of spectral techniques and relies among others on tools from Diophantine approximation.

Recommendations

• Invariant polytopes of linear systems
• A control problem for affine dynamical systems on a full-dimensional polytope.
• On recurrent reachability for continuous linear dynamical systems
• scientific article; zbMATH DE number 7204476
• The continuous Skolem-Pisot problem

Cited in

(1)

• scientific article; zbMATH DE number 7724206 (Why is no real title available?)

This page was built for publication: On the polytope escape problem for continuous linear dynamical systems

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