On the Polytope Escape Problem for Continuous Linear Dynamical Systems

Abstract

The Polyhedral Escape Problem for continuous linear dynamical systems consists of deciding, given an affine function $f:{\mathbb{R}}^d\to {\mathbb{R}}^d$ and a convex polyhedron $\mathcal{P}\subseteq {\mathbb{R}}^d$, whether, for some initial point ${\mathbf{x}}_0$ in $\mathcal{P}$, the trajectory of the unique solution to the differential equation $\dot{\mathbf{x}}(t)=f(\mathbf{x}(t))$, $\mathbf{x}(0)={\mathbf{x}}_0$, is entirely contained in $\mathcal{P}$. 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 $\exists \mathbb{R}$, which lies between NP and PSPACE. Our algorithm makes use of spectral techniques and relies among others on tools from Diophantine approximation.

Accepted to HSCC 2017